Блог пользователя loverBoUy

Автор loverBoUy, история, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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