Link

https://www.luogu.org/problemnew/show/P1395

Description

  there are n villagers living in a village, and there are n-1 paths to connect the homes of these n villagers. The length of each path is 1. Now the village head wants to hold a meeting in a certain villager's home. The village head wants the sum of the distances from all the villagers to the meeting place to be the smallest. Then the village head should set the meeting place in which villager's home, and what is the minimum sum of the distances? If more than one node meets the condition, select the point with the lowest node number.

Solution

The barycenter of a   tree has the following properties:

• The sum of distances from all points in the tree to a certain point and to the center of gravity is the smallest. If there are two distances and, their distances are the same.
• Connect the two trees by one side, and the center of gravity of the new tree is on the line of the original two trees.
• When a tree adds or removes a node, the center of gravity of the tree can only move one edge at most.
• A tree has at most two centers of gravity and is adjacent to each other.

So this is a template problem for finding the center of gravity of trees.

Code

#include<iostream>
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
#define maxn 50090


struct edge{
    int u,v,next; 
}e[2*maxn];

int head[maxn],cnt;
void add(int x,int y){
    e[cnt].u=x,e[cnt].v=y;
    e[cnt].next=head[x];
    head[x]=cnt++;
    e[cnt].u=y,e[cnt].v=x;
    e[cnt].next=head[y];
    head[y]=cnt++;
}

int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}



int res,n,m,root,sz[maxn],level[maxn];

void getroot(int x,int fa){
    sz[x]=1;
    int maxsz=-1;
    for(int i=head[x];i!=-1;i=e[i].next){
        int v=e[i].v;
        if(fa==v||sz[v])continue;
        getroot(v,x);
        sz[x]+=sz[v];
        maxsz=max(sz[v],maxsz);
    }
    maxsz=max(maxsz,n-sz[x]);
    if(res>maxsz)res=maxsz,root=x;
    else if(res==maxsz)root=min(root,x);
}

void bfs(int x){
    queue<int>q;
    q.push(x);
    res=0;
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i!=-1;i=e[i].next){
            int v=e[i].v;
            if(level[v]||v==x)continue;
            level[v]=level[u]+1;
            res+=level[v];
            q.push(v);
        }
    }
}
int main(){
    cin>>n;
    int a,b;
    memset(head,-1,sizeof(head));
    for(int i=0;i<n-1;i++){
        a=read(),b=read();
        add(a,b);
    }
    res=n;
    getroot(1,0);
    bfs(root);
    cout<<root<<" "<<res<<endl;
}

We insist on one thing not because it will work, but because we firmly believe that it is right to do so.
——Javier