#include"beechtree.h"
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
#define N 200000
#define SM 2000
using namespace std;
struct reads
{
	int x,y;
};
int n,t,length,dfn[N+1],sz[N+1],rt[N+1],cnt[N+1],l[N+1],cl[N+1],fa[N+1],tong[N+1];
vector<int>E[N+1];
vector<reads>v[N+1];
vector<reads>st[N+1];
bool used[SM+1][SM+1],vis[SM+1];
bitset<SM+1>B[SM+1];
bitset<SM+1>B2[SM+1];
void dfs(int x)
{
	tong[++length]=x;
	for (int i=0;i<E[x].size();++i) dfs(E[x][i]);
	return;
}
void dfs2(int x)
{
	tong[++length]=x,dfn[x]=length,sz[x]=1;
	for (int i=0;i<E[x].size();++i) dfs2(E[x][i]),sz[x]+=sz[E[x][i]];
	return;
}
bool LENG(int x,int y)
{
	return dfn[x]<=dfn[y]&&dfn[y]<=dfn[x]+sz[x]-1;
}
bool cmp(int x,int y)
{
	return E[x].size()>E[y].size();
}
int find(int x)
{
	if (rt[x]==x) return x;
	return rt[x]=find(rt[x]);
}
void unionn(int x,int y)
{
	rt[x]=y;
	return;
}
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]!=-1&&fa[y]!=-1&&cl[x]==cl[y]&&!used[fa[x]][fa[y]])
	{
		if (min(dfn[fa[x]],dfn[fa[y]])>=t) adder(fa[x],fa[y]); 
		else v[min(dfn[fa[x]],dfn[fa[y]])].push_back((reads){fa[x],fa[y]});
	}
	return;
}
void dfs3(int x,int y)
{
	if (LENG(x,y)) l[x]=x;
	if (x<y) st[l[x]].push_back((reads){x,y});
	for (int i=0;i<E[x].size();++i) l[E[x][i]]=l[x],dfs3(E[x][i],y);
	return;
}
vector<int>beechtree(int SN,int M,vector<int>P,vector<int>C)
{
	bool op=1,opt;
	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],fa[i]=P[i];
	for (int i=0;i<n;++i) rt[i]=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;
	}
	for (int i=0;i<n;++i)
	{
		length=0,dfs(i),sort(tong+1,tong+length+1,cmp);
		for (int j=1;j<=M;++j) cnt[j]=0;
		for (int j=1;j<=length;++j)
			if (tong[j]!=i)
				cnt[cl[tong[j]]]++,opt&=(E[fa[tong[j]]].size()>=E[tong[j]].size());
		opt=1;
		for (int j=1;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;
	}
	length=0,dfs2(0);
	for (int i=0;i<n;++i) dfs3(0,i);
	for (int i=n;i>=1;--i)
	{
		if (tong[i]) unionn(tong[i],fa[tong[i]]);
		t=i;
		for (int j=0;j<E[tong[i]].size();++j)
			if (!used[tong[i]][E[tong[i]][j]])
				adder(tong[i],E[tong[i]][j]);
		for (int j=0;j<st[tong[i]].size();++j)
		{
			if (E[st[tong[i]][j].x].size()<E[st[tong[i]][j].y].size()&&!used[st[tong[i]][j].y][st[tong[i]][j].x]) adder(st[tong[i]][j].y,st[tong[i]][j].x);
			if (E[st[tong[i]][j].x].size()>E[st[tong[i]][j].y].size()&&!used[st[tong[i]][j].x][st[tong[i]][j].y]) adder(st[tong[i]][j].x,st[tong[i]][j].y);
		}
		for (int j=0;j<v[i].size();++j)
			if (!used[v[i][j].x][v[i][j].y])
				adder(v[i][j].x,v[i][j].y);
		p[tong[i]]&=(!used[tong[i]][tong[i]]);
	}
	for (int i=length;i>=1;--i)
		for (int j=0;j<E[tong[i]].size();++j)
			p[tong[i]]&=p[E[tong[i]][j]];
	return p;
}