#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif
const int MAXN = 200005;
const int inf=1000000500ll;
const long long oo =1000000000000000500ll;
const int MOD = (int)1e9+7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int par[MAXN];
vector<int>childs[MAXN];
int st[MAXN],en[MAXN];
int TIME;
bool isleaf[MAXN];
bool child(int par, int child){
if(st[par]<=st[child] && en[par]>=en[child])return 1;
return 0;
}
void dfs(int x, int p){
st[x]=TIME++;
par[x]=p;
isleaf[x]=1;
for(auto v:childs[x]){
isleaf[x]=0;
dfs(v,x);
}
en[x]=TIME-1;
}
std::vector<int> beechtree(int n, int M, std::vector<int> P, std::vector<int> C)
{
vector<int> res=vector<int>(n,0);
for(int i=1;i<n;i++){
childs[P[i]].push_back(i);
}
dfs(0,-1);
for(int i=0;i<n;i++){ // check for this guy
if(isleaf[i]){
res[i]=1;
continue;
}
int nonleafs=0;
for(auto x:childs[i]){
if(!isleaf[x])nonleafs++;
}
if(nonleafs>1){
res[i]=0;
continue;
}
int leaf=-1;
for(auto x:childs[i]){
if(!isleaf[x])leaf=x;
}
if(leaf == -1){
// everyone is a leaf. just check that they are all different
unordered_set<int>os;
for(auto x:childs[i]){
os.insert(C[x]);
}
if(os.size() == childs[i].size()){
res[i]=1;
} else{
res[i]=0;
}
} else{
// 1 leaf.
bool bad=0;
unordered_set<int>ms;
for(auto x:childs[i]){
ms.insert(C[x]);
}
for(auto x:childs[leaf]){
if(!isleaf[x])bad=1;
if(ms.find(C[x]) == ms.end()){
bad=1;
} else{
}
}
if(!bad ){
res[i]=1;
}else{
res[i]=0;
}
}
}
return res;
}
