【图论】树的重心

 树的重心

删去这一点后每一块中点数最为平均

统计以u为根的子树点数个数（加上一个本身，从哪里来的），这里点都是一样的

s846. 树的重心 - AcWing题库

#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int n;
int ans=INF;
 
struct EDGE{
int next;
int to;
 
}edge[200001];
int tot=0;
int head[100001];
void addedge(int u,int v){
edge[++tot].next=head[u];
edge[tot].to=v;
head[u]=tot;
}
 
 
int dfs(int u,int father){
int mzishuu=0;
int sumu=1;
 
for(int i=head[u];~i;i=edge[i].next){
    int v=edge[i].to;
    if(v==father)continue;
 
    int temp=dfs(v,u);
    mzishuu=max(mzishuu,temp);
    sumu+=temp;
}
//上面还没有算呢
mzishuu=max(mzishuu,n-sumu);
 
 
 
ans=min(ans,mzishuu);
return sumu;
}
 
int main(){
 
cin>>n;
for(int i=1;i<=n;i++)head[i]=-1;
 
for(int i=1;i<=n-1;i++){
    int u,v;
    cin>>u>>v;
    addedge(u,v);
    addedge(v,u);
}
 
dfs(1,0);
cout<<ans;
 
}