AcWing 846. 树的重心
原题链接
简单
树的重心
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10, M = 2 * N;
int n;
// 领接表
int h[N], e[M], ne[M], idx;
int ans = N;
bool visit[N];
// 在顶点a上添加一条到顶点b的边
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int dfs(int s) {
// 标记顶点s已经访问过
visit[s] = true;
// 连通块的大小
int size = 0;
// 以顶点s为根节点的子树的节点个数
int sum = 0;
// 遍历邻接表
for (int i = h[s]; i != -1; i = ne[i]) {
int j = e[i];
// 如果顶点j没有被访问过
if (!visit[j]) {
// 访问顶点j,并记录以顶点j为根节点的子树的节点个数
int num = dfs(j);
// j的父节点i,以i为根节点的子树的节点个数+num
sum += num;
// 更新删去i后,最大连通块的大小(此时的更新,并没有把上面的一部分连通块加入比较)
size = max(size, num);
}
}
// 更新删去i后,最大连通块的大小
size = max(size, n - (sum + 1));
// 更新结果
ans = min(ans, size);
return sum + 1;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
for (int i = 0; i < n - 1; i++) {
int a, b;
cin >> a >> b;
add(a, b), add(b, a);
}
dfs(1);
cout << ans << endl;
return 0;
}