考虑 \(k = 1\) 时,我们必须选择树的中心。猜测 \(k \ge 1\) 时也要选择树的中心。
首先可以发现,只要我们选择树的中心,则答案一定不会超过树的半径。
现在令树的中心为根。不难发现只要 \(n \ge 3\),这个根就有两个子树。
由于我们选择的 \(k\) 个点必须联通,所以如果我们不选择树的中心,就只能在树的中心的某个儿子 \(s_1\) 的子树里选。这会导致树的中心的另一个儿子 \(s_2\) 最深的叶子节点到达我们选择的 \(k\) 个点的距离超过树的半径,因此是不优的。
\(n \le 2\) 的情况,这个时候所有点都是中心,肯定要选。
证毕,我们必选树的中心。
因此令树的任意一个中心为根,选择以根的一棵子树即可。
不难发现这个贪心思路:看哪边的叶子距离它最近的被选的祖先最远,就把这个祖先的儿子给选上。
或者甚至不用找根,从叶子出发就好。因为 \(n \ge 3\) 的时候,以树的中心为根时的叶子和无根意义下的叶子其实是等价的。所以直接从无根意义下的叶子开始慢慢往里选 \(n - k\) 个点作为最后不选的点即可。再次手玩 \(n \le 2\) 发现也是合法的。
从叶子出发找多源最长路,普通 bfs 有困难,可以考虑魔改拓扑。每次我们只需要处理度数为 \(1\) 的点(叶子),并把这个叶子删去即可。
这个方法虽然简便但是也要依赖上面那个找根做法的证明。题解中找规律式的说明我不是很认可。
/*
* @Author: crab-in-the-northeast
* @Date: 2023-04-23 19:07:23
* @Last Modified by: crab-in-the-northeast
* @Last Modified time: 2023-04-23 19:33:09
*/
#include <bits/stdc++.h>
inline int read() {
int x = 0;
bool f = true;
char ch = getchar();
for (; !isdigit(ch); ch = getchar())
if (ch == '-')
f = false;
for (; isdigit(ch); ch = getchar())
x = (x << 1) + (x << 3) + ch - '0';
return f ? x : (~(x - 1));
}
const int maxn = (int)1e5 + 5;
std :: vector <int> G[maxn];
int deg[maxn], dis[maxn];
int main() {
int n = read(), k = n - read();
std :: queue <int> q;
for (int i = 1; i < n; ++i) {
int u = read(), v = read();
G[u].push_back(v);
G[v].push_back(u);
++deg[u];
++deg[v];
}
for (int u = 1; u <= n; ++u) {
if (deg[u] == 1) {
q.push(u);
dis[u] = 1;
}
}
int ans = 0;
while (!q.empty() && k) {
int u = q.front();
q.pop();
ans = dis[u];
--k;
for (int v : G[u]) {
--deg[v];
if (deg[v] == 1) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
printf("%d\n", ans);
return 0;
}
标签:选择,ch,P5536,中心,int,核心,叶子,read,XR
From: https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p5536.html