# How fast can we find and disconnect roots in a forest?

Consider a forest of rooted trees. The problem is to support two operations:

1. disconnect(v): if v is the root of some tree in the forest, remove all edges of v;
2. findroot(v): find root of the tree containing node v.

Are there known worst-case lower bounds for such operations? In particular, is it possible to support both operations in $O(1)$ worst-case time?

Note that this problem is equivalent to the following version of marked ancestor problem:

1. mark(v): mark node v of the rooted tree, if its direct parent already marked or if v is the root;
2. firstmarked(v): return nearest marked ancestor of v.

There is a known lower bound trade-off if we allow mark(v) to mark any node:

We present a new lower bound for the marked ancestor problem in the cell probe model with word size b between the update time $t_u$ and the query time $t_q$, $$t_q = \Omega(\frac{\log n}{\log(t_u b \log n)})$$

### BRICS RS-98-7 Alstrup et al.: Marked Ancestor Problems

For a reasonable word size $b$, this trade-off implies that it is impossible to support both operations within $O(1)$ worst-case time.

Alstrup et al. prove the same trade-off for various related problems. However I couldn't find any assertions about my version: their proof technique seems to rely on arbitrary gaps between marked nodes.

• In “remove all its edges”, does the “it” refer to the tree, or just to the root? May 17, 2018 at 9:40
• It refers just to the root. May 17, 2018 at 10:32

The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations , thus overcoming the lower bound for generic version of the problem. Their solution is based on Euler tour of the tree with union-split-find structure (and fast LCA for trees with unbounded degree).