Thost's blog

A tree DP problem
By Thost, 13 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

13 years ago, # |
  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
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    How to calculate each node's k-th largest leaves then from up to bottom?
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      since it is a binary tree, so the value can be combined by it's parent and the other child. 
      → Reply
      • 13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        That's the one which I haven't meet with~
        Nice solution~
        → Reply