#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;
set<int> TT[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;
S[v].pb(v);
return;
}
int big = -1;
for(auto [u, cl]: g[v]){
dfs(u);
for(int x: S[u]) S[v].pb(x);
TT[u].insert(cl);
if(big == -1 || s[u] > s[big]) big = u;
s[v] += s[u];
if(res[u] == 0){
ok = false;
}
col.pb(cl);
}
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;
}
TT[v].swap(TT[big]);
for(auto [u, cl]: g[v]){
if(u != big){
for(int x: TT[u]) TT[v].insert(x);
}
}
// cerr << v << ' ' << " :\n";
// for(int x: TT[v]){
// cerr << x << ' ';
// }
// cerr << '\n';
// cerr << '\n';
vector<vi> CL(m + 1);
for(int x: TT[v]){
for(int u: S[v]){
if(C[u] == x && u != v)
CL[x].pb(par[u]);
}
sort(all(CL[x]));
}
sort(all(CL), [&](const vi &x, const vi &y){
return x.size() > y.size();
});
bool fine = true;
for(int i = 1; i < (int) CL.size(); ++i){
if(!check_cover(CL[i - 1], CL[i])){
fine = false;
break;
}
}
if(!fine){
res[v] = 0;
return;
}
res[v] = 1;
return;
}
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;
}
