目前 dp[i][j] 表示 i 下面 距离 i 距离为 j 的点的点权和。
void dfs_up(int cur, int fa) {
for (int v : g[cur]) {
if (v == fa)continue;
for (int dep = 1; dep <= k; dep++) {
dp[v][dep] += dp[cur][dep - 1];
if (dep >= 2)dp[v][dep] -= dp[v][dep - 2];
}
dfs_up(v, cur);
}
}
如果你第二次 dfs 这么写,不妨看这个图(左图):
![P3174 [HAOI2009] 毛毛虫](https://cdn.luogu.com.cn/upload/pic/7967.png)
此时在求 dp[5][3] 时,会用到 dp[1][2](为 3,4,7,8 的点权和)减去 dp[5][1](为 7,8 的点权和),但是注意,此时的 dp[5][1] 已经被提前于 dp[5][3] 被更新,变成了 \color {red}{1}$$,7,8 的点权和,所以要从大到小倒序更新。
void dfs_up(int cur, int fa) {
for (int v : g[cur]) {
if (v == fa)continue;
for (int dep = k; dep >= 1; dep--) {
dp[v][dep] += dp[cur][dep - 1];
if (dep >= 2)dp[v][dep] -= dp[v][dep - 2];
}
dfs_up(v, cur);
}
}