P1395 【会议】

## Solve 1.每个村民的家都为一个节点，所有的边权值为1，而且这是一个树。 2.找到[树的重心](https://five-shifts-forever.blog.luogu.org/shu-di-zhong-xin)。 3.以树的重心为源点，求出其与各个节点的距离和（使用BFS）。 ## Tips 1.什么是树的重心？ 链接Blog~~较为详细地~~描述了树的重心的概念。 2.为什么会议地点就是树的重心？  这是树的重心的性质运用。 ## Code ```cpp #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; } ```