Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
物是人非~#include<map> #include<vector> #include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; #define N 55555 #define INF 0x3f3f3f3f struct node { int to,next; }Edge[N<<1]; int head[N],n,cnt,num[N],ans,Min; int vec[N],Size; void add(int w,int v) { Edge[cnt].to=v; Edge[cnt].next=head[w]; head[w]=cnt++; Edge[cnt].to=w; Edge[cnt].next=head[v]; head[v]=cnt++; } void Tree_DP(int w,int fa) { int i,j,k,tot=0,Max=-1; for(i=head[w];~i;i=Edge[i].next) { int v=Edge[i].to; if(v==fa)continue; //printf("%d %d \n",w,v); Tree_DP(v,w); num[w]+=num[v]; } } void dfs(int w,int fa) { // printf("w=====%d %d",w,fa); int i,j,k,tot=0,Max=-1; for(i=head[w];~i;i=Edge[i].next) { int v=Edge[i].to;//printf("w==%d %d \n",w,v); if(v==fa)continue; dfs(v,w); Max=max(Max,num[v]); tot+=num[v]; } Max=max(Max,n-1-tot); if(Max<Min) { Min=Max; Size=0; vec[Size++]=w; } else if(Max==Min) vec[Size++]=w; // vec.push_back(w); } int main() { int m,j,i,k,l; while(~scanf("%d",&n)) { Size=0; memset(head,-1,sizeof(head)); cnt=0; for(i=1;i<n;i++) scanf("%d%d",&j,&k),add(j,k),num[i]=1; num[n]=1; Min=INF; Tree_DP(1,0); dfs(1,0); sort(vec,vec+Size); for(i=0;i<Size;i++) { printf("%d",vec[i]); if(i!=Size-1) printf(" "); else printf("\n"); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator