Can anyone give a clear solution for this question.

https://www.codechef.com/EXPP2019/problems/EXUND

Basically, this is how I saw the problem,

One clear observation is,

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

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.