My task is to efficiently process Q
queries in a spanning tree graph with N
nodes.
Each query refers to an edge that I am required to process, and I am supposed to output the sizes of each of the two components in the graph that remain after removing that edge.
My current idea is to start a DFS from the two nodes connected by that edge, making sure that the DFS never traverses across the edge itself. This way, I'll be able to find the sizes of the two components in O(N)
time, for a total complexity of O(Q * N)
.
However, I think that there is some sort of pre-processing that I can do to lower the time complexity of my solution even further, but I just can't think of what that might be. Can somebody please point me in the right direction?
Well, here's a strategy I just came up with:
Firstly, find any node that has a degree of exactly
1
(which is guaranteed to exist in a spanning tree graph; it is called a "leaf"). Run a DFS from that node, keeping a variablecount
representing the number of nodes that have been visited so far. Every time you traverse an edge, the size of the two components formed by removing that edge would have to equalcount
andN - count
because of the special properties of a tree (specifically, there is exactly one path between any pair of nodes). This results in an algorithm withO(N)
preprocessing andO(1)
query answering, for a total time complexity ofO(N + Q)
.