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

Question

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.

Answer 1

The problem has name "fringe marked ancestor problem" and indeed has $O(\log \log n)$ worst-case solution for both operations [1], 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).

The same paper states that it is an open problem whether this bound is tight.

[1] D. Breslauer and G. F. Italiano. Near real-time suffix tree construction via the fringe marked ancestor problem. Selected papers from the 18th International Symposium on String Processing and Information Retrieval (SPIRE 2011) https://www.sciencedirect.com/science/article/pii/S1570866712001062#br0230