POJ 3107

时间:2021-04-01 10:10:55
 #include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#define MAXN 50010
using namespace std;
typedef struct PP{
int id,par;
bool operator < (const PP & a) const{
if(par == a.par) return id < a.id;
return par < a.par;
}
}Partition;
typedef struct{
int to,next;
}Node;
Node edge[*MAXN];
Partition P[MAXN];
int head[MAXN],vis[MAXN],cnt[MAXN],N;
void addedge(int u,int v,int k){
edge[k].to = v;
edge[k].next = head[u];
head[u] = k;
}
int dfs_child(int s){
vis[s] = cnt[s] = ;
for(int i = head[s];~i;i = edge[i].next){
int u = edge[i].to;
if(!vis[u]) cnt[s] += dfs_child(u);
}
return cnt[s]--;
}
void dfs_partition(int s){
P[s].id = s;
P[s].par = N-cnt[s]-;
vis[s] = ;
for(int i = head[s];~i;i = edge[i].next){
int u = edge[i].to;
if(!vis[u]){
P[s].par = max(P[s].par,cnt[u]+);
dfs_partition(u);
}
}
}
int main(){
int u,v;
while(~scanf("%d",&N)){
int k = ;
memset(head,-,sizeof(head));
for(int i = ;i <= N-;i ++){
scanf("%d%d",&u,&v);
addedge(u,v,k++);
addedge(v,u,k++);
}
memset(vis,,sizeof(vis));
dfs_child();
memset(vis,,sizeof(vis));
dfs_partition();
sort(P+,P+N+);
k = ;
while(P[k].par == P[].par){
printf("%d ",P[k].id);
k++;
}
printf("\n");
}
return ;
}