Help for EXUND chipped tree

Can anyone give a clear solution for this question.
https://www.codechef.com/EXPP2019/problems/EXUND

1 Like

Basically, this is how I saw the problem,

One clear observation is,

  1. If a chip is placed in a node A, it is always better to move from that node to all its children’s.
    WHY?
    Because if a node has children, then it is of two cases (can be seen at least for this problem),
    a). Has 1 children (In this case moving from that Node A to it’s only child, we maintain that ans = 1, we are not losing anything).
    b). Has more than 1 children (Now we are moving the chips to it’s children and improvising the ans from ans = 1 to ans = number of childrens for Node A.) Again we did not lose anything.

From a),b) we clearly observe, that moving the chips from node to it’s children’s is a better step.

So, At K = 1, keep all the chips in the leaf nodes. Sum of leaf nodes will be the ans for K = 1 which is height 0 for each tree branch.
So, At K = 2, nodes which are height = 1, will be the count.
lllly, keep doing for all, K’s and return the answer.

Hope you got it.

1 Like

Can you please tell me what is wrong with my code? I followed the exact same approach of ‘chipping’ the leaves first. I maintained a parent array for every node and its corresponding number of children (nch). Whenever nch becomes zero, that means it becomes a leaf node. My code got WA for most of the hidden test cases. Cannot figure out the bug. My code: https://www.codechef.com/viewsolution/27265618.

Edge is not always top to bottom .It may be bottom to top .

case:

1
7 2
1 2
1 3
2 4
2 5
3 6
7 3

I followed the same approach bro. Can you please check my code once.
https://www.codechef.com/viewsolution/27255901. I’m getting runtime error.

Also can you share your code

I had made a tester code for this problem, it tells where your code went wrong. You can find it here:

I tried swapping a and b whenever a > b i.e, I always added the larger node in the adjacency list of smaller node.Still WA!

My solution is not clear, so cant share. use dfs to fill both array instead of loop.