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

The number of unique ranks is equal to the greatest rank. With this observation, we can create an \mathcal{O}(N^2) 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.

\displaystyle down[u] = 1 + \max_{v \in children[u]} down[v] \displaystyle up[u] = \max\left(up[parent[u]], 2 + \max_{v \in children[parent[u]] \setminus \{u\}} down[v]\right)

The answer for each node is \max(down[u], up[u]).

Time complexity: \mathcal{O}(N)

Comments


  • 9
    Riolku  commented on Dec. 20, 2018, 2:39 p.m.

    For calculating up[u], it should be up[parent[u]] + 1


  • -12
    Darcy_Liu  commented on May 1, 2018, 9:48 p.m.

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


    • 18
      wleung_bvg  commented on May 1, 2018, 11:14 p.m.

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


  • 3
    Ninjaclasher  commented on Oct. 4, 2017, 9:35 a.m. ← edit 3

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


    • 1
      Riolku  commented on Jan. 5, 2019, 9:48 p.m.

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