题目描述

有一个村庄居住着n个村民，有n-1条路径使得这n个村民的家联通，每条路径的长度都为1。

现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。

原题链接

Solve

1.每个村民的家都为一个节点，所有的边权值为1，而且这是一个树。

2.找到树的重心。

3.以树的重心为源点，求出其与各个节点的距离和（使用BFS）。

Tips

1.什么是树的重心？

链接Blog较为详细地描述了树的重心的概念。

2.为什么会议地点就是树的重心？

这是树的重心的性质运用。

Code

#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;  //标准开头
const int N=50010;  //节点数
int n,ans;  //n——节点数，ans为树的重心
int maxn=10000000;
int u,r,sum;  //u，r边的两端点，sum——距离之和
int d[N],dis[N];  //dis[i]为节点i到源点（树的重心）的距离
vector<int> G[N];  //vector建图
queue<int> q;  //BFS必备队列
bool vis[N];  //BFS中已经遍历的点
void dfs(int s,int f){  //求树的重心
    d[s]=1;
    int res=0;
    for(int i=0;i<G[s].size();i++){
        if(G[s][i]==f) continue;
        dfs(G[s][i],s);
        d[s]+=d[G[s][i]];
        res=max(res,d[G[s][i]]);
    }
    res=max(res,n-d[s]);
    if(res<maxn||(res==maxn&&ans>s)){
        maxn=res;
        ans=s;
    }
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n-1;i++){
        scanf("%d%d",&u,&r);
        G[u].push_back(r);
        G[r].push_back(u);
    }
    dfs(1,0);
    q.push(ans);
    while(!q.empty()){  //标准BFS
        int e=q.front();
        q.pop();
        vis[e]=true;
        sum+=dis[e];
        for(int i=0;i<G[e].size();i++){
            if(!vis[G[e][i]]){
                q.push(G[e][i]);
                dis[G[e][i]]=dis[e]+1;
            }
        }
    }
    printf("%d %d",ans,sum);  //完美输出
    return 0;
}