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
- Take last 3rd from (1..k)
- 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 :)