#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

VI sz;

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);
    sz=VI(n,0);
    struct node {
        int x;
        bool operator < (const node &b) const {
            return sz[x]<sz[b.x];
        }
    };
    vector<set<node>> rkord(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=[&](node aa,node bb) {
            int a=aa.x,b=bb.x;
            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=[&](set<node> &c,node w) {
            auto p=c.lower_bound(w);
            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]) {
                if (SZ(rkord[v])>SZ(rkord[u])) rkord[u].swap(rkord[v]);
                for (auto x:rkord[v]) {
                    if (!add(rkord[u],(node){x})) { val[u]=0; break; }
                }
            }
            if (!add(rkord[u],(node){u})) val[u]=0;
        }
        /*if (val[u]) {
            printf("%d : ",u); for (auto x:rkord[u]) printf("%d ",x); puts("");
        }*/
    };
    dfs(0);
    return val;
}