#include "beechtree.h"
#include <bits/stdc++.h>
#define ll int64_t
#define ld long double
using namespace std;
//
const int maxn =2e5+5;
const int mod = 1e9+7; // 998244353,1610612741
const ll inf = 1e18;
const ld pi = atan(1.0L)*4;
int sz[maxn],par[maxn],b[maxn],cnt[maxn],col[maxn];
vector<int> res;
bool vs[maxn];
vector<int> g[maxn],a;
struct nai{
int s,id,u;
bool operator<(const nai& other) const {
return (s==other.s?id<other.id:s>other.s);
}
};
set<nai> s;
int get(int u,int p=-1) {
sz[u]=1;
for (auto v:g[u]) {
if (!vs[v]&&v!=p) sz[u]+=get(v,u);
}
return sz[u];
}
int find (int u,int s,int p=-1) {
for (auto v:g[u]) {
if (!vs[v]&&v!=p&&sz[v]*2>=s) return find(v,s,u);
}
return u;
}
int calc(int u){
a.clear();
s.insert({sz[u],0,u});
while (!s.empty()) {
int x=s.begin()->u;
s.erase(s.begin());
a.push_back(x);
for (auto v:g[x]) {
if (v!=par[x]) s.insert({sz[v],(int)a.size(),v});
}
}
for (int i=1;i<a.size();i++) cnt[col[a[i]]]=0;
for (int i=1;i<a.size();i++) {
int x=(i==1?0:cnt[col[a[i]]]);
if (par[a[i]]!=a[x]) return false;
cnt[col[a[i]]]++;
}
return true;
}
void nai(int u) {
int c=find(u,get(u));
vs[c]=1;
if (b[c]==-1){
b[c]=calc(c);
if (b[c]==0) {
for (int v=par[c];v&&b[v]==-1;v=par[v]) b[v]=0;
}
}
if (b[c]!=1) {
for (auto v:g[c]) {
if (!vs[v]&&v!=par[c]) nai(v);
}
}
if (par[c]&&!vs[par[c]]) nai(par[c]);
}
vector<int> beechtree(int n,int m,vector<int> p,vector<int> c){
for (int i=1;i<=n;i++) {
g[i].clear();
vs[i]=0;
b[i]=-1;
}
for (int i=0;i<n;i++) {
col[i+1]=c[i];
par[i+1]=p[i]+1;
g[par[i+1]].push_back(i+1);
g[i+1].push_back(par[i+1]);
}
res.resize(n);
nai(1);
for (int i=1;i<=n;i++) {
if (i>1&&b[par[i]]==1) b[i]=1;
res[i-1]=b[i];
}
return res;
}
