洛谷 P3523

显然考虑二分，设当前二分出的值是 \(lim\)。

那么就是称一个点能覆盖另一个点当且仅当它被选中且它与那个点的距离不大于 \(lim\)，要判断是否能选出不多于 \(m\) 个点覆盖到所有的关键节点。

令 \(f_i\) 表示节点 \(i\) 的子树中距离 \(i\) 最近的被选中的节点到 \(i\) 的距离，\(g_i\) 表示节点 \(i\) 的子树中距离 \(i\) 最远的还没有被覆盖的关键节点到 \(i\) 的距离。

定义有点绕，可以在这里停下来读一读。

假设当前在点 \(u\)。

初始时 \(f_u=\infty,g_u=-\infty\)。

然后 \(f_u=\min\limits_{v\in son_u}(f_u,f_v+1)\)，\(g_u=\max\limits_{v\in son_u}(g_u,g_v+1)\)。

然后如果点 \(u\) 是关键节点并且 \(f_u\gt lim\)，那么 \(g_u=\max(g_u,0)\)。

如果 \(f_u+g_u\le lim\)，那么 \(g_u=-\infty\)。

如果 \(g_u=lim\)，那么 \(u\) 必须被选择，所以 \(f_u=0,g_u=-\infty\)。

最后如果根节点的 \(g\ge 0\)，那么根节点也必须被选择。

Code：

#include <bits/stdc++.h>
using namespace std;
const int N = 300005, inf = 0x3f3f3f3f;
int n, m;
int ty[N];
int head[N], ver[N*2], nxt[N*2], cnt;
int f[N], g[N], tot = 0;

void add(int u, int v) {
	ver[++cnt] = v, nxt[cnt] = head[u], head[u] = cnt;
}

void dfs(int u, int fa, int lim) {
	f[u] = inf, g[u] = -inf;
	for (int i = head[u]; i; i = nxt[i]) {
		int v = ver[i];
		if (v == fa) continue;
		dfs(v, u, lim);
		f[u] = min(f[u], f[v] + 1);
		g[u] = max(g[u], g[v] + 1);
	}
	if (ty[u] && f[u] > lim) g[u] = max(g[u], 0);
	if (g[u] + f[u] <= lim) g[u] = -inf;
	if (g[u] == lim) g[u] = -inf, f[u] = 0, ++tot;
}

bool check(int x) {
	tot = 0, dfs(1, 0, x);
	if (g[1] >= 0) ++tot;
	return tot <= m;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) scanf("%d", &ty[i]);
	for (int i = 1, u, v; i < n; ++i) scanf("%d%d", &u, &v), add(u, v), add(v, u);
	int l = 0, r = n - 1;
	while (l < r) {
		int mid = l + r >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d", l);
	return 0;
}

原文地址：http://www.cnblogs.com/Kobe303/p/16885931.html