#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,mm;
vector<pair<int,int>>g[MAX_N];
map<int,int>coltochild[MAX_N];
int par[MAX_N];
int col[MAX_N];
bool good[MAX_N];
bool ok[MAX_N];
int sz[MAX_N];
int T;
int in[MAX_N];
int out[MAX_N];
int ver[MAX_N];
void dfs0(int u)
{
in[u]=++T;
ver[T]=u;
sz[u]=1;
set<int>s;
for(auto [v,edge]:g[u])
{
if(s.count(edge))good[u]=0;
s.insert(edge);
coltochild[u][edge]=v;
dfs0(v);
sz[u]+=sz[v];
good[u]=min(good[u],good[v]);
}
out[u]=T;
}
bool checksmaller(int a,int b)
{
for(auto [v,edge]:g[b])
{
if(coltochild[a].find(edge)==coltochild[a].end())return 0;
if(sz[coltochild[a][edge]]<sz[v])return 0;
}
return 1;
}
bool checkequal(int a,int b)
{
if(g[a].size()!=g[b].size())return 0;
for(auto [v,edge]:g[b])
{
if(coltochild[a].find(edge)==coltochild[a].end())return 0;
if(sz[coltochild[a][edge]]!=sz[v])return 0;
}
return 1;
}
map<int,int>m;
void add(int node,int u)
{
if(m.find(sz[node])==m.end())
{
auto it=m.upper_bound(sz[node]);
if(it!=m.end())
{
if(checksmaller(it->second,node)==0)ok[u]=0;
}
if(it!=m.begin())
{
it--;
if(checksmaller(node,it->second)==0)ok[u]=0;
}
m[sz[node]]=node;
}
else
{
if(checkequal(m[sz[node]],node)==0)ok[u]=0;
}
}
void dfs(int u,bool keep)
{
ok[u]=good[u];
int mx=-1,bigchild=-1;
for(auto [v,edge]:g[u])
{
if(sz[v]>mx)
{
mx=sz[v];
bigchild=v;
}
}
for(auto [v,edge]:g[u])
{
if(v!=bigchild)
{
dfs(v,0);
ok[u]=min(ok[u],ok[v]);
}
}
if(bigchild!=-1)
{
dfs(bigchild,1);
ok[u]=min(ok[u],ok[bigchild]);
}
for(auto [v,edge]:g[u])
{
if(v==bigchild)continue;
for(int pos=in[v];pos<=out[v];pos++)
{
int node=ver[pos];
add(node,u);
}
}
add(u,u);
if(keep==0)
{
m.clear();
}
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
n=N;
mm=M;
vector<int>ans;
ans.resize(n);
m.clear();
T=0;
for(int i=0;i<n;i++)
{
g[i].clear();
coltochild[i].clear();
}
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;
ok[i]=1;
}
dfs0(0);
dfs(0,0);
for(int i=0;i<n;i++)
{
ans[i]=ok[i];
}
return ans;
}
