#include"beechtree.h"
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<bitset>
#include<queue>
#include<random>
#define N 200000
#define Base1 131
#define Base2 171
#define mod1 998244353
#define mod2 998244853
using namespace std;
mt19937 RAND(0);
struct reads
{
	int x,y;
};
struct rds
{
	int hsh1,hsh2;
	bool operator == (const rds &t)const
	{
		return hsh1==t.hsh1&&hsh2==t.hsh2;	
	}
};
rds hsh[N+1],pw[N+1],rd[N+1],rd2[N+1],dp[N+1],zero;
int MD1(int x)
{
	return x>=mod1?x-mod1:x;
}
int MD2(int x)
{
	return x>=mod2?x-mod2:x;
}
int MD3(int x)
{
	return x<0?x+mod1:x;
}
int MD4(int x)
{
	return x<0?x+mod2:x;
}
rds operator + (rds a,rds b)
{
	return (rds){MD1(a.hsh1+b.hsh1),MD2(a.hsh2+b.hsh2)};
}
rds operator - (rds a,rds b)
{
	return (rds){MD3(a.hsh1-b.hsh1),MD4(a.hsh2-b.hsh2)};
}
rds operator * (rds a,rds b)
{
	return (rds){1ll*a.hsh1*b.hsh1%mod1,1ll*a.hsh2*b.hsh2%mod2};
}
rds F(int l,int r)
{
	return hsh[r]-hsh[l-1]*pw[r-l+1];
}
int n,cnt[N+1],num[N+1],leng,cater,rt[N+1],rt2[N+1],st[N+1],hs[N+1],delta[N+1],cl[N+1],sp[N+1],rk[N+1],rks[N+1],fa[N+1],dfn[N+1],sz[N+1],lg[N+1],nums[N+1];
vector<int>E[N+1];
struct nde
{
	int num,data;
	bool operator < (const nde &t)const
	{
		int l1=dfn[num],r1=dfn[num]+sz[num]-1,l2=dfn[t.num],r2=dfn[t.num]+sz[t.num]-1,d=0;
		for (int i=lg[min(r1-l1+1,r2-l2+1)];i>=0;--i)
			if (d+(1<<i)<=min(r1-l1+1,r2-l2+1)&&F(l1,l1+d+(1<<i)-1)==F(l2,l2+d+(1<<i)-1))
				d+=(1<<i);
		if (d==r1-l1+1)
		{
			if (r1-l1!=r2-l2) return r1-l1<r2-l2;
			else return data>t.data;
		}
		else return delta[l1+d]<delta[l2+d];
	}
};
priority_queue<nde>q;
struct points
{
	int x,y,num;
	bool operator < (const points &t)const
	{
		return x!=t.x?x<t.x:y<t.y;
	}
};
points ds[N+1];
bool cmp(int x,int y)
{
	return cl[x]<cl[y];
}
bool cmp2(int x,int y)
{
	return rks[x]<rks[y];
}
void dfs(int x)
{
	dfn[x]=++leng,sz[x]=1,st[leng]=x;
	for (int i=0;i<E[x].size();++i) dfs(E[x][i]),sz[x]+=sz[E[x][i]];
	return;
}
struct seg
{
	struct node
	{
		int ls,rs,cl,cr,sz;
		rds data,res;
	};
	node tree[60*N+1];
	int length;
	void push_up(int k)
	{
		if (!tree[k].rs) tree[k].cl=tree[tree[k].ls].cl,tree[k].cr=tree[tree[k].ls].cr,tree[k].sz=tree[tree[k].ls].sz,tree[k].data=tree[tree[k].ls].data,tree[k].res=tree[tree[k].ls].res;
		else if (!tree[k].ls) tree[k].cl=tree[tree[k].rs].cl,tree[k].cr=tree[tree[k].rs].cr,tree[k].sz=tree[tree[k].rs].sz,tree[k].data=tree[tree[k].rs].data,tree[k].res=tree[tree[k].rs].res;
		else
		{
			tree[k].cl=tree[tree[k].ls].cl,tree[k].cr=tree[tree[k].rs].cr;
			if (tree[tree[k].ls].cr==tree[tree[k].rs].cr) tree[k].sz=tree[tree[k].ls].sz+tree[tree[k].rs].sz;
			else tree[k].sz=tree[tree[k].rs].sz;
			if (tree[tree[k].ls].cl==tree[tree[k].rs].cl) tree[k].data=tree[tree[k].ls].data+tree[tree[k].rs].data;
			else tree[k].data=tree[tree[k].ls].data;
			if (tree[tree[k].ls].cr==tree[tree[k].rs].cl) tree[k].res=tree[tree[k].ls].res+tree[tree[k].rs].res+(rds){tree[tree[k].ls].sz,tree[tree[k].ls].sz}*tree[tree[k].rs].data;
			else tree[k].res=tree[tree[k].ls].res+tree[tree[k].rs].res;
		}
		return;
	}
	int add(int k,int L,int R,int x,rds d)
	{
		int nw=++length;
		tree[nw]=tree[k];
		if (L==R)
		{
			tree[nw].cl=tree[nw].cr=ds[x].x,tree[nw].sz=1,tree[nw].data=d;
			return nw;
		}
		int mid=(L+R)>>1;
		if (x<=mid) tree[nw].ls=add(tree[nw].ls,L,mid,x,d);
		else tree[nw].rs=add(tree[nw].rs,mid+1,R,x,d);
		push_up(nw);
		return nw;
	}
	int merge(int x,int y)
	{
		if (!x||!y) return x^y;
		tree[x].ls=merge(tree[x].ls,tree[y].ls),tree[x].rs=merge(tree[x].rs,tree[y].rs),push_up(x);
		return x;
	}
};
seg T;
struct seg2
{
	struct node
	{
		int ls,rs,sz;
		rds data,res;
	};
	node tree[60*N+1];
	int length;
	void push_up(int k)
	{
		tree[k].sz=tree[tree[k].ls].sz+tree[tree[k].rs].sz,tree[k].data=tree[tree[k].ls].data+tree[tree[k].rs].data,tree[k].res=tree[tree[k].ls].res+tree[tree[k].rs].res+(rds){tree[tree[k].ls].sz,tree[tree[k].ls].sz}*tree[tree[k].rs].data;
		return;
	}
	int add(int k,int L,int R,int x,rds d)
	{
		int nw=++length;
		tree[nw]=tree[k];
		if (L==R)
		{
			tree[nw].sz=1,tree[nw].data=tree[nw].res=d;
			return nw;
		}
		int mid=(L+R)>>1;
		if (x<=mid) tree[nw].ls=add(tree[nw].ls,L,mid,x,d);
		else tree[nw].rs=add(tree[nw].rs,mid+1,R,x,d);
		push_up(nw);
		return nw;
	}
	int merge(int x,int y)
	{
		if (!x||!y) return x^y;
		tree[x].ls=merge(tree[x].ls,tree[y].ls),tree[x].rs=merge(tree[x].rs,tree[y].rs),push_up(x);
		return x;
	}
};
seg2 T2;
void merge(int x,int y)
{
	rt[y]=T.merge(rt[x],rt[y]),rt2[y]=T2.merge(rt2[x],rt2[y]);
	return;
}
void dfs2(int x)
{
	for (int i=0;i<E[x].size();++i) dfs2(E[x][i]),merge(E[x][i],x);
	dp[x]=T.tree[rt[x]].res-T2.tree[rt2[x]].res,rt[x]=T.add(rt[x],1,n,nums[x],rd[x]),rt2[x]=T2.add(rt2[x],1,n,rks[x],rd2[x]);
	return;
}
vector<int>beechtree(int SN,int M,vector<int>P,vector<int>C)
{
	int top;
	vector<int>p(SN);
	n=SN,cl[0]=1;
	for (int i=2;i<=N;++i) lg[i]=lg[i>>1]+1;
    for (int i=1;i<n;++i) cl[i]=C[i],fa[i]=P[i],E[fa[i]].push_back(i);
	for (int i=0;i<n;++i) sort(E[i].begin(),E[i].end(),cmp),rd[i]=(rds){(int)(RAND()%mod1),(int)(RAND()%mod2)};
	dfs(0),pw[0]=(rds){1,1};
	for (int i=1;i<=leng;++i) delta[i]=E[st[i]].size(),hsh[i]=hsh[i-1]*(rds){Base1,Base2}+(rds){delta[i],delta[i]},pw[i]=pw[i-1]*(rds){Base1,Base2};
	q.push((nde){0,0});
	while (!q.empty())
	{
		top=q.top().num,rks[top]=++cater,sp[cater]=top,q.pop();
		for (int i=0;i<E[top].size();++i) q.push((nde){E[top][i],cater});
	}
	for (int i=0;i<n;++i)
	{
		rd2[i]=zero;
		for (int j=0;j<E[i].size();++j) rd2[i]=rd2[i]+rd[E[i][j]];
	}
	for (int i=0;i<n;++i) ds[i+1]=(points){cl[i],rks[i],i};
	sort(ds+1,ds+n+1);
	for (int i=1;i<=n;++i) nums[ds[i].num]=i;
	dfs2(0);
	for (int i=0;i<n;++i) p[i]=(dp[i]==zero);
	return p;
}