Codeforces will be possibly unavailable in the period between Sep. 19, 19:00 (UTC) and Sep. 19, 21:00 (UTC) because of maintenance. ×

### CP_Sucks's blog

By CP_Sucks, 2 years ago,  Wasnt able to get D in the contest . And Thought editorial was also confusing so trying to explain If i am wrong somewhere plz mention

I understood using the following code https://codeforces.com/contest/1153/submission/52692393

In the code we are setting first of all all the leaves to 1

Then for max we will take the min from all the dp of the childeren and for min we will add the dp of all the children

How i thought of this was dp[v] is basically how many numbers from the last can be allowed to pass to the top (root).

This is because we will be subtracting the result from k (k-dp+1). So if dp was 1 answer is last element (that is k)

If dp Then basically second last element (that is k-1).

So if min was there will have to go to number from the last of k by adding all the children dp.

But if we have max we can just stop to the min of all children (so that k-dp+1 will be maximum as dp[v] taken was minimum)

Take this tree for eg

Here mark all child as 1 so we are saying that we can take last 1 element from end of (1...k) . That is k itself.

Now as there is min in left we add 1+1+1 . What this means is that the best we can do is take last 3rd from (1...k) that is k-3+1. Similiarly for right part we add 1+1 that is best we can do is take k-2+1.

Now comes the root

Suppose if the root was max then we have 2 options

1. Take last 3rd from (1..k)
2. Take last 2nd from (1..k)

So best will be to take 2

That is the reason we are taking min(dp of all children so that in the end we will get a max) answer.

Now if the root was min there is no choice but to take 2+3 rd element from the end. we cant stop at taking just dp = 2 as we could in case of max

so here dp = 3+2

and answer becomes 5-5+1 = 1.

Hope this helps .

Upvote if this helped :) Comments (4)
 » Auto comment: topic has been updated by CP_Sucks (previous revision, new revision, compare).
 » How do i add image to the blog ?
 » Thanks a lot i finally understood the question!!!!!!! :)
•  » » Np :)