×

# TROOT - Editorial

 2 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 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. Solutions : Setter Tester This question is marked "community wiki". asked 25 May '14, 14:00 719●43●63●77 accept rate: 0%

 8 Problem Statement itself is not clear !!!!!!! Codechef please focus on lunchtime also. answered 25 May '14, 17:15 138●1●1●3 accept rate: 0%
 3 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. :-( answered 26 May '14, 01:01 350●1●6●12 accept rate: 6%
 1 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 0★amish 16●1 accept rate: 0%
 0 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 1●1●1 accept rate: 0% Why do you think the answer should be 60 when no path was added? (25 May '14, 15:06) stzgd6★ 2 cannot be the root anytime. (25 May '14, 15:41) @stzgd & @xcwgf666 &all rply plz fast... (25 May '14, 16:15) I think you might misunderstand the statement. If no path was added, every node can be the root. (25 May '14, 17:13) stzgd6★ 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) stzgd6★ showing 5 of 6 show all
 0 can anyone exaplain this line 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)  answered 13 Jul '14, 12:29 3★soulmate 10●4 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,755
×1,672
×726
×5

question asked: 25 May '14, 14:00

question was seen: 2,632 times

last updated: 21 Aug '14, 00:47