警示后人 20pts WA on #1 #5
查看原帖
警示后人 20pts WA on #1 #5
546150
liuChF楼主2024/5/9 19:21

目前 dp[i][j]dp[i][j] 表示 ii 下面 距离 ii 距离为 jj 的点的点权和。

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] 毛毛虫

此时在求 dp[5][3] 时,会用到 dp[1][2](为 3,4,7,8 3, 4, 7, 8 的点权和)减去 dp[5][1](为 7,87,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);
	}
}
2024/5/9 19:21
加载中...