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

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

I'm stuck on the following problem:

Given a tree with $$$N$$$ nodes and a positive integer $$$D$$$ $$$(1 \leq N, D \leq 2\times 10^5)$$$, a set of marked nodes is a subset of nodes from the original graph such that marked nodes may not be closer to each other than distance $$$D$$$. What is the maximum number of marked nodes for this graph?

I tried tree dp with $$$dp[i][j]$$$ representing the answer for node $$$i$$$'s subtree such that all marked nodes in $$$i$$$'s subtree are $$$\geq j$$$ edges away from $$$i$$$ but it's too inefficient. Any ideas?

Полный текст и комментарии »

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