定义：
如果在树中删去某个结点v后，得到的图中每个连通分量的大小均不超过原树结点数的一半，就称这个结点v
为整棵树的重心(centroid).
性质：
1.树中所有结点到某个结点的距离和中，到结点v的距离和最小。
2.把两棵树通过一条边相连，新的树的重心在原来两棵树重心的连线上。
3.一棵树添加或者删除一个节点，树的重心最多只移动一条边的位置。
4.一棵树最多有两个重心，且相邻。
解决方法：
找到一个点作为根时，其所有的子树中最大的子树节点数最少。跑一边dfs就行了。
点击查看代码
int n;
int zs[106];//zs[i]表示以i为根其向下子树节点个数 (包括根)
int dp[106];//dp[i]表示删掉i时最大联通分量的大小 int mn=0x7fffffff;
int ans;
void find(int u,int fa)
{//先看向下子树：zs[i]=1;//包含自己for(int i=head[u];i;i=s[i].next)//链式前向星 {int e=s[i].to;if(e!=fa)//单向边时需要写 防止成环 { find(e,u);zs[u]+=zs[e];dp[u]=max(dp[u],zs[e]);}}//上面： dp[u]=max(dp[u],n-zs[u]);//求重心： if(mn>dp[u]){mn=dp[u];ans=u;}
}
例题：
洛谷P1364 医院设置
题意：
在一棵带点权的二叉树中找到树的重心并求出每个点到重心的距离*点权。
点击查看代码
#include<bits/stdc++.h>////点权影响重心位置，要求有权重心
using namespace std;inline void read(register int &a)
{a=0;register char c;while((c=getchar())<48);do a=(a<<3)+(a<<1)+(c^48);while((c=getchar())>47);
}int n;//100
int v[106];//10^5
int h;//100*10^5
int l,r;//100
int zs[106];//100 zs[i]表示以i为根其向下子树节点个数 (包括根 )
int dp[106];//100 dp[i]表示删掉i时最大联通分量的大小 int cnt;//99
int head[106];//99
struct node{int start;//100int to;//100int next;//99
}s[206];
void add(int x,int y)
{++cnt;s[cnt].start=x;s[cnt].to=y;s[cnt].next=head[x];head[x]=cnt;}int mn=0x7fffffff;//100*10^5
int ans;//100
void find(int u,int fa)
{for(int i=head[u];i;i=s[i].next){int e=s[i].to;if(e!=fa)//单向边时需要写 防止成环 {find(e,u);zs[u]+=zs[e];dp[u]=max(dp[u],zs[e]);}}dp[u]=max(dp[u],h-zs[u]);
// cout<<u<<":"<<dp[u]<<"!\n";//if(mn>dp[u]){mn=dp[u];ans=u;}
}int jl[106];//100 每个点到重心的距离
int q[106];//100
bool bj[106];
long long bfs(int u)
{long long sum=0;//5050*10^5=5*10^8int t=1,w=1;//100q[1]=u;bj[u]=1;while(t<=w){// cout<<q[t]<<":";//for(int i=head[q[t]];i;i=s[i].next){int e=s[i].to;if(!bj[e]){bj[e]=1;jl[e]=jl[q[t]]+1;sum+=jl[e]*v[e];// cout<<e<<":"<<jl[e]<<"*"<<v[e]<<"\n";// q[++w]=e; }}++t;}return sum;
}int main()
{read(n);for(int i=1;i<=n;i++){read(v[i]);read(l);read(r);zs[i]=v[i];h+=v[i];if(l) add(i,l),add(l,i);if(r) add(i,r),add(r,i);}find(1,0);cout<<bfs(ans);return 0;
}
/*
50
1 2 3
4 0 0
87 4 5
21 0 0
28 6 7
68 0 0
32 8 9
17 0 0
38 10 11
43 0 0
9 12 13
48 0 0
8 14 15
85 0 0
6 16 17
30 0 0
92 18 19
37 0 0
78 20 21
33 0 0
70 22 23
85 0 0
72 24 25
31 0 0
17 26 27
33 0 0
47 28 29
25 0 0
83 30 31
28 0 0
49 32 33
15 0 0
88 34 35
29 0 0
78 36 37
98 0 0
50 38 39
89 0 0
83 40 41
3 0 0
15 42 43
15 0 0
51 44 45
3 0 0
60 46 47
1 0 0
78 48 49
66 0 0
78 50 0
71 0 0out:14522
*/