How to find size of each tree in a forest?

Question

Let $T$ be a tree with $n$ nodes. If I remove $k$ edges from $T$, I will have $k+1$ new trees i.e. a forest of $k+1$ trees.

How do I calculate the number of nodes in each of these new trees formed?

I need to do this for $q$ queries.

My approach: I can remove the $k$ edges from the original tree and run DFS on each nodes from which edge was deleted and find the size of the new tree. And then join the nodes back after getting size of each tree. But this is not optimal, can anyone suggest a better approach.

Answer 1

You can use any number of Dynamic Connectivity data structures, namely, an euler tour dynamic connectivity tree.

To summarize the reference, if you label the vertices of the original tree $T$ according to the first (denoted $label_f$) and last (denoted $label_l$) euler-tour visit order on $T$, you can maintain a BST $T^*$.

Each node $x$ in $T$ is linked to two nodes in $T^*$: $v_1$, $v_2$, where $key(v_1) = label_f(x)$ and $key(v_2) = label_l(x)$. Note $|T^*| = 2n $ and BST operations on $T^*$ will cost $O(\log n)$

Now, we can support the following operations on $T$:

• $cut(u, v)$: Disconnect the edge $(u,v)$. Denote $x$ the vertex whose $label_f$ is lesser. It is done simply by splitting from $T^*$ the interval $[label_f(x),label_l(x)]$ which can be done in $O(\log n)$ by splitting and merging.
• $findroot(v)$: Since the root of the tree has the minimum $label_f$, the root of $v$ will be the minimum node in the euler-tour BST in which he belongs

Since each node $x$ in $T$ is represented by exactly two nodes in $T^*$, by simply saving rank (tree size) on the euler tour BST ($T^*$), and dividing by $2$ you can answer the question "How many nodes are in the tree of $x$?" in $O(1)$, granted you are willing to pay $O(\log n)$ each time you disconnect an edge.