CF337D

2023-07-30

新鼠标,真高兴 (怎么和学校的一样)

由于是距离小于等于 $d$ ,所以如果一个点是魔法书所在点,它到达任何一个发现了怪物的点的距离都应该小于等于 $d$ 。

也就是说,距离这个节点最远的怪物点距离不超过 $d$

显然换根 dp 。

简单的想法是,维护每个点作为根的子树内 $(dp1[x])$ 外 $(dp3[x])$ ,距离根最远的怪物点。但是,这样就没法很好转移 $dp3[x]$ ,因为 $x$ 的兄弟节点子树内最远怪物点可能会更新 $dp3[x]$ 。

所以再开一个 $dp2[x]$ 表示 $x$ 为根的子树内距离根第二远的怪物点,就很好转移:

void dfs1(int x, int f) {
	dp1[x] = (monster[x] ? 0 : -INT_MAX);
	dp2[x] = -INT_MAX;
	for(int v : g[x]) {
		if (v == f) continue;
		dfs1(v, x);
		if (dp1[v] + 1 > dp1[x]) dp2[x] = dp1[x], dp1[x] = dp1[v] + 1;
		else if (dp1[v] + 1 > dp2[x]) dp2[x] = dp1[v] + 1;
	}
	return;
}
dp3[1] = -INT_MAX;
void dfs2(int x, int f) {
	for(int v : g[x]) {
		if (v == f) continue;
		if (dp1[x] == dp1[v] + 1) dp3[v] = max(dp3[x] + 1, dp2[x] + 1);
		else dp3[v] = max(dp3[x] + 1, dp1[x] + 1);
		dfs2(v, x);
	}
	return;
}