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