## Editorial for DMOPC '14 Contest 5 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

For calculating , it should be

+ 1This comment is hidden due to too much negative feedback. Click here to view it.

Yes, it's O(N) to get the input, but the algorithm to solve the problem is also O(N). O(N) + O(N) = O(N).

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