#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
#define pb push_back
const int N=2005,M=2e5+5;
int a[N],fa[N],L[N],R[N],ord[N],dep[N],s[N],z1[N],ans[N],z[N][N][2];struct Edge {int v,x;};
struct Node {int x,w;bool operator < (Node t) const {return x<t.x;}};
vector<Edge> e[N];vector<Node> vc[N];
int f(int u,int x)
{
    auto it=lower_bound(vc[u].begin(),vc[u].end(),(Node) {x,0});
    if(it==vc[u].end() || x!=it->x) return 0;return it->w;
}
int cmp(int u,int v)
{
    int t,cnt=0,fl1=0,fl2=0;
    for(auto [x,w]:vc[u]) {t=f(v,x);if(t) ++cnt;fl1|=w<t;fl2|=t<w;}
    fl1|=cnt<vc[v].size();return fl1*2+fl2;
}
void dfs(int u)
{
    ord[L[u]=++L[0]]=u;
    for(auto [v,x]:e[u]) dep[v]=dep[u]+1,dfs(v),vc[u].pb((Node) {x,f(v,x)+1});
    sort(vc[u].begin(),vc[u].end());for(auto [x,w]:vc[u]) s[u]+=w;R[u]=L[0];
}
void dfs1(int u)
{
    ans[u]=1;for(auto [v,x]:e[u]) dfs1(v),z1[u]=max(z1[u],z1[v]);
    for(auto [v,x]:e[u]) if(!ans[v]) {ans[u]=0;return;}
    for(auto [v,x]:e[u]) for(int i1=L[v],i=ord[i1];i1<=R[v];i=ord[++i1])
        for(int j1=L[u],j=ord[j1];j1<L[v];j=ord[++j1])
        {z1[u]=max(z1[u],min(z[i][j][0],z[i][j][1]));if(cmp(i,j)==3) {ans[u]=0;return;}}
    if(z1[u]>=dep[u]) ans[u]=0;
}
vector<int> beechtree(int n,int m,vector<int> _fa,vector<int> _a)
{
    vector<int> res(n);for(int i=1;i<=n;++i) fa[i]=_fa[i-1]+1,a[i]=_a[i-1];
    for(int i=2;i<=n;++i) e[fa[i]].pb((Edge) {i,a[i]});
    dep[1]=1;dfs(1);for(int i=1;i<=n;++i) z[i][i][0]=z[i][i][1]=1e9;
    for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j)
    {
        if(a[i]==a[j]) z[i][j][0]=z[fa[i]][fa[j]][0],z[i][j][1]=z[fa[i]][fa[j]][1];
        if(s[i]<s[j]) z[i][j][0]=min(dep[i],dep[j]);if(s[i]>s[j]) z[i][j][1]=min(dep[i],dep[j]);
    }dfs1(1);copy(ans+1,ans+n+1,res.begin());return res;
}