## Editorial for DMOPC '14 Contest 4 P6 - Save Nagato!

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Author:

The number of unique ranks is equal to the greatest rank. With this observation, we can create an algorithm by just finding the longest path from each node. However, we can do even better by using dynamic programming — root the tree arbitrarily, and then for each node, compute the longest path downwards and the longest path upwards.

The answer for each node is .

**Time complexity:**

## Comments

How do you calculate max of children of parent[u] without TLE'ing?

You can pass it as an argument when doing dfs. Just store max and second max for children. When recursing to a child, you pass either max or second max depending on if the child is the max value of not.

This comment is hidden due to too much negative feedback. Show it anyway.

Yes, it's to get the input, but the algorithm to solve the problem is also . .

....or you could just solve THICC '17 P6 - Tunnels and copy the code. Still time complexity.

Yes, this problem is far from unique. However, it is a great problem.