Clear up partitioning

1 files changed, 9 insertions, 5 deletions

diff --git a/mgr.tex b/mgr.tex
index 47c1013..41d0941 100644
--- a/mgr.tex
+++ b/mgr.tex
@@ -725,13 +725,17 @@ many parts, then, in a bottom-up fashion, compute the state in the root of each
 part in the relabeled tree. The computation for each part will take constant
 time.
 
+Partitioning into $O(m)$ parts will take time $O(m \log m)$, then after the
+bottom-up computation we will arrive at the root's state in time $O(m)$, thus
+answering the question in the promised time.
+
 \subsection{LCA partition}
 
-Consider a set of tree vertices $W$. We'll say that $W$ is \definedterm{LCA
-closed} if for every pair of vertices $v, w \in W$, it is the case that
-$\mathlca(v, w) \in W$ (note that one of $v$ or $w$ might be their LCA). We also
-require that the tree's root is in $W$ (just to ensure the partition we define
-next covers the whole tree).
+Consider a set of tree vertices $W \subseteq V(T)$. We'll say that $W$ is
+\definedterm{LCA closed} if for every pair of vertices $v, w \in W$, it is the
+case that $\mathlca(v, w) \in W$ (note that one of $v$ or $w$ might be their
+LCA). We also require that the tree's root is in $W$ (just to ensure the
+partition we define next covers the whole tree).
 
 The \definedterm{subtree of $v$} is $v$ along with all its descendants.
 We also consider subtrees with holes: the \definedterm{subtree of $v$ with hole