#include "beechtree.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
const int N = 2e5+100;
int s[N];
vi T[N];
vector<pii> g[N];
vi res;
bool check_cover(vi &x, vi &y){
for(int u: y){
int pos = lower_bound(all(x), u) - x.begin();
if(pos < (int)x.size() && x[pos] == u) continue;
return false;
}
return true;
}
void dfs(int v){
bool ok = true;
vi col;
s[v] = 1;
if(g[v].empty()){
res[v] = 1;
return;
}
for(auto [u, cl]: g[v]){
dfs(u);
s[v] += s[u];
if(res[u] == 0){
ok = false;
}
col.pb(cl);
}
if(!ok){
res[v] = 0;
return;
}
if(v != 0){
int sz = col.size();
sort(all(col));
col.erase(unique(all(col)), col.end());
T[v] = col;
if((int)col.size() < sz){
res[v] = 0;
return;
}
int id = -1;
for(auto [u, col]: g[v]){
if(s[u] > 1){
if(id == -1)
id = u;
else id = -2;
}
}
if(id == -2) res[v] = 0;
else if(id == -1) res[v] = 1;
else{
if(check_cover(T[v], T[id])){
res[v] = 1;
}else{
res[v] = 0;
}
}
}else{
int sz = col.size();
sort(all(col));
col.erase(unique(all(col)), col.end());
T[v] = col;
if((int)col.size() < sz){
res[v] = 0;
return;
}
sort(all(g[v]), [&](const pii &x, const pii &y){
return (int)T[x.ff].size() > (int)T[y.ff].size();
});
vector<vi> S;
S.pb(T[v]);
for(auto [u, cl]: g[v]) S.pb(T[u]);
for(int i = 1; i < (int) S.size(); ++i){
if(!check_cover(S[i-1], S[i])){
res[v] = 0;
return;
}
}
res[v] = 1;
}
}
std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> C)
{
for(int i = 0; i < n; ++i) T[i].clear(), g[i].clear();
res.clear();
res.resize(n);
for(int i = 1; i < n; ++i) g[P[i]].pb({i, C[i]});
dfs(0);
return res;
}
