比赛 |
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;
}