#include"beechtree.h"
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
#define N 200000
#define TM 2000
#define SM 2000
using namespace std;
int n,length,cl[N+1],fa[N+1],tong[N+1],cnt[N+1],cnts[N+1],num[N+1];
vector<int>E[N+1];
bool used[TM+1][TM+1];
bitset<SM+1>B[TM+1];
bitset<SM+1>B2[TM+1];
void dfs(int x)
{
	tong[++length]=x;
	for (int i=0;i<E[x].size();++i) dfs(E[x][i]);
	return;
}
bool cmp(int x,int y)
{
	return E[x].size()>E[y].size();
}
void adder(int x,int y)
{
	used[x][y]=B[x][y]=B2[y][x]=1;
	bitset<SM+1>res;
	bitset<SM+1>rst;
	int ps;
	while (1)
	{
		rst=B[x],rst.flip(),res=B[y]&rst,ps=res._Find_first();
		if (ps!=res.size()) adder(x,ps);
		else break;
	}
	while (1)
	{
		rst=B2[y],rst.flip(),res=B2[x]&rst,ps=res._Find_first();
		if (ps!=res.size()) adder(ps,y);
		else break;
	}
	if (fa[x]&&fa[y]&&cl[tong[x]]==cl[tong[y]]&&!used[fa[x]][fa[y]]) adder(fa[x],fa[y]);
	return;
}
vector<int>beechtree(int SN,int M,vector<int>P,vector<int>C)
{
	bool op=1,opt,opst=0;
	vector<int>p(SN);
	n=SN;
	for (int i=0;i<M;++i) cnt[i]=0;
    for (int i=1;i<n;++i) op&=(P[i]==i-1),E[P[i]].push_back(i),cl[i]=C[i],cnts[cl[i]]++;
	if (op)
	{
		opt=1;
		for (int i=n-1;i>=0;--i)
		{
			if (i<=n-3) opt&=(cl[i+1]==cl[i+2]);
		    p[i]=opt;
		}
		return p;
	}
	op=1;
	for (int i=1;i<n;++i) op&=(fa[i]==0||fa[fa[i]]==0);
	if (op)
	{
		for (int i=n-1;i>=0;--i)
		{
			if (!i)
			{
				opt=1,tong[++length]=i;
				for (int j=0;j<M;++j) cnt[j]=0;
				for (int j=0;j<E[i].size();++j) opt&=p[E[i][j]],tong[++length]=E[i][j],cnt[cl[E[i][j]]]++;
				for (int j=0;j<M;++j)
					for (int k=1;k<=cnt[j];++k)
					{
						op=0;
						for (int t=0;t<E[tong[k]].size();++t) op|=(C[E[tong[k]][t]]==j);
						opt&=op;
					}
				p[i]=opt;
			}
			else
			{
				opt=0;
				for (int j=0;j<E[i].size();++j) opt|=(cnt[cl[E[i][j]]]>0),cnt[cl[E[i][j]]]++;
				p[i]=opt;
				for (int j=0;j<E[i].size();++j) cnt[cl[E[i][j]]]--;
			}
		}
		return p;
	}
	op=1;
	for (int i=0;i<M;++i) op&=(cnts[i]<=2);
	if (op)
	{
		for (int i=n-1;i>=0;--i)
		{
			op=0;
			for (int j=0;j<E[i].size();++j) op|=(!E[E[i][j]].empty());
			if (op&&!opst)
			{
				opt=1,tong[++length]=i;
				for (int j=0;j<M;++j) cnt[j]=0;
				for (int j=0;j<E[i].size();++j) opt&=p[E[i][j]],tong[++length]=E[i][j],cnt[cl[E[i][j]]]++;
				for (int j=0;j<M;++j)
					for (int k=1;k<=cnt[j];++k)
					{
						op=0;
						for (int t=0;t<E[tong[k]].size();++t) op|=(C[E[tong[k]][t]]==j);
						opt&=op;
					}
				p[i]=opt,opst=1;
			}
			else
			{
				opt=0;
				for (int j=0;j<E[i].size();++j) opt|=(cnt[cl[E[i][j]]]>0),cnt[cl[E[i][j]]]++;
				p[i]=opt;
				for (int j=0;j<E[i].size();++j) cnt[cl[E[i][j]]]--;
			}
		}
		return p;
	}
	for (int i=0;i<n;++i)
	{
		length=0,dfs(i),sort(tong+1,tong+length+1,cmp);
		for (int j=0;j<M;++j) cnt[j]=0;
		for (int j=1;j<=length;++j)
			if (tong[j]!=i)
				cnt[cl[tong[j]]]++;
		opt=1;
		for (int j=0;j<M;++j)
			for (int k=1;k<=cnt[j];++k)
			{
				op=0;
				for (int t=0;t<E[tong[k]].size();++t) op|=(C[E[tong[k]][t]]==j);
				opt&=op;
			}
		if (opt)
		{
			for (int j=1;j<=length;++j)
			{
				B[j].reset(),B2[j].reset();
				for (int k=1;k<=length;++k) used[j][k]=0;
			}
			for (int j=1;j<=length;++j) num[tong[j]]=j;
			for (int j=1;j<=length;++j)
			{
				if (tong[j]!=i) fa[j]=num[P[tong[j]]];
				else fa[j]=0;
			}
			for (int j=1;j<=length;++j)
				if (tong[j]!=i&&!used[fa[j]][j])
					adder(fa[j],j);
			for (int j=1;j<=length;++j)
				for (int k=j+1;k<=length;++k)
					if (E[tong[j]].size()>E[tong[k]].size()&&!used[j][k])
						adder(j,k);
			for (int j=1;j<=length;++j)
				if (used[j][j])
					opt=0;
			if (opt) p[i]=1;
		}
	}
	return p;
}