#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> BI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}()); 
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head

std::vector<int> beechtree(int n, int M, std::vector<int> P, std::vector<int> C)
{
    vector<vector<PII>> son(n);
    vector<map<int,int>> mson(n);
    vector<VI> tson(n);
    vector<vector<VI>> ps(n);
    vector<int> val(n,1);
    vector<VI> rkord(n);
    VI sz(n);
    for (int i=1;i<n;i++) {
        son[P[i]].pb(mp(i,C[i]));
        mson[P[i]][C[i]]=i;
    }
    function<void(int)> dfs=[&](int u) {
        sz[u]=1;
        VI cc;
        for (auto [v,c]:son[u]) {
            dfs(v);
            sz[u]+=sz[v];
            cc.pb(c);
            if (!val[v]) val[u]=0;
        }
        sort(all(cc));
        rep(i,0,SZ(cc)-1) if (cc[i]==cc[i+1]) val[u]=0;
        auto cmp=[&](int a,int b) {
            if (SZ(son[a])>SZ(son[b])) return false;
            for (auto [c,col]:son[a]) {
                if (!mson[b].count(col)) return false;
                if (sz[c]>sz[mson[b][col]]) return false;
            }
            return true;
        };
        auto add=[&](VI &c,int w) {
            auto p=lower_bound(all(c),w,[&](int a,int b) {
                return sz[a]<sz[b];
            });
            if (p!=c.begin()&&!cmp(*prev(p),w)) return false;
            if (p!=c.end()&&!cmp(w,*p)) return false;
            //puts("??");
            c.insert(p,w);
            return true;
        };
        if (val[u]) {
            for (auto [v,c]:son[u]) {
                for (auto w:rkord[v]) if (!add(rkord[u],w)) {
                    val[u]=0; break;
                }
            }
            if (!add(rkord[u],u)) val[u]=0;
        }
        /*if (val[u]) {
            printf("%d : ",u); for (auto x:rkord[u]) printf("%d ",x); puts("");
        }*/
    };
    dfs(0);
    return val;
}