#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ALL(a) a.begin(), a.end()
const int MXN = 200200;
int n;
int m;
vector<int> p;
vector<int> c;
vector<int> adj[MXN];
bool leaf[MXN];
int h[MXN];
int sz[MXN];
vector<int> sub[MXN];
bool cmp(int v, int u) {
if (h[v]!=h[u]) return h[v]<h[u];
else return sz[v]>sz[u];
}
bool is_subset(vector<int> a, vector<int> b) {
set<int> all;
for (int x : b) all.insert(c[x]);
for (int x : a) if (!all.contains(c[x])) return false;
return true;
}
vector<int> ans;
void dfs(int v) {
sz[v] = 1;
if (leaf[v]) {
ans[v] = 1;
return;
}
vector<int> norm, esp;
for (int u : adj[v]) {
h[u] = h[v]+1;
dfs(u);
sz[v] += sz[u];
for (int x : sub[u]) (leaf[x] ? esp : norm).pb(x);
(leaf[u] ? esp : norm).pb(u);
}
ans[v] = 1;
sort(ALL(norm), cmp);
for (int i=0; i+1 < norm.size(); i++) if (!is_subset(sub[norm[i]], sub[norm[i+1]])) ans[v] = 0;
vector<int> kids;
for (int u : adj[v]) kids.pb(u);
if (!norm.empty()) if (!is_subset(sub[norm.back()], kids)) ans[v] = 0;
sort(ALL(kids), [&](int x, int y) {
return c[x] < c[y];
});
for (int i=0; i+1 < kids.size(); i++) if (c[kids[i]] != c[kids[i+1]]) ans[v] = 0;
for (int x : norm) sub[v].pb(x);
for (int x : esp) sub[v].pb(x);
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
n = N;
m = M;
p = P;
c = C;
for (int i=1; i<n; i++) adj[p[i]].pb(i);
for (int i=0; i<n; i++) leaf[i] = adj[i].empty();
ans.resize(n);
dfs(0);
return ans;
}
