洛谷 P3000 [USACO10DEC] Cow Calisthenics G

思路

题目要求断若干条边后形成的连通块中，最大的直径最小，很明显的二分。关键就在于如何写 $check$ 函数了。

可以用 $dfs$ 来判断要断哪条边。

一、$d[u]$ 定义

设 $d[u]$ 为从 $u$ 出发到子树中【断开边后连通块的叶子节点】所经过的最多的节点数，包括 $u$ 节点自己。

这句话可能比较难理解。设 $v$ 为 $u$ 的一个子节点，那么程序会先递归判断以 $v$ 为根的子树中哪些边需要被断掉。那么再回朔到 $u$ 节点时，子树 $v$ 就算一个被删了一些边的连通块，那么子树 $v$ 就会有一些新的叶子节点。这些新叶子节点到 $u$ 会经过若干节点，$d[u]$ 就代表【经过节点数最多的】那条路径上的【节点数】。

如此一来，$d[v]$ 就表示从 $v$ 出发到其子树叶子节点经过的最多节点数。同时，它还可以表示节点 $u$ 走到【以 $v$ 为根的子树的叶子节点】所经过的最多边数。

（本人在看其他题解时想了好一会才想明白，因此花了这么多文字来解释，太菜了）

二、断边条件

现在考虑什么情况断边。

假设 $maxd$ 是目前所扫过的所有子节点 $v$ 中 $d[]$ 值最大的那个。

现在又扫完一个新节点 $v^{\prime }$：若 $maxd+d[v^{\prime }]>limit$，那就断边；否则用 $d[v^{\prime }]$ 更新 $maxd$。

问题又来了，断边时有两条边可供断开（即：$maxd,d[v^{\prime }]$ 分别代表的那一条），该断哪一条？

贪心的想，我们肯定要保留值较小的那一条。因为若保留大的，它未来可能会与其他更多的 $d[]$ 相加超出限制，导致更多的断边，这样显然时更劣的。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 7;

int n, m;
vector<int> e[maxn];

int d[maxn], cnt;
void dfs(int u, int f, int lim) {
	if (cnt > m) return ;
	int maxd = 0;
	for (int v : e[u]) {
		if (v == f) continue;
		dfs(v, u, lim);
		if (maxd + d[v] > lim)  // 超出限制, 断边, 并保留较小的那一条边 
		    ++cnt, maxd = min(maxd, d[v]);
		else maxd = max(maxd, d[v]);  // 没有超出限制, 更新 maxd 
	}
	d[u] = maxd + 1;
}
bool check(int x) {
	cnt = 0, dfs(1, 0, x);
	return cnt <= m;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i < n; ++i) {
		int u, v;
		scanf("%d%d", &u, &v);
		e[u].push_back(v);
		e[v].push_back(u);
	}
	
	// 二分最大直径的最小值 
    int l = 0, r = n - 1;
    int ans = 0;
	while (l <= r) {
		int mid = (l + r) >> 1;
		if (check(mid)) ans = mid, r = mid - 1;
		else l = mid + 1;
	}
	printf("%d\n", ans);
	return 0;
} 

若觉得此篇题解过于冗长，可以看看这篇