You are not logged in. Please login at www.codechef.com to post your questions!

×

TROOT - Editorial

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

xcwgf666's gravatar image

6★xcwgf666 ♦♦
719436377
accept rate: 0%


Problem Statement itself is not clear !!!!!!! Codechef please focus on lunchtime also.

link

answered 25 May '14, 17:15

deepanshum007's gravatar image

3★deepanshum007
138113
accept rate: 0%

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. :-(

link

answered 26 May '14, 01:01

rushilpaul's gravatar image

4★rushilpaul
3501612
accept rate: 6%

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."

link

answered 21 Aug '14, 00:46

amish's gravatar image

0★amish
161
accept rate: 0%

edited 21 Aug '14, 00:47

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

link

answered 25 May '14, 14:26

bakshinder's gravatar image

1★bakshinder
111
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) bakshinder1★

@stzgd & @xcwgf666 &all rply plz fast...

(25 May '14, 16:15) bakshinder1★

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) bakshinder1★

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

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)
link

answered 13 Jul '14, 12:29

soulmate's gravatar image

3★soulmate
104
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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