From 1145ace49ac081704bf1a357d74bc9c89a6ed7b7 Mon Sep 17 00:00:00 2001 From: Marcin Chrzanowski Date: Thu, 25 Nov 2021 16:34:12 +0100 Subject: Clear up partitioning --- mgr.tex | 14 +++++++++----- 1 file changed, 9 insertions(+), 5 deletions(-) (limited to 'mgr.tex') 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 -- cgit v1.2.3