poj3107树的重心

/*
树的重心求法:两次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("");
}
}
上一篇:EasyExcel导入工具(SpringMVC下使用)


下一篇:POJ3107 树的重心