P1395 【会议】

· · 题解

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;
}