#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], m;
vi T[N], S[N], C, par;
vector<pii> g[N];
vi res, G[N];
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;
S[v].pb(v);
return;
}
int big = -1;
for(auto [u, cl]: g[v]){
dfs(u);
G[v].pb(cl);
col.pb(cl);
for(int x: S[u]) S[v].pb(x);
if(big == -1 || s[u] > s[big]) big = u;
s[v] += s[u];
if(res[u] == 0){
ok = false;
}
}
if(!ok){
res[v] = 0;
return;
}
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;
}
vector<vi> pt;
for(int x: S[v]){
pt.pb(G[x]);
}
sort(all(pt), [&](const vi &x, const vi &y){
return x.size() > y.size();
});
for(int i = 1; i < pt.size(); ++i){
if(!check_cover(pt[i - 1], pt[i])){
res[v] = 0;
return;
}
}
res[v] = 1;
}
std::vector<int> beechtree(int n, int mm, std::vector<int> P, std::vector<int> CC)
{
m = mm;
par = P;
C = CC;
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;
}
