AcWing 846. 树的重心
原题链接
简单
作者:
跟着灿哥学切菜
,
2021-01-17 14:26:50
,
所有人可见
,
阅读 268
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = N * 2;
int h[N], e[M], ne[M], idx;
bool st[N];
int ans = N; // 此时存储的就是最小的最大值
int n;
void add(int a, int b) {
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx ++;
}
int dfs(int u) { //以u为根的子树中的节点个数
st[u] = true; //表示此时的u这个顶点已经被搜索了
//对于每一个点, 首先来记录以这个点为根节点的子树的大小
int sum = 1, res = 0; //此时res 表示的是将这个节点删除之后, 此时连通块中的最大值
for (int i = h[u]; i != -1; i = ne[i]) {
int j = e[i];
if (!st[j]) {
int s = dfs(j); //使用s来表示当前的这个子树的大小
//当前的这个子树也是连通块的一部分
res = max(res, s);
sum += s;
}
}
res = max(res, n - sum);
ans = min(ans, res);
return sum;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n; i ++) {
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}