比赛 |
20241022 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
猴猴吃苹果 |
最终得分 |
100 |
用户昵称 |
flyfree |
运行时间 |
0.740 s |
代码语言 |
C++ |
内存使用 |
6.91 MiB |
提交时间 |
2024-10-22 11:05:11 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 50010
inline ll read(){
ll x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
struct node{
ll l,r,tag;
ll maxz,id;
}tr[MAXN*4];
ll n,k,idx,cnt,siz;
ll ans[MAXN],used[MAXN];
ll hd[MAXN],ed[MAXN*2],nxt[MAXN*2];
ll dep[MAXN],fa[MAXN],len[MAXN],son[MAXN],son_id[MAXN];
ll dfn[MAXN],lst[MAXN],re_dfn[MAXN];
void push_up(ll now){
// tr[now].maxz=max(tr[now*2].maxz,tr[now*2+1].maxz);
if(tr[now*2].maxz>tr[now*2+1].maxz)tr[now].maxz=tr[now*2].maxz,tr[now].id=tr[now*2].id;
else if(tr[now*2+1].maxz>tr[now*2].maxz)tr[now].maxz=tr[now*2+1].maxz,tr[now].id=tr[now*2+1].id;
else tr[now].maxz=tr[now*2].maxz,tr[now].id=min(tr[now*2].id,tr[now*2+1].id);
}
void push_down(ll now){
ll tag=tr[now].tag;
tr[now*2].maxz+=tag;
tr[now*2+1].maxz+=tag;
tr[now*2+1].tag+=tag;
tr[now*2].tag+=tag;
tr[now].tag=0;
}
void tr_build(ll now,ll l,ll r){
tr[now].l=l,tr[now].r=r;
if(l==r){
tr[now].maxz=dep[re_dfn[l]];
tr[now].id=re_dfn[l];
return;
}
ll mid=(l+r)/2;
tr_build(now*2,l,mid);
tr_build(now*2+1,mid+1,r);
push_up(now);
}
void ad_(ll now,ll l,ll r,ll val){
if(tr[now].l>=l&&tr[now].r<=r){
tr[now].maxz+=val;
tr[now].tag+=val;
// cout<<now<<" "<<tr[now].l<<" "<<tr[now].r<<" "<<tr[now].maxz<<" "<<tr[now].id<<endl;
return;
}
push_down(now);
ll mid=(tr[now].l+tr[now].r)/2;
if(l<=mid)ad_(now*2,l,r,val);
if(r>mid)ad_(now*2+1,l,r,val);
push_up(now);
// cout<<now<<" "<<tr[now].l<<" "<<tr[now].r<<" "<<tr[now].maxz<<" "<<tr[now].id<<endl;
}
//pair <ll,ll> re_(ll now,ll l,ll r){// first-最大值,second-最大值下标
// if(tr[now].l>=l&&tr[now].r<=r){
// if(tr[now].maxz)return make_pair<tr[now].maxz,tr[now].id>
// else return make_pair<0,-1>
// }
// push_down(now);
// ll mid=(tr[now].l+tr[now].r)/2;
// if(l<=mid){
// if(r>mid){
// pair <ll,ll> a=re_(now*2,l,r),b=re_(now*2+1,l,r);
// if(a.first>b.first)return a;
// else if(b.first>a.first)return b;
// else if(b.second>a.second)return a;
// else return b;
// }else return re_(now*2,l,r);
// }else return re_(now*2+1,l,r);
//}
void build(ll x,ll y){
nxt[++idx]=hd[x];
ed[idx]=y;
hd[x]=idx;
}
void dfs1(ll now,ll f){
fa[now]=f,dep[now]=dep[f]+1,son_id[now]=now;
for(int i=hd[now];i;i=nxt[i]){
ll y=ed[i];
if(y==f)continue;
dfs1(y,now);
if(len[y]>len[son[now]]||(len[y]==len[son[now]]&&son_id[y]<son_id[now])){
len[now]=len[y];
son[now]=y;
son_id[now]=son_id[y];
}
}
len[now]++;
}
void dfs2(ll now){
lst[now]=dfn[now]=++cnt,re_dfn[cnt]=now;
if(!son[now])return;
dfs2(son[now]);
lst[now]=max(lst[now],lst[son[now]]);
for(int i=hd[now];i;i=nxt[i]){
ll y=ed[i];
if(y==fa[now]||y==son[now])continue;
dfs2(y);
lst[now]=max(lst[now],lst[y]);
}
}
void dfs_ad(ll now){
if(used[now])return;
// cout<<now<<endl;
ad_(1,dfn[now],lst[now],-1);
used[now]=1;
dfs_ad(fa[now]);
}
int main(){
freopen("apple.in","r",stdin);
freopen("apple.out","w",stdout);
n=read(),k=read();
for(int i=1;i<n;i++){
ll x=read(),y=read();
build(x,y);
build(y,x);
}
dep[0]=-1;
dfs1(k,0);
dfs2(k);
tr_build(1,1,n);
used[k]=1;
// for(int i=1;i<=n;i++)cout<<dfn[i]<<" ";
// cout<<endl;
while(1){
ll now=tr[1].id,p=tr[1].maxz;
// if(now!=7||p!=1)cout<<now<<" "<<p<<endl;
if(!p)break;
ans[++siz]=now;
dfs_ad(now);
}
cout<<k<<endl;
for(int i=1;i<=siz;i++)cout<<ans[i]<<endl;
return 0;
}