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