记录【P3047 [USACO12FEB]Nearby Cows G】

传送门。

$\texttt{Description}$

给定一棵树，边权为 $1$，点有点权，对于每一个点输出与它距离不超过 $k$ 的所有点的点权和。

$1\le n\le 10^5$，$1\le k\le 20$。

$\texttt{Solution}$

考虑树形 $\texttt{DP}$，设 $f_i$ 为 $i$ 点的答案。

但我们发现这样很难去搞 $\texttt{DP}$，因为距离无法确定。

所以考虑再加一维状态，$f_{i,j}$ 表示距离 $i$ 不超过 $j$ 的点的点权和。

这样就可以愉快的转移了。

很套路的，要搞一个 $g_{i,j}$，表示在以 $i$ 为根的子树中，距离 $i$ 不超过 $j$ 的点的点权和。

很容易地写出状态转移方程：$f_{v,j}=f_{u,j-1}+g_{v,j}-g_{v,j-2}$。

然后 $g_{v,j}-g_{v,j-2}$ 可以表示成 $sum_{v,j}+sum_{v,j-1}$，其中 $sum_{i,j}$ 表示在以 $i$ 为根的子树中，距离 $i$ 恰好为 $j$ 的点的点权和。

$sum_{i,j}$ 可在第一次 $\texttt{dfs}$ 中通过递推来得到。$sum_{u,j}=\sum_{\text{v is a son of u}}sum_{v,j-1}$。

然后就做完了。