u literally go from each node to the root so if u have a chain like this 1 -> 2-> 3-> 4-> 5-> 6 then your algorithm iterate from 6 to 1 and from 5 to 1 and from 4 to 1 and so on which mean u walk : n — 1 + n — 2 + ... + 1 = n * (n — 1) / 2 which can be considered o(n2)

I went from every leaf node to node 1. Which complexity should be O(nlogn) in worst . But I also got tle in test case 6

Funny thing is that initially all the trees were either not deep, or did not have many leaves. Around 6 hours before the contest I realized that solutions in O(sum_of_leaf_depths) might be able to pass. That is when I added test 6. Here is the description of it:

There is 1 testcase with N=300 000. Letters are assigned randomly. First I build a long path from vertex 1 to vertex 150 000. So basically 1 — 2 — 3 — ... — 150 000. I randomly decided if child will be right or left. Then at 150 000 I add a balanced binary tree with 150 000 verticies. That makes around 75 000 leafs with depth 150 000. Lastly, I shuffled the vertex numbers (but 1 keeps being the root).

Go from each leaf, for a subtree if u already have found a minimal answer, don't look at the path for the right subtree. I got AC doing this.

i got AC by pruning the branches, check my code below- https://codeforces.me/contest/1900/submission/234642669

because you are dump