Problem link : contest practice Difficulty : EasyMedium Prerequisites : 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:
Note that all increasings of D[k] are on the consecutive range if we reenumerate 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:
So now we've obtained the standard segment tree problem. It can be solved in O(M log N) time.
This question is marked "community wiki".
asked 25 May '14, 14:00

Problem Statement itself is not clear !!!!!!! Codechef please focus on lunchtime also. answered 25 May '14, 17:15

Should have been written as:
All this time I was thinking that all paths in the tree have to be considered. :( answered 26 May '14, 01:01

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." answered 21 Aug '14, 00:46

The solutions provided are both wrong for this example 5 4 1 2 2 3 2 4 4 5 + 1 3 + 3 5  1 3  3 5 answers should be 3 3 15 60 answered 25 May '14, 14:26
Why do you think the answer should be 60 when no path was added?
(25 May '14, 15:06)
2 cannot be the root anytime.
(25 May '14, 15:41)
I think you might misunderstand the statement. If no path was added, every node can be the root.
(25 May '14, 17:13)
The node numbered 2 has 3 edges already defined so 1 of it must be its parent therefore 2 cannot be the root if it is a binary tree @stzgd
(25 May '14, 17:38)
It doesn't need to be a binary tree. The statement doesn't mention anything about binary tree. It just need to be a tree.
(25 May '14, 18:36)
showing 5 of 6
show all

can anyone exaplain this line
answered 13 Jul '14, 12:29
