1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 #define mt(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 const int M=50010; 8 vector<int> g[M]; 9 int dp[M],num[M],n;10 void dfs(int u,int fa){11     dp[u]=0;12     num[u]=1;13     int len=g[u].size();14     for(int i=0;i<len;i++){15         int v=g[u][i];16         if(v!=fa){17             dfs(v,u);18             num[u]+=num[v];19             dp[u]=max(dp[u],num[v]);20         }21     }22     dp[u]=max(dp[u],n-num[u]);23 }24 int main(){25     int t;26     while(~scanf("%d",&t)){27         while(t--){28             scanf("%d",&n);29             for(int i=1;i<=n;i++) g[i].clear();30             for(int i=0,u,v;i<n-1;i++){31                 scanf("%d%d",&u,&v);32                 g[u].push_back(v);33                 g[v].push_back(u);34             }35             dfs(1,-1);36             int sma=n;37             for(int i=1;i<=n;i++){38                 sma=min(sma,dp[i]);39             }40             for(int i=1;i<=n;i++){41                 if(dp[i]==sma){42                     printf("%d %d\n",i,dp[i]);43                     break;44                 }45             }46         }47     }48     return 0;49 }

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<vector> 5 #define mt(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 const int M=50010; 8 struct G{ 9     struct E{10         int u,v,next;11     }e[M<<1];12     int le,head[M];13     void init(){14         le=0;15         mt(head,-1);16     }17     void add(int u,int v){18         e[le].u=u;19         e[le].v=v;20         e[le].next=head[u];21         head[u]=le++;22     }23 }g;24 int dp[M],num[M],n;25 void dfs(int u,int fa){26     dp[u]=0;27     num[u]=1;28     for(int i=g.head[u];~i;i=g.e[i].next){29         int v=g.e[i].v;30         if(v!=fa){31             dfs(v,u);32             num[u]+=num[v];33             dp[u]=max(dp[u],num[v]);34         }35     }36     dp[u]=max(dp[u],n-num[u]);37 }38 int main(){39     int t;40     while(~scanf("%d",&t)){41         while(t--){42             scanf("%d",&n);43             g.init();44             for(int i=0,u,v;i<n-1;i++){45                 scanf("%d%d",&u,&v);46                 g.add(u,v);47                 g.add(v,u);48             }49             dfs(1,-1);50             int sma=n;51             for(int i=1;i<=n;i++){52                 sma=min(sma,dp[i]);53             }54             for(int i=1;i<=n;i++){55                 if(dp[i]==sma){56                     printf("%d %d\n",i,dp[i]);57                     break;58                 }59             }60         }61     }62     return 0;63 }

 1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int M=50010; 7 struct G{ 8     struct E{ 9         int u,v,next;10     }e[M<<1];11     int le,head[M];12     void init(){13         le=0;14         mt(head,-1);15     }16     void add(int u,int v){17         e[le].u=u;18         e[le].v=v;19         e[le].next=head[u];20         head[u]=le++;21     }22 }g;23 int dp[M],num[M],n;24 void dfs(int u,int fa){25     dp[u]=0;26     num[u]=1;27     for(int i=g.head[u];~i;i=g.e[i].next){28         int v=g.e[i].v;29         if(v!=fa){30             dfs(v,u);31             num[u]+=num[v];32             dp[u]=max(dp[u],num[v]);33         }34     }35     dp[u]=max(dp[u],n-num[u]);36 }37 int main(){38     while(~scanf("%d",&n)){39         g.init();40         for(int i=0,u,v;i<n-1;i++){41             scanf("%d%d",&u,&v);42             g.add(u,v);43             g.add(v,u);44         }45         dfs(1,-1);46         int sma=n;47         for(int i=1;i<=n;i++){48             sma=min(sma,dp[i]);49         }50         for(int i=1;i<=n;i++){51             if(dp[i]==sma){52                 printf("%d ",i);53             }54         }55         puts("");56     }57     return 0;58 }