#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
const int lim=2e5+100;
using pii=pair<int,int>;
#define pb push_back
int n,m;
vector<int>p,c;
int dep[lim];
vector<int>v[lim];
unordered_map<int,int>guycnt[lim],col[lim];
map<int,int>cnt[lim];
struct Node{
int dep=0,chcnt=0,minch=0,maxch=0;
}dat[lim];
using pnode=Node*;
struct cmp{
bool operator()(pnode i,pnode j) const {
if(i->dep^j->dep)return i->dep<j->dep;
if(i->chcnt^j->chcnt)return i->chcnt>j->chcnt;
if(i->minch^j->minch)return i->minch>j->minch;
return i->maxch>j->maxch;
}
};
set<pnode,cmp>ct[lim];
bool insertnode(int par,pnode x){
auto p=ct[par].insert(x).first;
if(p!=ct[par].begin()){
auto pp=prev(p);
if((*pp)->chcnt<x->chcnt)return 0;
if((*pp)->minch<x->minch)return 0;
if((*pp)->maxch<x->maxch)return 0;
}
auto pp=next(p);
if(pp!=ct[par].end()){
if((*pp)->chcnt>x->chcnt)return 0;
if((*pp)->minch>x->minch)return 0;
if((*pp)->maxch>x->maxch)return 0;
}
return 1;
}
vector<int>dp;
void dfs(int node){
for(int j:v[node]){
dfs(j);
if(!dp[j]){
dp[node]=0;
}
}
if(!dp[node])return;
insertnode(node,dat+node);
for(int j:v[node]){
if(ct[node].size()<ct[j].size()){
swap(ct[j],ct[node]);
}
for(pnode p:ct[j]){
if(!insertnode(node,p)){
dp[node]=0;
return;
}
}
if(col[node].size()<col[j].size()){
swap(col[node],col[j]);
swap(cnt[node],cnt[j]);
}
for(auto[x,y]:col[j]){
if((--cnt[node][col[node][x]])==0){
cnt[node].erase(col[node][x]);
}
cnt[node][col[node][x]+=y]++;
}
if(guycnt[node].size()<guycnt[j].size()){
swap(guycnt[j],guycnt[node]);
}
for(auto[x,y]:guycnt[j]){
guycnt[node][x]+=y;
}
}
int have=col[node].size(),prevsum=0;
for(auto[x,y]:cnt[node]){
if(guycnt[node][have]!=x-prevsum){
dp[node]=0;
return;
}
have-=y;
prevsum=x;
}
}
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C){
n=N,m=M;
p=P,c=C;
dp=vector<int>(n,1);
for(int i=1;i<n;i++){
v[P[i]].pb(i);
if(col[P[i]].count(C[i]))dp[P[i]]=0;
col[P[i]][c[i]]=1;
cnt[p[i]][1]++;
}
for(int i=n-1;0<=i;i--){
guycnt[i][v[i].size()]++;;
dat[i].chcnt=v[i].size();
if(dat[i].chcnt){
dat[i].minch=INT_MAX;
dat[i].maxch=0;
for(int j:v[i]){
dat[i].minch=min(dat[i].minch,dat[j].chcnt);
dat[i].maxch=max(dat[i].maxch,dat[j].chcnt);
}
}
}
for(int i=1;i<n;i++){
dep[i]=dep[p[i]]+1;
}
dfs(0);
return dp;
}
