Submission #698693

#	Time	Username	Problem	Language	Result	Execution time	Memory
698693		moonrabbit2	Pastiri (COI20_pastiri)	C++17	100 / 100	754 ms	133376 KiB

pastiri

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
const int N=5e5+5,inf=1e8;
int n,k;
vector<int> G[N],g[N];
int par[N];
bool in[N];
int sub[N],up[N],sz[N],best[N][2],dp[N][2][2];
vector<int> ans;
void dfs1(int u){
	sub[u]=inf;
	if(in[u]){
		sub[u]=0;
		sz[u]=1;
	}
	for(int v: G[u]) if(v!=par[u]){
		par[v]=u;
		g[u].emplace_back(v);
		dfs1(v);
		sub[u]=min(sub[u],sub[v]+1);
		sz[u]+=sz[v];
	}
}
void dfs2(int u){
	up[u]=min(up[u],inf);
	if(in[u]) up[u]=0;
	if(!g[u].size()) return;
	best[u][0]=g[u][0];
	for(int v: g[u]) if(sub[v]<sub[best[u][0]]) best[u][0]=v;
	best[u][1]=-1;
	for(int v: g[u]) if(v!=best[u][0]&&(best[u][1]==-1||sub[v]<sub[best[u][1]])) best[u][1]=v;
	for(int v: g[u]){
		if(v!=best[u][0]) up[v]=min(up[u]+1,sub[best[u][0]]+2);
		else{
			up[v]=up[u]+1;
			if(best[u][1]!=-1) up[v]=min(up[v],sub[best[u][1]]+2);
		}
		dfs2(v);
	}
}
void dfs3(int u){
	dp[u][0][0]=dp[u][0][1]=dp[u][1][0]=dp[u][1][1]=inf;
	for(int v: g[u]) dfs3(v);
	if(in[u]){
		int s=0;
		for(int v: g[u]) s+=dp[v][1][0];
		dp[u][0][0]=s;
		dp[u][1][0]=s+1;
		for(int v: g[u]) dp[u][1][0]=min(dp[u][1][0],s+dp[v][1][1]-dp[v][1][0]);
	} else{
		if(sub[u]==inf){
			dp[u][1][0]=0;
			dp[u][1][1]=1;
		} else{
			if(sub[u]==up[u]){
				{
					int s=0;
					for(int v: g[u]) s+=dp[v][1][0];
					dp[u][1][0]=min(dp[u][1][0],s);
				}
				{
					int s=0;
					for(int v: g[u]){
						if(sub[u]==sub[v]+1) s+=dp[v][0][0];
						else s+=dp[v][1][0];
					}
					dp[u][1][1]=min(dp[u][1][1],s+1);
					for(int v: g[u]) if(sub[u]!=sub[v]+1) dp[u][1][1]=min(dp[u][1][1],s-dp[v][1][0]+dp[v][1][1]);
				}
			} else if(sub[u]>up[u]){
				{
					int s=0;
					for(int v: g[u]) s+=dp[v][1][0];
					dp[u][1][0]=min(dp[u][1][0],s);
					dp[u][1][1]=min(dp[u][1][1],s+1);
					for(int v: g[u]) dp[u][1][1]=min(dp[u][1][1],s-dp[v][1][0]+dp[v][1][1]);
				}
			} else{
				{
					int s=0;
					for(int v: g[u]) s+=dp[v][1][0];
					dp[u][1][0]=min(dp[u][1][0],s);
				}
				{
					int s=0;
					for(int v: g[u]){
						if(sub[u]==sub[v]+1) s+=dp[v][0][0];
						else s+=dp[v][1][0];
					}
					if(sub[u]+1<=up[u]-1) dp[u][0][0]=min(dp[u][0][0],s);
					dp[u][1][0]=min(dp[u][1][0],s+1);
					for(int v: g[u]) if(sub[u]!=sub[v]+1) dp[u][1][0]=min(dp[u][1][0],s-dp[v][1][0]+dp[v][1][1]);
				}
			}
		}
	}
	dp[u][1][0]=min(dp[u][1][0],dp[u][1][1]);
	dp[u][0][1]=min(dp[u][0][1],dp[u][1][1]);
	dp[u][0][0]=min({dp[u][0][0],dp[u][0][1],dp[u][1][0]});
	if(sz[u]==k){
		dp[u][1][1]=min(dp[u][1][1],dp[u][1][0]);
		dp[u][0][1]=min(dp[u][0][1],dp[u][0][0]);
	}
}
void track(int u,int x,int y){
	if(!dp[u][x][y]) return;
	if(in[u]){
		int s=0;
		for(int v: g[u]) s+=dp[v][1][0];
		if(x==0&&y==0&&dp[u][x][y]==s){
			for(int v: g[u]) track(v,1,0);
			return;
		}
		if(x==1&&y==0&&dp[u][x][y]==s+1){
			ans.emplace_back(u);
			for(int v: g[u]) track(v,1,0);
			return;
		}
		for(int v: g[u]){
			if(x==1&&y==0&&dp[u][x][y]==s+dp[v][1][1]-dp[v][1][0]){
				for(int w: g[u]) if(v!=w) track(w,1,0);
				track(v,1,1);
				return;
			}
		}
	} else{
		if(sub[u]==inf){
			if(x==1&&y==0&&dp[u][x][y]==0) return;
			if(x==1&&y==1&&dp[u][x][y]==1){
				ans.emplace_back(u);
				return;
			}
		} else{
			if(sub[u]==up[u]){
				{
					int s=0;
					for(int v: g[u]) s+=dp[v][1][0];
					if(x==1&&y==0&&dp[u][x][y]==s){
						for(int v: g[u]) track(v,1,0);
						return;
					}
				}
				{
					int s=0;
					for(int v: g[u]){
						if(sub[u]==sub[v]+1) s+=dp[v][0][0];
						else s+=dp[v][1][0];
					}
					if(x==1&&y==1&&dp[u][x][y]==s+1){
						ans.emplace_back(u);
						for(int v: g[u]){
							if(sub[u]==sub[v]+1) track(v,0,0);
							else track(v,1,0);
						}
						return;
					}
					for(int v: g[u]) if(sub[u]!=sub[v]+1){
						if(x==1&&y==1&&dp[u][x][y]==s-dp[v][1][0]+dp[v][1][1]){
							for(int w: g[u]) if(v!=w){
								if(sub[u]==sub[w]+1) track(w,0,0);
								else track(w,1,0);
							}
							track(v,1,1);
							return;
						}
					}
				}
			} else if(sub[u]>up[u]){
				{
					int s=0;
					for(int v: g[u]) s+=dp[v][1][0];
					if(x==1&&y==0&&dp[u][x][y]==s){
						for(int v: g[u]) track(v,1,0);
						return;
					}
					if(x==1&&y==1&&dp[u][x][y]==s+1){
						ans.emplace_back(u);
						for(int v: g[u]) track(v,1,0);
						return;
					}
					for(int v: g[u]){
						if(x==1&&y==1&&dp[u][x][y]==s-dp[v][1][0]+dp[v][1][1]){
							for(int w: g[u]) if(v!=w) track(w,1,0);
							track(v,1,1);
							return;
						}
					}
				}
			} else{
				{
					int s=0;
					for(int v: g[u]) s+=dp[v][1][0];
					if(x==1&&y==0&&dp[u][x][y]==s){
						for(int v: g[u]) track(v,1,0);
						return;
					}
				}
				{
					int s=0;
					for(int v: g[u]){
						if(sub[u]==sub[v]+1) s+=dp[v][0][0];
						else s+=dp[v][1][0];
					}
					if(sub[u]+1<=up[u]-1){
						if(x==0&&y==0&&dp[u][x][y]==s){
							for(int v: g[u]){
								if(sub[u]==sub[v]+1) track(v,0,0);
								else track(v,1,0);
							}
							return;
						}
					}
					if(x==1&&y==0&&dp[u][x][y]==s+1){
						ans.emplace_back(u);
						for(int v: g[u]){
							if(sub[u]==sub[v]+1) track(v,0,0);
							else track(v,1,0);
						}
						return;
					}
					for(int v: g[u]) if(sub[u]!=sub[v]+1){
						if(x==1&&y==0&&dp[u][x][y]==s-dp[v][1][0]+dp[v][1][1]){
							for(int w: g[u]) if(v!=w){
								if(sub[u]==sub[w]+1) track(w,0,0);
								else track(w,1,0);
							}
							track(v,1,1);
							return;
						}
					}
				}
			}
		}
	}
	if(x==1&&y==0&&dp[u][x][y]==dp[u][1][1]){
		track(u,1,1);
		return;
	}
	if(x==0&&y==1&&dp[u][x][y]==dp[u][1][1]){
		track(u,1,1);
		return;
	}
	if(x==0&&y==0&&dp[u][x][y]==dp[u][0][1]){
		track(u,0,1);
		return;
	}
	if(x==0&&y==0&&dp[u][x][y]==dp[u][1][0]){
		track(u,1,0);
		return;
	}
	if(sz[u]==k){
		if(x==1&&y==1&&dp[u][x][y]==dp[u][1][0]){
			track(u,1,0);
			return;
		}
		if(x==0&&y==1&&dp[u][x][y]==dp[u][0][0]){
			track(u,0,0);
			return;
		}
	}
	assert(0);
}
int main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k;
	for(int u,v,i=1;i<n;i++){
		cin>>u>>v;
		G[u].emplace_back(v);
		G[v].emplace_back(u);
	}
	for(int u,i=1;i<=k;i++){
		cin>>u;
		in[u]=true;
	}
	dfs1(1);
	up[1]=inf;
	dfs2(1);
	dfs3(1);
	cout<<dp[1][1][1]<<"\n";
	track(1,1,1);
	for(int u: ans) cout<<u<<" ";
	return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 18 / 18
• Subtask 3: 23 / 23
• Subtask 4: 51 / 51