TLE for one test case of EXUND

Can someone tell me why my solution to problem EXUND is giving TLE for one test case.
My solution’s link:
Basically, I am using level order traversal to create a parent array, and storing all leaves in a separate array. Then, using leaves array and parent array I am assigning minimum k required for each node to get at least one chip.
Thanks in advance.

1 Like

Extend it for a tree of height N/2

1 Like

One of the testcases from the file you got TLE on is a broom. That is a chain of N/2 nodes and the rest N/2 connected to an endpoint of the chain. It is exactly the case mentioned by @aryanc403.

Your code’s complexity is the summation of heights of the leaves which in this case is O(N^2)