This would have been an easy problem if the N is <= 10000, as we can easily formulate the recurrence function.
lposra ←←←←← longestPathOfSubtreeRootedAt ⇛⇛⇛⇛⇛⇛⇛⇛ lposra[i] ⇗⇗ lposra[n] ⇶⇶ max ⇰⇰⇰⇰ ∀ i ∈ children of n ⇘⇘ ⇛⇛⇛⇛⇛⇛⇛⇛ 1stMax(depths[i]) \ + 2ndMax(depths[i]) + 1
but as N can be 105 the recursive solution gave me SIGSEGV. i just couldn’t think of any other way to solve this so flatted my recursive function into traversing and resolving parts and submitted it with 9.35s. but there is a solution with 0.35s, I couldn’t think of another way to solve this. 😦