【题目来源】
【问题描述】
给定一颗树，树中包含 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
【算法分析】
● 链式前向星：
● 邻接表存“树”：
【算法代码一：链式前向星】
#include <bits/stdc++.h>
using namespace std;const int N=1e5+10;
const int M=N<<1;
int h[N],e[M],ne[M],idx;
bool st[N];
int imax=INT_MAX;
int n;void add(int a,int b) {e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}int dfs(int u) {st[u]=true;int cnt=1;int rem=0; //remnantfor(int i=h[u]; i!=-1; i=ne[i]) {int j=e[i];if(!st[j]) {int t=dfs(j);rem=max(rem,t);cnt+=t;}}rem=max(rem,n-cnt);imax=min(imax,rem);return cnt;
}int main() {cin>>n;memset(h,-1,sizeof(h));for(int i=1; i<n; i++) {int a,b;cin>>a>>b;add(a,b),add(b,a);}dfs(1);cout<<imax<<endl;return 0;
}/*
in:
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6out:
4
*/
【算法代码二：邻接表】
#include<bits/stdc++.h>
using namespace std;const int N=1e5+5;
vector<int> G[N];
bool st[N];
int imax=INT_MAX;
int n;int dfs(int u) {st[u]=true;int cnt=1;int rem=0; //remnantfor(auto i:G[u]) {if(!st[i]) {int t=dfs(i);rem=max(rem,t);cnt+=t;}}rem=max(rem,n-cnt);imax=min(rem,imax);return cnt;
}int main() {cin>>n;int x,y;for(int i=1; i<n; i++) {cin>>x>>y;G[x].push_back(y);G[y].push_back(x);}dfs(1);cout<<imax<<endl;return 0;
}/*
in:
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6out:
4
*/ 【算法代码三：链式前向星】
此代码与“东方博宜OJ 2190：树的重心”代码的差别，仅在于最后一部分的循环内容不同。
详见：
#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 10out:
5
*/
【参考文献】