Thost's blog

A tree DP problem
By Thost, 15 years ago, In English

Could anyone help me to solve this problem?

I had tried several times,but failed.

Tags dp, tree
  • Vote: I like it
  • +8
  • Vote: I do not like it

15 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it
i think it is not a dynamic programming problem on a tree. it can be solved by mergement sort in O(NK) time.

we can transform the given tree into a binary tree by inserting some virtual point.
then we can compute the each node's k-th largest leaves from bottom to up, then from up to bottom.
→ Reply