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.net/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]+1). So if dp[1] was 1 answer is last element (that is k)

If dp[2] 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]+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[1] = 2 as we could in case of max

so here dp[1] = 3+2

and answer becomes 5-5+1 = 1.

Hope this helps .

Upvote if this helped :)