pblpbl's blog

By pblpbl, history, 2 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +11
  • Vote: I do not like it