Help with tree dp problem

Revision en1, by pblpbl, 2021-12-31 20:02:23

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English pblpbl 2021-12-31 20:02:23 549 Initial revision (published)