本文主要是介绍树的重心（dfs），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
[Acwing 846.树的重心]
给定一颗树，树中包含 n n n 个结点（编号 1 ∼ n 1∼n 1∼n）和 n − 1 n−1 n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
输入格式
第一行包含整数 n n n，表示树的结点数。
接下来 n − 1 n−1 n−1 行，每行包含两个整数 a a a 和 b b b，表示点 a a a 和点 b b b 之间存在一条边。
输出格式
输出一个整数 m m m，表示将重心删除后，剩余各个连通块中点数的最大值。
数据范围
1 ≤ n ≤ 105 1≤n≤105 1≤n≤105
输入样例
9
1 2
1 7
1 4
2 8
2 5
4 3
3 9
4 6
输出样例：
4
代码
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;const int N=1e5+10;
int n,ans=N;
bool vis[N];
int h[N],e[2*N],ne[2*N],idx;
/*使用邻接表建图，h存储头节点e存储元素值，ne指向next节点地址idx为链表长度*/void add(int a,int b){e[++idx]=b;ne[idx]=h[a];h[a]=idx;
}int dfs(int u){int res=0;//记录u的最大子树的节点数vis[u]=true;int sum=1;//以u为根的子树的节点数for(int i=h[u];i!=-1;i=ne[i]){int j=e[i];if(!vis[j]){int s=dfs(j);res=max(res,s);sum+=s;}}res=max(res,n-sum);ans=min(res,ans);//u节点上方的节点数return sum;
}int main() {memset(h,-1,sizeof h);cin>>n;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;
}这篇关于树的重心（dfs）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
