#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
template<class T>bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<class T>bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
vector<int> to[200005],sc[200005];
int fc[200005];
int fa[200005];
int p[200005],c;
bool check(int x){
	p[c=0]=x;
	for(int i=0;i<=c;++i)for(auto j:to[p[i]])p[++c]=j;
	sort(p+1,p+c+1);
	do{
		bool ok=1;
		for(int i=1;i<=c;++i){
			int f=0;
			for(int j=1;j<i;++j)if(fc[p[j]]==fc[p[i]])++f;
			if(p[f]!=fa[p[i]])ok=0;
		}
		if(ok)return 1;
	}while(next_permutation(p+1,p+c+1));
	return 0;
}
int ok[200005];
int d[200005];
bool subset(const vector<int> &a,const vector<int> &b){
	auto it=b.begin();
	for(auto i:a){
		while(it!=b.end() && *it!=i)++it;
		if(it==b.end())return 0;
	}
	return 1;
}
void dfs(int x){
	ok[x]=1;
	sort(sc[x].begin(),sc[x].end());
	for(auto i:to[x]){
		dfs(i);
		chkmax(d[x],d[i]+1);
		if(!ok[i])ok[x]=0;
	}
	if(d[x]>=2)ok[x]=0;
	sc[x].erase(unique(sc[x].begin(),sc[x].end()),sc[x].end());
	if(sc[x].size()!=to[x].size())ok[x]=0;
	if(!to[x].size())return;
	if(ok[x]){
		sort(to[x].begin(),to[x].end(),[](int x,int y){return sc[x].size()<sc[y].size();});
		for(int i=1;i<to[x].size();++i)if(!subset(sc[to[x][i-1]],sc[to[x][i]]))ok[x]=0;
		if(!subset(sc[to[x].back()],sc[x]))ok[x]=0;
	}
}
std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> C)
{
	for(int i=1;i<n;++i){
		fa[i]=P[i];
		to[P[i]].emplace_back(i);
		sc[P[i]].emplace_back(C[i]);
		fc[i]=C[i];
	}
	vector<int> ans(n);
	if(n<=8){
		for(int i=0;i<n;++i)ans[i]=check(i);
		return ans;
	}
	else{
		bool chain=1;
		for(int i=1;i<n;++i)if(fa[i]!=i-1){
			chain=0;
		}
		if(chain){
			bool ok=1;
			for(int i=n-1;~i;--i){
				ans[i]=ok;
				if(fc[i]!=fc[n-1])ok=0;
			}
			return ans;
		}
		else{
			dfs(0);
			return vector<int>(ok,ok+n);
		}
	}
}