Problem link : contest practice
Difficulty : Easy-Medium
Pre-requisites : Segment trees
Problem : Perform queries on the given tree and output the product of possible roots’ numbers after every query.
Explanation :
First of all, we can root the tree at the arbitrary node. Let’s make the DFS over this tree and calculate input and output times - that is the standard trick when the problem is about counting something in the subtree. When we enter some new node, we increase the value of the timer by one. Node’s input time is the value of the timer, when we’ve entered it. Node’s output time is the value of the timer, when we exit this node. Let’s denote the input time of the node x by tin_{x} and the output time by tout_{x}. There is a property that x is an ancestor of y if and only of [tin_{y}, tout_{y}] is a subsegment of [tin_{x}, tout_{x}].
Let’s maintain the value of D[x]. It will be equal to the number of appropriate paths if the root of the tree is located at the node x. Let’s see, what happens when we add a path between some two nodes x and y. There are two possible situations:
- LCA(x, y) is either x or y. In this case the value of D[k] gets increased by one if k is a descendant of the deepest node or if k is not a descendant of the highest node.
- LCA(x, y) is not equal to x and is not equal to y. In this case the value of D[k] gets increased if k is a descendant of either x or y.
Note that all increasings of D[k] are on the consecutive range if we re-enumerate them according the input times, obtained earlier. At the same time we will store the old node’s numbers. So we can handle a segment tree in order to perform the following operations:
- Increase the subsegment by one. It corresponds to the path’s adding.
- Decrease the subsegment by one. It corresponds to the path’s deletion.
- Keep track on the product of the old node’s numbers, for which the current value of D[x] is maximal.
So now we’ve obtained the standard segment tree problem. It can be solved in O(M log N) time.