会议dfs树

会议

题目描述

有一个村庄居住着 n 个村民，有 n-1 条路径使得这 n 个村民的家联通，每条路径的长度都为 1。
现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？
若有多个节点都满足条件，则选择节点编号最小的那个点。

输入格式

第一行，一个数 n，表示有 n 个村民。
接下来 n-1 行，每行两个数字 a 和 b，表示村民 a 的家和村民 b 的家之间存在一条路径。

输出格式

一行输出两个数字 x 和 y。
x 表示村长将会在哪个村民家中举办会议。
y 表示距离之和的最小值。

样例输入1

4
1 2
2 3
3 4

样例输出1

2 4

注释说明

对于70%数据，n<=1000
对于100%数据，n<=50000

#include <bits/stdc++.h>
using namespace std;
vector<int>a[50002];
int f[50002],sum[50002],n,ans=INT_MAX,num;
void dfs(int x){
f[x]=1;
for(int i=0;i<a[x].size();i++){
int to=a[x][i];
dfs(to);
f[x]+=f[to];
sum[x]+=sum[to];
}
sum[x]+=f[x]-1;
}
void dfs2(int x){

if(ans>sum[x]){
ans=sum[x];
num=x;
}
for(int i=0;i<a[x].size();i++){
int to=a[x][i];
sum[to]=sum[x]+n-2*f[to];//printf("%d %d %d\n",x,to,sum[to]);
dfs2(to);
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
if(u>v)swap(u,v);
a[u].push_back(v);
}
dfs(1);
//for(int i=1;i<=n;i++){
//printf("%d ",sum[i]);
//}
dfs2(1);
printf("%d %d",num,ans);
}
/*

4
1 2
2 3
3 4
*/

原文地址：https://blog.csdn.net/no_play_no_games/article/details/142438604

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！