#include "bits/stdc++.h"
#include "beechtree.h"
#define pb push_back
using namespace std;
const int N = 2e5 + 5;
vector<pair<int, int> > ch[N];
bool comp1(int a, int b){
if(ch[a].size() == ch[b].size()) return (a < b);
else return (ch[a].size() > ch[b].size());
}
bool comp2(int a, int b){
if(ch[a].size() == ch[b].size()) return (a > b);
else return (ch[a].size() > ch[b].size());
}
vector<int> perm;
vector<pair<int, int> > edges;
void dfs(int node){
perm.pb(node);
for(auto itr: ch[node]){
edges.pb(itr);
dfs(itr.first);
}
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C){
for(int i = 0; i < N; i++){
ch[i].clear();
}
for(int i = 1; i < N; i++){
ch[P[i]].pb({i, C[i]});
}
vector<int> ans(N, 0);
for(int i = 0; i < N; i++){
perm.clear();
edges.clear();
dfs(i);
vector<int> perm2 = perm;
sort(perm.begin(), perm.end(), comp1);
sort(perm2.begin(), perm2.end(), comp2);
if(perm[0] != i) continue;
vector<int> cnt(M+1), pos(N), pos2(N);
for(int j = 0; j < perm.size(); j++){
pos[perm[j]] = j;
pos2[perm2[j]] = j;
}
bool ok = 1;
for(int j = 1; j < perm.size(); j++){
if(min(pos[P[perm[j]]], pos2[P[perm[j]]]) > cnt[C[perm[j]]] || max(pos[P[perm[j]]], pos2[P[perm[j]]]) < cnt[C[perm[j]]]){
ok = 0;
}
cnt[C[perm[j]]]++;
}
/*
cout<<i<<" icin perm: ";
for(auto itr: perm){
cout<<itr<<" ";
}
cout<<endl;
*/
if(ok) ans[i] = 1;
else ans[i] = 0;
}
return ans;
}
