#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn=2e5;
vector<int> cc[maxn],ch[maxn],ans,c,p;
bool fd(int x,int v){
auto it=lower_bound(cc[v].begin(),cc[v].end(),x);
return it!=cc[v].end()&&(*it)==x;
}
vector<int> dfs(int v){
vector<int> s={};
if(!cc[v].empty())s.push_back(v);
for(int u:ch[v]){
auto t=dfs(u);
for(int i:t)s.push_back(i);
ans[v]&=ans[u];
}
sort(s.begin(),s.end(),[&](int x,int y){return cc[x].size()>cc[y].size();});
for(int i=0;i+1<s.size();i++){
for(int j:cc[s[i+1]])ans[v]&=fd(j,s[i]);
}
map<int,int> ce;
for(int i=1;i<s.size();i++){
ans[v]&=p[s[i]]==s[ce[c[s[i]]]++];
}
return s;
}
std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> C)
{
p=P;
c=C;
for(int i=1;i<n;i++){
cc[p[i]].push_back(c[i]);
ch[p[i]].push_back(i);
}
ans=vector<int>(n,1);
for(int v=0;v<n;v++){
sort(cc[v].begin(),cc[v].end());
for(int i=0;i+1<cc[v].size();i++)ans[v]&=cc[v][i]!=cc[v][i+1];
}
dfs(0);
return ans;
}
