How to find size of each tree in a forest?

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.

• You mean $q$ queries, each of which is a collection of edges to remove? – Dmitri Urbanowicz Jun 15 at 19:27
• @DmitriUrbanowicz yes – Resorcinol Jun 15 at 20:07

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.