#include <beechtree.h>
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(), x.end()
const int N = 2e5+100;
int sz[N], dep[N], par[N], n;
vector<array<int, 2>> g[N], s[N];
vector<int> ans, COL;
set<int> C[N];
void dfs(int v){
ans[v] = 1;
sz[v] = 1;
s[v].pb({v, COL[v]});
for(auto U: g[v]){
int u = U[0], c = U[1];
dep[u] = dep[v] + 1;
par[u] = v;
dfs(u);
for(auto x: s[u]) s[v].pb(x);
sz[v] += sz[u];
ans[v] &= ans[u];
if(C[v].find(c) != C[v].end()) ans[v] = 0;
C[v].insert(c);
}
if(n <= 8){
sort(s[v].begin() + 1, s[v].end());
ans[v] = 0;
do{
bool ok = 1;
map<int, int> colptr;
for(int i = 1; i < s[v].size(); ++i){
int u = s[v][i][0], co = s[v][i][1];
if(par[u] != s[v][colptr[co]][0]){
ok = 0;
break;
}
colptr[co]++;
}
if(ok){
ans[v] = 1;
break;
}
}while(next_permutation(s[v].begin() + 1, s[v].end()));
}
else{
if(ans[v] == 0) return;
sort(all(g[v]), [&](const array<int, 2> &x, const array<int, 2> &y){
return sz[x[0]] > sz[y[0]];
});
for(int i = 0; i < g[v].size(); ++i){
int x = (i == 0 ? v : g[v][i - 1][0]), y = g[v][i][0];
for(auto col: C[y]){
if(C[x].find(col) == C[x].end()){
ans[v] = 0;
break;
}
}
}
if(g[v].size() > 1){
if(abs(dep[g[v][0][0]] - dep[g[v][1][0]]) > 1) ans[v] = 0;
}
if(ans[v] == 0) return;
// if(g[v].size() == 0){
// s[v].pb({v, COL[v]});
// return;
// }
// if(g[v].size() == 1){
// s[v].pb({v, COL[v]});
// for(auto u: s[g[v][0][0]]) s[v].pb(u);
// return;
// }
// int ptx = 0, pty = 0;
// array<int, 2> pt = {0, 0};
// s[v].pb(v);
// int x = g[v][0][0], y = g[v][1][0];
// int num = s[x].size() + s[y].size();
// while(num > 0){
// if(ptx == g[x].size()){
// s[v].pb({s[y][pty]});
// pty++;
// }else if(pty == g[y].size()){
// s[v].pb({s[x][ptx]});
// ptx++;
// }else{
// if(pt[0] < pt[1]){
// }else{
// }
// }
// int col = s[v].back()[1] - 1, node = s[v].back()[0];
// if(s[v][pt[col]][0] != par[node]){
// ans[v] = 0;
// return;
// }
// num--;
// }
}
}
vector<int> beechtree(int nn, int m, vector<int> P, vector<int> CC){
COL = CC;
n = nn;
for(int i = 1; i < n; ++i){
g[P[i]].pb({i, COL[i]});
}
ans.resize(n);
dep[0] = 0;
dfs(0);
return ans;
}
