From 6f800605fbc32510ca8f7e680071ad8b4d02c720 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Sat, 11 Dec 2021 13:53:07 +0100 Subject: Expand on singleton case --- mgr.tex | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) (limited to 'mgr.tex') diff --git a/mgr.tex b/mgr.tex index a9d3121..af3cdb2 100644 --- a/mgr.tex +++ b/mgr.tex @@ -964,9 +964,10 @@ original tree $T$. We look them up in the precomputed run, then apply $A$'s transition to those states and $v$'s new label. We will compute the states of part roots in a bottom-up fashion, so the second -case is also simple: once we've computed the states in the children of $v$, we -again simply apply $A$'s transition function to those states and $v$'s new -label. +case is also simple. Both of $v$'s children are roots of parts (since the LCA +partition is based on a partition ready set), so once we've computed the states +in the children of $v$, we again simply apply $A$'s transition function to those +states and $v$'s new label. The third is the interesting case, that of a subtree with a hole. Consider the path from the hole $w$ up to the root $v$. What we claim is that the question -- cgit v1.2.3