树的重心
定义
树的重心定义为树的某个节点，当去掉该节点后，树的各个连通分量中，节点数最多的连通分量其节点数达到最小值。树可能存在多个重心。
性质
2.树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等。
3.两个树通过一条边合并，新的重心在原树的两个重心的路径上
4.树删除或者添加一个叶子节点，重心最多只移动一条边
5.一棵树最多有两个重心，且相邻
求树的重心
#include<iostream> #include<vector> #include<algorithm> using namespace std; const int N = 1e5+10; vector<int>vec[N]; int vis[N]; int n; int ans = 0x3f3f3f3f; int dfs(int now){ vis[now] = 1; int sum = 1, res = 0; for(int i = 0;i<vec[now].size();++i){ if(!vis[vec[now][i]]){ int s = dfs(vec[now][i]); //以 now 的子节点为根的子树的大小 res = max(res,s); // 连通分量最大值 sum += s; //sum == 以 now 为根的所有子树中的节点数量 } } res = max(n - sum,res); //以 now 的父亲节点为根且不包含 now 的子树的的大小 也即将 now 删除后 另一半子树的大小 ans = min(ans,res); //连通分量最大值的最小值 即重心 return sum; } int main(){ //建树 cin >> n ; for(int i = 0;i<n-1;++i){ int u,v; cin >> u >> v; vec[u].push_back(v); vec[v].push_back(u); } dfs(1); cout << ans << endl; }
