/*
树的重心求法:两次dfs,第一次dfs处理出每个结点的size,以此求每个结点大儿子的size,第二次dfs将每个结点大儿子的size和余下结点数进行比较,所有结点里两个值之间差值最小的那个点就是重心
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 50005
struct Edge{int to,nxt;}edge[maxn<<];
int Max,head[maxn],tot,n,size[maxn],maxv[maxn];
vector<int>vec;
void init(){
memset(maxv,,sizeof maxv);
memset(head,-,sizeof head);
tot=;Max=;
}
void addedge(int u,int v){
edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++;
}
void dfssize(int u,int pre){
size[u]=;maxv[u]=;
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(v==pre)continue;
dfssize(v,u);
size[u]+=size[v];
if(size[v]>maxv[u])maxv[u]=size[v];
}
}
void dfsroot(int u,int pre){
if(n-size[u]>maxv[u])
maxv[u]=n-size[u];
if(maxv[u]<Max)
Max=maxv[u];
for(int i=head[u];i!=-;i=edge[i].nxt){
int v=edge[i].to;
if(v!=pre)dfsroot(v,u);
}
}
int main(){
while(scanf("%d",&n)!=EOF){
init();
for(int i=;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
addedge(u,v);
addedge(v,u);
}
dfssize(,);//一次dfs求所有节点size
dfsroot(,);
for(int i=;i<=n;i++)if(maxv[i]==Max)printf("%d ",i);
puts("");
}
}

最新文章

  1. yii2 使用composer安装
  2. mysql查询所有表行数
  3. Html-Css-设置DIV边框圆滑
  4. Fresco 源码分析(三) Fresco服务端处理(1) ImagePipeline为何物
  5. 详解android.mk-2016.01.18
  6. C语言学习--可变数组
  7. BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊(动态树)
  8. 【Android界面实现】信息更新小红点显示——自己定义控件BadgeView的使用介绍
  9. PHP函数积累
  10. 第一章 flume架构介绍
  11. leetCode没那么难啦 in Java (二)
  12. JS生成当前月份包括最近12个月内的月份
  13. win8 notepad++ 设置无法保存
  14. noiac64 sort (二分答案)
  15. Codeforces Round #419 (Div. 2) ABC
  16. Flex外包公司——案例汇总
  17. visual studio 2013的使用和单元测试
  18. 【openstack N版】——网络服务neutron(flat扁平网络)
  19. 当堆遇到STL 代码焕发光芒
  20. VI 你不知道的事

热门文章

  1. Spring的常用工具类
  2. 关于vue2.0 cnpm 镜像安装
  3. Jedis(java操作redis数据库技术)
  4. yum upgrade卡在 清理initial-setup-0.3.9.30-1.el7.centos.x86_64
  5. [转] 解决Driver/library version mismatch
  6. 【SVN】关于钩子的一些使用
  7. 正则表达式、BeautifulSoup、Lxml进行性能对比
  8. 判断HDFS文件是否存在
  9. workqueue --最清晰的讲解
  10. 修改主机IP地址