m-chrzan.xyz
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-11 13:53:07 +0100
committerMarcin Chrzanowski <mc370754@students.mimuw.edu.pl>2021-12-11 13:53:07 +0100
commit6f800605fbc32510ca8f7e680071ad8b4d02c720 (patch)
treef792de1eaec966bccdabf894946a6ed3c5f59312
parent031bb87dd41b3210baa44edd097bd89a338ad5ab (diff)
Expand on singleton case
-rw-r--r--mgr.tex7
1 files changed, 4 insertions, 3 deletions
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