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<<1]; int Max,head[maxn],tot,n,size[maxn],maxv[maxn]; vector<int>vec; void init(){ memset(maxv,0,sizeof maxv); memset(head,-1,sizeof head); tot=0;Max=99999999; } 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]=1;maxv[u]=0; for(int i=head[u];i!=-1;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!=-1;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=1;i<n;i++){ int u,v; scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } dfssize(1,0);//一次dfs求所有节点size dfsroot(1,0); for(int i=1;i<=n;i++)if(maxv[i]==Max)printf("%d ",i); puts(""); } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10343895.html