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 \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 \begin{align*} down[u] &= 1 + \max_{v \in children[u]} down[v] \\ up[u] &= \max\left(1 + up[parent[u]], 2 + \max_{v \in children[parent[u]] \setminus \{u\}} down[v]\right) \end{align*}

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

Time complexity: \mathcal{O}(N)

Comments


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

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


    • 0
      thomas_li  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.


  • -14
    Darcy_Liu  commented on May 2, 2018, 1:48 a.m. ← edited

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


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

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


  • 0
    Ninjaclasher  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 \mathcal{O}(N) time complexity.


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

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