loverBoUy's blog

By loverBoUy, history, 3 years ago, In English

Hello!

Given a binary tree, find a** maximum path for each node**.

Hope to get an optimal solution Input- N=6

edges= 1->2,2->3,1->4,4->5,4->6

output= 2 3 4 3 4 4

Thanks in advance!

  • Vote: I like it
  • +2
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

You can solve this problem using DP on trees, check this tutorial

»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

solition in O(n log n)

lets find the answer for node V. V has O(logN) nodes in path from V to root. Let U — node in this path. then also let's find for each V max_d[V] — max len from V to some node in subtree of V.

let's try to update the answer for V. there's a exactly one son of U, who is in the path from V to root, let it be Z. then there's the algorithm to find the ans for V, if U is known.

Spoiler

i think it's pretty obvious why it works. so then whole alg is this:

Spoiler