/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include"beechtree.h"
int S=0;
int n,m;
vector<int>c,ans,p;
vector<vector<int>>a;
vector<vector<int>>nd;
void calc1(int i){
vector<int>&pp=nd[i];
pp={i};
for(int&j:a[i]){
calc1(j);
for(int&k:nd[j])pp.push_back(k);
}
sort(pp.begin(),pp.end());
int fnd=0;
do{
vector<int>f(m+1,0);
int vl=1;
for(int i=1;i<pp.size();i++){
vl&=pp[f[c[pp[i]]]]==p[pp[i]];
f[c[pp[i]]]++;
}
if(vl){fnd=1;break;}
}
while(next_permutation(pp.begin()+1,pp.end()));
ans[i]&=fnd;
}
vector<int>d;
void calc2(int i){
int vv=0;
for(int&j:a[i]){
calc2(j);
d[i]=max(d[j]+1,d[i]);
vv+=a[j].size()>0;
}
if(d[i]<=2&&vv<=1){
set<int>s,ss;
for(int&j:a[i]){
if(!a[j].empty()){
for(int&k:a[j])s.insert(c[k]);
}
ss.insert(c[j]);
}
for(auto&ii:s)ans[i]&=ss.find(ii)!=ss.end();
}
else ans[i]=0;
}
void check(int i){
set<int>s;
for(int&j:a[i]){
check(j);
ans[i]&=ans[j];
s.insert(c[j]);
}
ans[i]&=s.size()==a[i].size();
}
vector<int>beechtree(int N,int M,vector<int>P,vector<int>C){
n=N;m=M;c=C;a.resize(n);ans.assign(n,1);p=P;
for(int i=1;i<n;i++)a[p[i]].push_back(i);
check(0);
S=1;for(int i=1;i<n;i++)S&=p[i]==i-1;
vector<int>f(m+1,0);for(int&i:c)f[i]++;
if(n<9){
nd.resize(n);
calc1(0);
}
else if(S){
ans[n-1]=1;
int i;
for(i=n-1;i>0&&c[i]==c.back();i--)ans[i-1]=1;
for(;i>0;i--)ans[i-1]=0;
}
else if(*max_element(f.begin(),f.end())<3){
d.assign(n,0);
calc2(0);
}
else{
;
}
return ans;
}
