P12195 [NOISG 2025 Prelim] Itinerary

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int n,m;
const int N=2e5+5;
int f[N][25],dep[N];
vector<int>vc[N];
int a[2*N];
map<int,int>cnt;
int p=1;
int vis[N];
map<pair<int,int>,int>mp; //存u-v边走的次数 
pair<int,int> pr(int u,int v){
	return make_pair(max(u,v),min(u,v));
}
void dfs1(int u,int fa){//倍增板子 
	dep[u]=dep[fa]+1;
	f[u][0]=fa;
	for(int i=1;i<=21;i++){
		f[u][i]=f[f[u][i-1]][i-1];
	}
	for(int v:vc[u]){
		if(v==fa)continue;
		dfs1(v,u);
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y])swap(x,y);
	for(int i=19;i>=0;i--){
		if(dep[f[x][i]]>=dep[y])x=f[x][i];
	}
	if(x==y)return x;
	for(int i=21;i>=0;i--){
		if(f[x][i]!=f[y][i]){
			x=f[x][i];
			y=f[y][i];
		}
	}
	return f[x][0];
}
int gs(int x,int y){//x跳到y走向x方向的儿子 
	if(dep[x]<dep[y])swap(x,y);
	for(int i=21;i>=0;i--){
		if(dep[f[x][i]]>dep[y])x=f[x][i];
	}
	return x;
}
void dfs2(int u,int fa){
	while(p<=m){
		if(u==a[p])p++;
		if(p>m)return;
		int l=lca(u,a[p]);
		if(l==u){//目标在x子树内，向下dfs
			int s=gs(a[p],u);//找出正确的儿子 
			mp[pr(u,s)]++;//从u走到s 
			if(mp[pr(u,s)]>=3){//判断路径是否超过2次 
				for(int i=1;i<=n;i++){//不然会T，下同 
					cout<<0<<'\n';
				}
				exit(0);
			}
			dfs2(s,u);
			if(p>m)return;
		}
		else{
			mp[pr(u,fa)]++;//目标不在x子树内，向上dfs
			if(mp[pr(u,fa)]>=3){//下同 
				for(int i=1;i<=n;i++){
					cout<<0<<'\n';
				}
				exit(0);
			}
			return;
		}
	}
	mp[pr(u,fa)]++;
	if(mp[pr(u,fa)]>=3){
		for(int i=1;i<=n;i++){
			cout<<0<<'\n';
		}
		exit(0);
	}
}
void dfs3(int u,int fa){
	vis[u]=1;
	for(int v:vc[u]){//边数<2的可以再走一遍 
		if(v==fa||(mp.count(pr(u,v))&&mp[pr(u,v)]>=2))continue;
		dfs3(v,u);
	}
}
signed main(){
	ios::sync_with_stdio(0);cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		vc[u].pb(v);
		vc[v].pb(u);
	}
	for(int i=1;i<=m;i++){
		cin>>a[i];
	}
	dfs1(a[1],0);
	dfs2(a[1],0);
	dfs3(a[1],0);
	for(int i=1;i<=n;i++){
		cout<<vis[i]<<'\n';
	}
	return 0;
}