How to solve this problem ?
Any good problem for dp on tree.
Define an r-neighbourhood of a vertex u as the set of all vertices v so that \mathrm{dist}(u, v) \le r.
Claim:
If the answer is r, then there exists some vertex v so that the sum of values of all vertices in its r-neighbourhood is \ge K.
Proof:
Consider an optimal set for the problem S and focus on its center c and its radius r. Then S is a subset of the r-neighbourhood of c. So we can include all nodes that are not in S but are in the r-neighbourhood of c, and we still have a valid solution.
So let’s find for each vertex v, and for each possible distance d from it, the sum of values of all nodes that fall within distance d of this node. We can do this because the maximum possible value of d is 2\cdot 60=120 (since we’re given that the maximum depth from the root is 60).
How to do it? First, let subt[v][d] denote the sum of values of all nodes that are in the subtree of v at a distance d from v. We can calculate this for all v and d in a single dfs.
Then let dp[v][d] denote the sum of values of all nodes that are at a distance d from v. Notice that we now need to consider two cases for vertices at distance d: either the node is in the subtree of v, or it is not in the subtree of v. We’ve already seen the first case. To handle the second case, note that these nodes will be at a distance d - 1 from \mathrm{par}(v). So the transition is:
dp[v][d] =\begin{cases} subt[v][d]&v \text{ is the root}\\ subt[v][d] + dp[\mathrm{par}(v)][d-1] - subt[v][d-2]& \text{otherwise} \end{cases}
Do you see why we have subtracted subt[v][d-2]? It’s because dp[\mathrm{par}(v)][d-1] also counts the nodes in the subtree of v that are at distance d-2 from v, but we only wanted to handle those nodes that are not in the subtree of v.
Now we have the values of sum of values of nodes at an exact distance d for each vertex. To convert this to sum of values of nodes in the d-neighbourhood of a vertex, just take the prefix sum.
4 Likes