2
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.