diff options
Diffstat (limited to 'presentation')
| -rw-r--r-- | presentation/presentation.md | 15 |
1 files changed, 14 insertions, 1 deletions
diff --git a/presentation/presentation.md b/presentation/presentation.md index d3ab7be..3004971 100644 --- a/presentation/presentation.md +++ b/presentation/presentation.md @@ -102,7 +102,20 @@ We'll partition the tree such that: * Working bottom-up, we can compute $A$'s state in the root of each part in $O(1)$. -Note: computing the partition takes time $O(m \log{m})$ as it uses a sort. +## LCA Closure Questions + +**Given**: a tree T. + +**Questions**: given $W \subseteq V(T)$, output the LCA closure of $W$. + +Can be solved in $\langle O(n), O(m \log m) \rangle$ (Section 4.1.2). + +## LCA Closure Questions + +* Preprocess for LCA. +* Given $W$, sort it according to in-order numbers. +* Add the LCA's of pairs of subsequent vertices in the sorted list. + ## Types of Parts |