#include "beechtree.h"
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<tuple>
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];
bool good[MAX_N];
void dfsgood(int u)
{
set<int>s;
for(auto [v,edge]:g[u])
{
if(s.count(edge))good[u]=0;
s.insert(edge);
dfsgood(v);
good[u]=min(good[u],good[v]);
}
}
vector<int>nodes;
set<int>typesset;
int types;
int curtype;
int type[MAX_N];
int cnt[MAX_N][100];
void dfsnode(int u)
{
nodes.push_back(u);
typesset.insert((int)g[u].size());
for(auto [v,edge]:g[u])
{
dfsnode(v);
}
}
void dfs(int u,int ty)
{
if(g[u].size()==curtype)
{
type[u]=ty;
cnt[u][ty]=1;
}
else cnt[u][ty]=0;
for(auto [v,edge]:g[u])
{
dfs(v,ty);
cnt[u][ty]+=cnt[v][ty];
}
}
int seq[MAX_N];
int sz;
map<int,int>cntt;
int root;
bool add(int u)
{
if(sz==0)
{
if(u!=root)return 0;
}
else
{
if(seq[cntt[col[u]]]!=par[u])return 0;
cntt[col[u]]++;
}
seq[sz++]=u;
return 1;
}
bool cmp(int x,int y)
{
return cnt[x][curtype]<cnt[y][curtype];
}
bool cmp2(int x,int y)
{
return seq[par[x]]<seq[par[y]];
}
bool solve(int r)
{
//if(good[r]==0)return 0;
root=r;
types=0;
typesset.clear();
nodes.clear();
cntt.clear();
sz=0;
dfsnode(r);
if(nodes.size()<=2)return 1;
for(int u:nodes)type[u]=-1;
for(int downedges:typesset)
{
curtype=downedges;
dfs(r,types);
types++;
}
vector<vector<int>>v;
v.push_back(nodes);
for(int ty=types-1;ty>=0;ty--)
{
curtype=ty;
vector<vector<int>>nv;
vector<int>vv;
for(auto&curblock:v)
{
sort(curblock.rbegin(),curblock.rend(),cmp);
int prev=-1;
for(auto&x:curblock)
{
if(cnt[x][ty]!=prev)
{
if(prev!=-1)nv.push_back(vv);
vv.clear();
}
vv.push_back(x);
prev=cnt[x][ty];
}
nv.push_back(vv);
}
swap(nv,v);
}
for(auto&curblock:v)
{
sort(curblock.begin(),curblock.end(),cmp2);
for(auto&x:curblock)
{
if(add(x)==0)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++)
{
good[i]=1;
}
dfsgood(0);
for(int i=0;i<n;i++)
{
ans[i]=solve(i);
}
return ans;
}
