#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#define rng(i,a,b) for(int i=int(a);i<=int(b);i++)
#define rep(i,b) rng(i,0,b-1)
#define gnr(i,b,a) for(int i=int(b);i>=int(a);i--)
#define per(i,b) gnr(i,b-1,0)
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define bg begin()
#define ed end()
#define all(x) x.bg,x.ed
#define si(x) int(x.size())
template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;
typedef long long ll;
using pii=pair<int,int>;
using vi=vc<int>;
using uint=unsigned;
using ull=unsigned long long;
using pil=pair<int,ll>;
using pli=pair<ll,int>;
using pll=pair<ll,ll>;
using t3=tuple<int,int,int>;
ll rand_int(ll l, ll r) { //[l, r]
#ifdef LOCAL
static mt19937_64 gen;
#else
static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
#endif
return uniform_int_distribution<ll>(l, r)(gen);
}
#define N_ 201000
int n, m, w[N_], CC[N_],par[N_], CK[N_], Num[N_];
vi E[N_];
vi ans;
map<int,int>D[N_], G[N_];
void DFS(int a){
CC[a]=1;
set<int>Set;
for(auto &x:E[a]){
DFS(x);
Set.insert(w[x]);
CC[a]+=CC[x];
}
if(si(Set) != si(E[a])){
CK[a]=1;
}
}
int Go(int a){
if(!si(E[a])){
Num[a] = a;
D[a][CC[a]] = a;
return 1;
}
for(auto &t:E[a]){
ans[t] = Go(t);
//printf("%d %d\n",t,ans[t]);
}
if(CK[a]){
return 0;
}
int x = -1, Mx = -1;
for(auto &t:E[a]){
if(!ans[t])return 0;
if(Mx <CC[t]){
Mx=CC[t];
x=t;
}
}
int px = Num[x];
Num[a]=px;
for(auto &y:E[a]){
if(y==x)continue;
int py = Num[y];
for(auto &[c,u] : D[py]){
if(c==1)continue;
auto it = D[px].lower_bound(c);
int v = it->se;
int vv;
if(it->fi == c)vv = v;
else{
it--;
vv=it->se;
}
for(auto &z: E[u]){
if(!G[v].count(w[z]) || CC[G[v][w[z]]] < CC[z])return 0;
}
for(auto &z: E[vv]){
if(!G[u].count(w[z]) || CC[G[u][w[z]]] < CC[z])return 0;
}
}
for(auto &[c,u] : D[py]){
D[px][c]=u;
}
}
auto it = D[px].end();it--;
int u = it->se;
for(auto &z: E[u]){
if(!G[a].count(w[z]) || CC[G[a][w[z]]] < CC[z])return 0;
}
D[px][CC[a]]=a;
return 1;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
n=N, m=M;
ans.resize(n);
rep(i,n){
CK[i]=0;
E[i].clear();
}
map<int,int>Map;
int c=0;
rng(i,1,n-1){
par[i]=P[i];
E[P[i]].pb(i);
if(!Map.count(C[i])){
Map[C[i]]=++c;
}
}
m=c;
rng(i,1,n-1){
C[i]=Map[C[i]];
w[i]=C[i];
G[P[i]][w[i]]=i;
}
DFS(0);
ans[0] = Go(0);
return ans;
}
