#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<VI> tson(n);
    vector<vector<VI>> ps(n);
    vector<int> val(n,1);
    VI sz(n);
    for (int i=1;i<n;i++) {
        son[P[i]].pb(mp(i,C[i]));
    }
    //puts("???");
    function<void(int)> dfs=[&](int u) {
        ps[u].pb(VI{});
        tson[u].pb(u);
        sz[u]=1;
        VI cc;
        for (auto [v,c]:son[u]) {
            dfs(v);
            tson[u].pb(v);
            sz[u]+=sz[v];
            //for (auto w:tson[v]) tson[u].pb(w);
            cc.pb(c);
            if (!val[v]) val[u]=0;
            for (auto x:ps[v]) {
                auto y=x; y.insert(y.begin(),c);
                ps[u].pb(y);
            }
        }
        //printf("?? %d %d\n",u,SZ(tson[u]));
        sort(all(cc));
        rep(i,0,SZ(cc)-1) if (cc[i]==cc[i+1]) val[u]=0;
        auto cmp=[&](vector<VI> &a,vector<VI> &b) {
            sort(all(a)); sort(all(b));
            for (auto x:b) {
                auto it=lower_bound(all(a),x);
                //for (auto y:x) printf("%d ",y); puts("----");
                if (it==a.end()||*it!=x) return false;
            }
            //puts("!!!");
            return true;
        };
        if (val[u]) {
            sort(all(tson[u]),[&](int &a,int b) {
                return SZ(tson[a])>SZ(tson[b]);
            });
            rep(i,0,SZ(tson[u])-1) {
                if (!cmp(ps[tson[u][i]],ps[tson[u][i+1]])) {
                    val[u]=0;
                    break;
                }
            }
        }
    };
    dfs(0);
    return val;
}