当前位置：首页 > news >正文

AcWing 846：树的重心 ← 类似“东方博宜OJ 2190：树的重心”代码

news 2026/6/10 16:50:03

【题目来源】
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 10out:
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/