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

Автор FineLine, история, 7 лет назад, По-английски

Hello Everyone ,I am trying to solve this problem for some time now.I could not find an explanation in English for it anywhere . The question is related to DP (on trees) . In Brief the problem asks you to find the minimum number of edges to be removed to isolate a subtree of size p .The original problem statement can be seen here.Thanks in advance :)

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

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

I think it is a dp[v][sz] with knapsack-like recalc

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

A similar problem Barricades appeared in Algorithmic Engagements 2007. That has been discussed in the book Looking For A Challenge, the preview of which includes this problem. :)