#include "bits/stdc++.h"
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
bool is_path(vector<int> P){
for (int i = 1; i<P.size(); i++){
if (P[i]!=i-1) return false;
}
return true;
}
bool mx_cnt(vector<int> C, int M){
vector<int> cnt(M+1);
for (int e: C) cnt[e]++;
return *max_element(all(cnt))<=2;
}
vector<int> brute(int N, int M, vector<int> P, vector<int> C){
vector<int> R(N);
vector<vector<int>> g(N);
for (int i = 1; i<N; i++){
g[P[i]].push_back(i);
g[i].push_back(P[i]);
}
vector<vector<int>> sub(N);
auto dfs = [&] (auto&& self, int u, int p) -> void {
for (int e: g[u]){
if (e!=p){
self(self, e, u);
for (int x: sub[e]) sub[u].push_back(x);
}
}
sort(all(sub[u]));
do {
map<int, int> cnt;
bool f = true;
vector<int> vec = sub[u];
vec.insert(vec.begin(), u);
for (int e: vec){
if (P[e]!=vec[cnt[C[e]]]){
f = false;
break;
}
cnt[C[e]]++;
}
if (f){
R[u] = 1;
break;
}
}
while(next_permutation(all(sub[u])));
sub[u].push_back(u);
};
dfs(dfs, 0, 0);
return R;
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
vector<int> R(N);
if (N<=8){
return brute(N, M, P, C);
}
else if (is_path(P)){
set<int> st;
for (int i = N-1; i>=0; i--){
if (st.size()<=1) R[i] = 1;
else break;
st.insert(C[i]);
}
return R;
}
else if (mx_cnt(C, M)){
vector<vector<int>> g(N);
for (int i = 1; i<N; i++){
g[P[i]].push_back(i);
g[i].push_back(P[i]);
}
vector<int> height(N);
auto dfs = [&] (auto&& self, int u, int p) -> void {
vector<int> ch;
int cnt = 0;
set<int> st;
for (int e: g[u]){
if (e!=p){
self(self, e, u);
height[u] = max(height[u], height[e]+1);
if (height[e]==1) ch.push_back(e);
st.insert(C[e]);
cnt++;
}
}
if (height[u]==0) R[u] = 1;
else if (height[u]==1){
if (st.size()==cnt) R[u] = 1;
}
else if (height[u]==2){
if (st.size()==cnt && ch.size()==1){
int v = ch[0];
bool f = true;
for (int e: g[v]){
if (st.find(C[e])==st.end()) f = false;
}
if (f) R[u] = 1;
}
}
};
dfs(dfs, 0, 0);
return R;
}
}
// int main(){
// }
