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: FatalEagle

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:

• commented on Sept. 27, 2021, 11:58 p.m.

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

• commented on Sept. 28, 2021, 3:56 p.m.

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.

• commented on May 2, 2018, 1:48 a.m. edited

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

• commented on May 2, 2018, 3:14 a.m. edited

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

• commented on Oct. 4, 2017, 1:35 p.m. edit 4

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

• commented on Jan. 6, 2019, 2:48 a.m.

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