DFS
在博主看来,本题最大的难点在于,搞懂dfs() 函数返回的究竟是什么?
是「返回以u为根的子树的结点总数」,还是直接「返回以u为重心的连通的最大值」?
显然,在y总的讲解中,答案是前者。
所以在做题时,可以先不用管其他的条件,就先写出「返回以u为根的子树的结点总数」的dfs()函数。
其框架如下:
// 求以u为根的子树结点总数
int dfs(int u) {
int sum = 1; // sum为返回值,初始值为1(即u结点)
st[u] = true; // 将当前结点标记为已访问
// 将u的每棵子树结点总数相加,就是以u为根的子树结点总数
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!st[j]) {
int s = dfs(j); // u的其中一颗子树结点总数
sum += s; // 累加
}
}
cout << "以" << u << "为根的子树共有" << sum << "个结点" << endl;
return sum;
}
在会写了上面的这个功能后,我们再按照题意进行扩展,就比较容易了。
题目中要求连通块(子树)的结点数最大值,那我们就在循环里添加一个比较最大值的变量,存储子树结点的最大值即可。
题目中要求重心是最大值的最小值,只要添加一个比较最小值全局变量,在函数的最后进行比较即可。
此题使用了标记数组,除了最上面的顶点(视角从上往下),中间结点不会回溯上方已被标记的子树。这个在完成dfs函数本身任务时,是完全正确的。但是由于本题需要求解的是连通块,即中间结点上方的连通块也要进行考虑,但是如果把上方的连通块,也算入中间节点子树的大小,就会使dfs()的含义发生变化,这是不行的。
所以本题用了一种很妙的方式,即使用通过 n - sum 这种方法来求解中间结点的上方的子树,又不会影响dfs()
本身返回值的大小,一举两得。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10,M = N * 2;
int e[M], ne[M], h[N], idx;
int n, a, b;
bool st[N];
int ans = N;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
// 返回以u为根的子树的结点总数
int dfs(int u) {
int sum = 1;
st[u] = true;
int res = 0; // res表示当前子树的最大值
for (int i = h[u]; ~i; i = ne[i]) {
int j = e[i];
if (!st[j]) {
int s = dfs(j); // 当前子树大小
sum += s;
res = max(res, s);
}
}
// 除了最上面的顶点,中间结点不会回溯已被标记的子树,所以通过此题的特殊性质求解。
res = max(n - sum, res);
// ans 是所有子树最大值的最小值
ans = min(res, ans);
return sum;
}
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 邻接表表头的初始化
memset(h, -1, sizeof(h));
// 加边
cin >> n;
for (int i = 1; i <= n - 1; ++i) {
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}