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

A tree DP problem
Автор Thost, 13 лет назад, По-английски

Could anyone help me to solve this problem?

I had tried several times,but failed.

Теги dp, tree
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
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.
→ Ответить