#include "beechtree.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int MAX_N=2e5+5;
int n,m;
vector<pair<int,int>>g[MAX_N];
int par[MAX_N];
int col[MAX_N];
int level[MAX_N];
vector<int>nodes;
vector<int>nodescol[MAX_N];
void dfs(int u)
{
for(auto [v,edge]:g[u])
{
nodescol[edge].push_back(v);
nodes.push_back(v);
dfs(v);
}
}
bool solve(int r)
{
nodes.clear();
for(int i=0;i<n;i++)level[i]=1e9;
for(int i=1;i<=m;i++)nodescol[i].clear();
dfs(r);
if(nodes.size()==0)return 1;
vector<pair<int,int>>colcnt;
for(int i=1;i<=m;i++)
{
if(nodescol[i].size()==0)continue;
colcnt.push_back({(int)nodescol[i].size(),i});
}
sort(colcnt.rbegin(),colcnt.rend());
set<int>s;
bool start=0;
for(auto [prefixsz,curcol]:colcnt)
{
prefixsz--;
if(start==0)
{
for(int v:nodescol[curcol]){level[par[v]]=prefixsz;s.insert(par[v]);}
start=1;
continue;
}
set<int>ns;
for(int v:nodescol[curcol])
{
if(s.count(par[v])==0)return 0;
level[par[v]]=prefixsz;
ns.insert(par[v]);
}
swap(ns,s);
}
for(auto v:nodes)
{
if(level[v]<level[par[v]])return 0;
}
return 1;
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
n=N;
m=M;
vector<int>ans;
ans.resize(n);
for(int i=1;i<n;i++)
{
par[i]=P[i];
col[i]=C[i];
g[P[i]].push_back({i,C[i]});
}
for(int i=0;i<n;i++)
{
ans[i]=solve(i);
}
return ans;
}
