#include "beechtree.h"
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
const int N = 2e5 + 10;
int n , col[N] , m , sbt[N] , is_path[N] , cnt[N] , dis[N];
vector <int> adj[N];
vector <int> all , p;
bool bad[N] , mark[N];
void Dfs(int v)
{
sbt[v] = 1;
dis[v] = 0;
for(auto u : adj[v])
{
Dfs(u);
sbt[v] += sbt[u];
bad[v] |= bad[u];
dis[v] = max(dis[v] , dis[u] + 1);
}
if(adj[v].size() == 1)
{
int c = adj[v][0];
if(sbt[c] == 1)
is_path[v] = col[c];
else if(col[c] == is_path[c])
is_path[v] = col[c];
else
is_path[v] = -1;
}
else if(adj[v].size() > 1)
{
is_path[v] = -1;
}
vector <int> vec;
for(auto u : adj[v])
vec.push_back(col[u]);
sort(vec.begin() , vec.end());
for(int i = 1 ; i < vec.size() ; i++) if(vec[i] == vec[i - 1])
bad[v] = true;
}
void Dfs_all(int v)
{
all.push_back(v);
cnt[col[v]] = 0;
for(auto u : adj[v])
Dfs_all(u);
}
bool cmp(pair<int , int> aa , pair<int , int> bb)
{
if(cnt[aa.F] != cnt[bb.F])
return cnt[aa.F] < cnt[bb.F];
return aa.F < bb.F;
}
bool Solve(int v)
{
all.clear();
Dfs_all(v);
sort(all.begin() , all.end());
vector <int> vec , all_col;
int cnt_root = 0;
vector <pair<int , int>> check;
for(int i = 1 ; i < all.size() ; i++)
{
int now = all[i];
all_col.push_back(col[now]);
if(p[now] != 0)
{
cnt[col[now]]++;
check.push_back(make_pair(col[now] , p[now]));
mark[p[now]] = false;
}
}
sort(all_col.begin() , all_col.end());
all_col.resize(unique(all_col.begin() , all_col.end()) - all_col.begin());
if(all_col.size() != adj[v].size())
return false;
sort(check.begin() , check.end() , cmp);
int las = -1 , num = all_col.size() + 1;
for(auto u : check)
{
if(u.F != las)
{
las = u.F;
num--;
}
if((int)adj[u.S].size() < num)
return false;
}
return true;
}
vector<int> beechtree(int nn, int mm, vector<int> P, vector<int> C)
{
n = nn;
m = mm;
p = P;
for(int i = 1 ; i < n ; i++)
{
adj[P[i]].push_back(i);
col[i] = C[i];
}
Dfs(0);
vector <int> res(n , 0);
for(int i = 0 ; i < n ; i++)
{
if(is_path[i] != -1)
{
res[i] = true;
continue;
}
if(bad[i] || dis[i] >= 3)
{
continue;
}
Solve(i);
}
return res;
}
