Question

(图论)给定一棵树,找到一个点，使得与其他节点距离总和最小值

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

Answer 1

有图么？、 没图的话。。。。。。。。。额

追问

补充个样例 样例的图就是一条直线1——2——3——4 这样的
【输入格式】
第一行。一个数n，表示有n个村民。
接下来n-1行，每行两个数字a和b，表示村民a的家和村民b的家之间存在一条路径。
【输出格式】
一行输出两个数字x和y
x表示村长将会在哪个村民家中举办会议
y表示距离之和的最小值
【样例输入】
4
1 2
2 3
3 4
【样例输出】
2 4

追答

你上的什么学。。。。完全看不懂

追问

这属于信息竞赛，看不懂就算了

Answer 2

思路：树的重心，然后dfs求每个点到ans的距离。
#include<cstdio>
#include<algorithm>
#define maxn 50001
using namespace std;
int deep[maxn],tot,n,ans,head[maxn],s[maxn],size=(1<<30);
bool vis[maxn];
struct node
{
int to,next;
}a[maxn*2];
void add(int x,int y)
{
tot++;
a[tot].to=y;
a[tot].next=head[x];
head[x]=tot;
}
void dfs(int x)
{
vis[x]=1;
s[x]=0;
int tmp=0;
for(int i=head[x];i;i=a[i].next)
{
int y=a[i].to;
if(!vis[y])
{
dfs(y);
s[x]+=s[y]+1;
tmp=max(tmp,s[y]+1);
}
}
tmp=max(tmp,n-s[x]-1);
if(tmp<size||tmp==size&&x<ans)
{
ans=x;
size=tmp;
}
}
void dfs1(int x,int y,int d)
{
deep[x]=d;
for(int i=head[x];i;i=a[i].next)
if(y!=a[i].to)
dfs1(a[i].to,x,d+1);
}
int main()
{
int i,j,x,y;
scanf("%d",&n);
for(i=1;i<n;i++)
scanf("%d%d",&x,&y),add(x,y),add(y,x);
dfs(1);
dfs1(ans,ans,0);
int sum=0;
for(i=1;i<=n;i++)
sum=sum+abs(deep[i]-deep[ans]);
printf("%d %d",ans,sum);
return 0;
}

Answer 3

网上自行搜索克鲁斯卡尔算法或者普利姆算法即可