比赛 20241022 评测结果 AAAAAAAAAAAAAAAAAAAA
题目名称 猴猴吃苹果 最终得分 100
用户昵称 wdsjl 运行时间 0.250 s
代码语言 C++ 内存使用 4.26 MiB
提交时间 2024-10-22 09:21:49
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

const int N = 5e4+10;

struct node{
	int to,ne;
}e[N*4];

int tot,h[N];

void add(int u,int v){
	e[tot]={v,h[u]};
	h[u]=tot++;
} 

int n,re,son[N],dep[N],mx[N],f[N],stk[N],tp,p[N],dis[N];

void dfs1(int x,int fa){
//	dep[x]=dep[fa]+1,mx[x]=dep[x],f[x]=fa;
//	cout<<x<<" "<<fa<<endl;
	mx[x]=1;
	for(int i=h[x];~i;i=e[i].ne){
		int v=e[i].to;
		if(v==fa)continue;
		dfs1(v,x);
		if(mx[v]>mx[son[x]]||(mx[v]==mx[son[x]]&&p[v]<p[son[x]])){
			mx[x]=mx[v];
			son[x]=v; 
		}
	}
	if(!son[x]){
		stk[++tp]=x;
		p[x]=x;
	}else p[x]=p[son[x]];
	mx[x]=mx[son[x]]+1;
}

void dfs2(int x,int sp,int fa){
	if(!son[x]){
		dis[x]=sp;
		return ;
	}else dfs2(son[x],sp+1,x);
	for(int i=h[x];~i;i=e[i].ne){
		int y=e[i].to;
		if(y==fa||y==son[x])continue;
		dfs2(y,1,x); 
	}
}

bool cmp(int a,int b){
    if(dis[a]==dis[b])return a<b;
    return dis[a]>dis[b];
}

int main(){
	freopen("apple.in","r",stdin);
	freopen("apple.out","w",stdout);
	memset(h,-1,sizeof(h));
	scanf("%d%d",&n,&re);
	re++;
	for(int i=2;i<=n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a++;
		b++;
		add(a,b);
		add(b,a); 
	}
////	cout<<"___________"<<endl;
//	for(int i=1;i<=n;i++){
//		for(int j=h[i];~j;j=e[j].ne){
//			cout<<e[j].to<<" ";
//		}
//		cout<<endl;
//	}
//	cout<<"RR";
	dfs1(re,0);
//	cout<<"RR";
	dfs2(re,1,0);
//	cout<<"RR";
	sort(stk+1,stk+1+tp,cmp);
	printf("%d\n",re-1);
	for(int i=1;i<=tp;i++){
		printf("%d\n",stk[i]-1);
	}
	return 0;
}