题目描述
有一个村庄居住着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
又是一道树形dp，我最近树形dp是不是写的太多了QAQ
用up and down 做两次dfs，第一次求出每一个点的子树大小size[]和它子树上的每一个点到这个点的距离之和ste[]。
作完第一步以后，可以发现这时每个点到根节点的距离之和已经处理完了。用这一性质从上到下更新每一个非根节点，可以算出到k节点开会的总步数stp[k]=stp[father[k]]+size[1]-2*size[k]
#include<iostream>
#include<stdio.h> using namespace std; int i,m,n,g,h,k,a[1000001],head[1000001],ver[10000001],nex[1000001],cnt,size[100001],ste[1000001],ans=0x7ffffff,p,deep[1000001],stp[1000001]; void add(int x,int y)
{
cnt+=1;
ver[cnt]=y;
nex[cnt]=head[x];
head[x]=cnt;
} void dfs1(int x,int f)
{
size[x]=1;
for(int i=head[x];i;i=nex[i])
{
int t=ver[i];
if(t==f) continue;
deep[t]=deep[x]+1;
dfs1(t,x);
ste[x]+=ste[t]+size[t];
size[x]+=size[t];
}
} void dfs2(int x,int f)
{
for(int i=head[x];i;i=nex[i])
{
int t=ver[i];
if(t==f) continue;
stp[t]=stp[x]+size[1]-2*size[t];
if(stp[t]==ans) p=min(p,t);
if(stp[t]<ans) ans=stp[t],p=t;
dfs2(t,x);
}
} int main()
{
scanf("%d",&n);
for(i=1;i<n;i++)
{
scanf("%d%d",&g,&h);
add(g,h);
add(h,g);
}
dfs1(1,0);
stp[1]=ans=ste[1]; p=1;
dfs2(1,0);
printf("%d %d",p,ans);
}