【题目来源】
https://www.acwing.com/problem/content/848/
【问题描述】
给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
【输入格式】
第一行包含整数 n，表示树的结点数。
接下来 n−1 行，每行包含两个整数 a 和 b，表示点 a 和点 b 之间存在一条边。
【输出格式】
输出一个整数 m，表示将重心删除后，剩余各个连通块中点数的最大值。
【数据范围】
1≤n≤10^5
【输入样例】
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
【输出样例】
4
【算法分析】
● 链式前向星：https://blog.csdn.net/hnjzsyjyj/article/details/139369904
【算法代码：链式前向星】
本文代码与“东方博宜OJ 2190：树的重心”代码的差别，仅在于最后一部分的循环内容不同。
详见：https://blog.csdn.net/hnjzsyjyj/article/details/155821553
#include <bits/stdc++.h> using namespace std; const int N=1e5+5; const int M=N<<1; int h[N],e[M],ne[M],idx; int pre[N],cnt[N]; int rem[N]; //remnant int n; void add(int a,int b) { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } int dfs(int u,int fa) { cnt[u]=1; pre[u]=fa; for(int i=h[u]; i!=-1; i=ne[i]) { int j=e[i]; if(j!=fa) cnt[u]+=dfs(j,u); } return cnt[u]; } int main() { memset(h,-1,sizeof h); cin>>n; for(int i=1; i<n; i++) { int a,b; cin>>a>>b; add(a,b),add(b,a); } dfs(1,-1); int imin=INT_MAX; for(int u=1; u<=n; u++) { rem[u]=n-cnt[u]; for(int i=h[u]; i!=-1; i=ne[i]) { int j=e[i]; if(pre[j]==u) { rem[u]=max(rem[u],cnt[j]); } } imin=min(imin,rem[u]); } int imax=INT_MIN; for(int u=1; u<=n; u++) { if(imin==rem[u]) { int t=0; for(int i=h[u]; i!=-1; i=ne[i]) { int j=e[i]; if(pre[j]==u) { t=max(t,cnt[j]); } } t=max(t,n-cnt[u]); imax=max(imax,t); } } cout<<imax<<endl; return 0; } /* in: 10 1 2 1 3 4 2 4 5 3 6 7 6 8 6 9 6 7 10 out: 5 */
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/155821553
https://www.acwing.com/solution/content/287387/
https://blog.csdn.net/hnjzsyjyj/article/details/139369904
https://blog.csdn.net/hnjzsyjyj/article/details/108655516
https://blog.csdn.net/qq_47783057/article/details/116195481
https://www.acwing.com/solution/content/13513/
https://www.acwing.com/solution/content/4917/
