#include "beechtree.h"
#include<bits/stdc++.h>
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
// #define int ll
// #define N 
using namespace std;
std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> C)
{
    vector<poly>G(n,poly());
    vector<set<pa>>all(n);
    poly siz(n,0),val(n,1);
    for (int i=1;i<n;i++)
        G[P[i]].push_back(i);
    vector<map<int,int>>son(n,map<int,int>());
    function<int(int,int)>cmp=[&](int x,int y)
    {
        // cout<<"!!!"<<x<<" "<<y<<endl;
        for (auto [u,v]:son[y])
        {
            if (!son[x].count(u)||son[x][u]<v) return 0;
        }
        // cout<<"!!!"<<x<<" "<<y<<" 1"<<endl;
        return 1;
    };
    function<void(set<pa>&,pa)>ins=[&](set<pa>&x,pa y)
    {
        // cout<<"ins "<<y.fi<<" "<<y.se<<endl;
        auto it=x.lower_bound(y);
        if (it!=x.end())   
        {
            if (!cmp((*it).se,y.se)) return;
        }
        if (it!=x.begin())
        {
            it--;
            if (!cmp(y.se,(*it).se)) return;
        }
        x.insert(y);
    };

    function<void(int)>dfs=[&](int k)
    {
        siz[k]++;
        int ms=0;
        for (auto u:G[k])
        {
            // cout<<"!!!!"<<u<<"->"<<k<<endl;
            dfs(u);
            siz[k]+=siz[u];
            val[k]&=val[u];
            if (ms==0||siz[u]>siz[ms]) ms=u;
            son[k][C[u]]=siz[u];
        }
        sort(G[k].begin(),G[k].end(),[&](int x,int y)
        {
            return C[x]<C[y];
        });
        for (int i=1;i<G[k].size();i++)
            if (C[G[k][i]]==C[G[k][i-1]]) val[k]=0;
        // cout<<k<<" "<<C[k]<<" "<<val[k]<<" "<<ms<<endl;
        if (val[k]==0) return;
        if (!ms)
        {
            all[k].insert(mp(siz[k],k));
            return;
        }
        all[k]=all[ms];
        for (auto u:G[k])
            if (u!=ms)
            {
                // cout<<"!!!!"<<u<<"->"<<k<<endl;
                for (auto v:all[u])
                    ins(all[k],v);
                set<pa>().swap(all[u]);
            }
        ins(all[k],mp(siz[k],k));
        if (all[k].size()!=siz[k]) val[k]=0;
    };
    dfs(0);
    return val;
}