poj3107树的重心
2024-10-13 12:16:09
/*
树的重心求法:两次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("");
}
}
最新文章
- yii2 使用composer安装
- mysql查询所有表行数
- Html-Css-设置DIV边框圆滑
- Fresco 源码分析(三) Fresco服务端处理(1) ImagePipeline为何物
- 详解android.mk-2016.01.18
- C语言学习--可变数组
- BZOJ 2002 [Hnoi2010]Bounce 弹飞绵羊(动态树)
- 【Android界面实现】信息更新小红点显示——自己定义控件BadgeView的使用介绍
- PHP函数积累
- 第一章 flume架构介绍
- leetCode没那么难啦 in Java (二)
- JS生成当前月份包括最近12个月内的月份
- win8 notepad++ 设置无法保存
- noiac64 sort (二分答案)
- Codeforces Round #419 (Div. 2) ABC
- Flex外包公司——案例汇总
- visual studio 2013的使用和单元测试
- 【openstack N版】——网络服务neutron(flat扁平网络)
- 当堆遇到STL 代码焕发光芒
- VI 你不知道的事
热门文章
- Spring的常用工具类
- 关于vue2.0 cnpm 镜像安装
- Jedis(java操作redis数据库技术)
- yum upgrade卡在 清理initial-setup-0.3.9.30-1.el7.centos.x86_64
- [转] 解决Driver/library version mismatch
- 【SVN】关于钩子的一些使用
- 正则表达式、BeautifulSoup、Lxml进行性能对比
- 判断HDFS文件是否存在
- workqueue --最清晰的讲解
- 修改主机IP地址