#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;
}
bool task3(vector<int> P){
int N = P.size();
vector<vector<int>> g(N);
for (int i = 1; i<N; i++){
g[P[i]].push_back(i);
g[i].push_back(P[i]);
}
int res = 0;
auto dfs = [&] (auto&& self, int u, int p, int d) -> void {
res = max(res, d);
for (int e: g[u]){
if (e!=p){
self(self, e, u, d+1);
}
}
};
dfs(dfs, 0, 0, 0);
return res<=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 i = 1; i<vec.size(); i++){
int e = vec[i];
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 (e!=u){
if (st.find(C[e])==st.end()) f = false;
}
}
if (f) R[u] = 1;
}
}
};
dfs(dfs, 0, 0);
return R;
}
else if (task3(P)){
vector<vector<int>> g(N);
for (int i = 1; i<N; i++){
g[P[i]].push_back(i);
g[i].push_back(P[i]);
}
bool f = true;
set<int> ss;
for (int i = 0; i<N; i++){
set<int> st;
int cnt = 0;
for (int e: g[i]){
if (e!=0) {
cnt++;
st.insert(C[e]);
}
}
if (st.size()==cnt) R[i] = 1;
else f = false;
if (i==0){
ss = st;
}
else {
for (int e: st){
if (ss.find(e)==ss.end()) f = false;
}
}
}
R[0] = f;
return R;
}
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int main(){
// // int t = 100;
// // int n = 5;
// // int u = 0;
// // while(t--){
// // cout<<t<<endl;
// // vector<int> P(n), C(n);
// // P[0] = -1;
// // for (int i = 1; i<n; i++) P[i] = rng()%i;
// // for (int i = 0; i<n; i++) C[i] = rng()%(n+1)+1;
// // vector<int> R1 = beechtree(n, 10, P, C);
// // vector<int> R2 = brute(n, 10, P, C);
// // if (R1!=R2){
// // for (int e: P) cout<<e<<" ";
// // cout<<endl;
// // for (int e: C) cout<<e<<" ";
// // cout<<endl;
// // return 0;
// // }
// // else {
// // u++;
// // }
// // }
// // cout<<u<<endl;
// vector<int> R1 = beechtree(5, 10, {-1, 0, 1, 1, 0}, {3, 3, 2, 2, 3});
// vector<int> R2 = brute(5, 10, {-1, 0, 1, 1, 0}, {3, 3, 2, 2, 3});
// for (int e: R1) cout<<e<<" ";
// cout<<endl;
// for (int e: R2) cout<<e<<" ";
// }
