题目描述 Description
有一个村庄居住着n个村民，有n-1条路径使得这n个村民的家联通，每条路径的长度都为1。现在村长希望在某个村民家中召开一场会议，村长希望所有村民到会议地点的距离之和最小，那么村长应该要把会议地点设置在哪个村民的家中，并且这个距离总和最小是多少？若有多个节点都满足条件，则选择节点编号最小的那个点。
输入描述 Input Description
第一行。一个数n，表示有n个村民。
接下来n-1行，每行两个数字a和b，表示村民a的家和村民b的家之间存在一条路径。
输出描述 Output Description
一行输出两个数字x和y
x表示村长将会在哪个村民家中举办会议
y表示距离之和的最小值
样例输入 Sample Input
4
1 2
2 3
3 4
样例输出 Sample Output
2 4
数据范围及提示 Data Size & Hint
70%数据n<=1000
100%数据n<=50000
思路：
求树的重心，然后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; }