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 tinx and the output time by toutx. There is a property that x is an ancestor of y if and only of [tiny, touty] is a subsegment of [tinx, toutx].
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.
If we root the tree at the node t and
for every present (added and not yet
deleted) path, the least common
ancestor of its endpoints is also one
of the endpoints of this path, then we
call the node t a possible root.
Should have been written as:
If we root the tree at the node t and
for every path that was added and not
yet deleted (by the queries), the
least common ancestor of its endpoints
is also one of the endpoints of this
path, then we call the node t a
possible root.
All this time I was thinking that all paths in the tree have to be considered.
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.
(how can the k be the descendant of the deepest node , since k is the root it can not be the descendant)
In every question at least one example should be explained, as how the output value was calculated from the input with diagram if needed. This will help everyone to understand the problem.
“Something obvious to author may not be obvious to all.”
