#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
#define pb push_back
const int N=2e5+5;
int a[N],fa[N],vs[N],sz[N],rt[N],ans[N];
struct Edge {int v,x;bool operator < (Edge t) const {return x<t.x;}};
struct Node {int u,w;bool operator < (Node t) const {return w==t.w?u<t.u:w<t.w;}};
vector<Edge> e[N];set<Node> z[N];
int f(int u,int x)
{
    auto it=lower_bound(e[u].begin(),e[u].end(),(Edge) {0,x});
    return it!=e[u].end() && x==it->x?it->v:0;
}
bool cmp(int u,int v)
{for(auto [u1,x]:e[u]) {int v1=f(v,x);if(sz[u1]>sz[v1]) return 0;}return 1;}
bool merge(int &x,int &y)
{
    if(z[x].size()<z[y].size()) swap(x,y);
    for(auto i:z[y])
    {
        z[x].insert(i);auto it=z[x].find(i);
        if(it!=z[x].begin() && !cmp(prev(it)->u,i.u)) return 0;
        ++it;if(it!=z[x].end() && !cmp(i.u,it->u)) return 0;
    }z[y].clear();return 1;
}
void dfs(int u)
{
    sz[u]=ans[u]=1;for(auto [v,x]:e[u]) dfs(v),sz[u]+=sz[v];++vs[0];
    for(auto [v,x]:e[u]) {if(!ans[v] || vs[x]==vs[0]) {ans[u]=0;return;}vs[x]=vs[0];}
    rt[u]=u;z[u].insert((Node) {u,sz[u]});
    for(auto [v,x]:e[u]) if(!merge(rt[u],rt[v])) {ans[u]=0;return;}
}
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]});
    for(int i=1;i<=n;++i) sort(e[i].begin(),e[i].end());
    dfs(1);copy(ans+1,ans+n+1,res.begin());return res;
}