#include "beechtree.h"
//#include "grader.cpp"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f first
#define s second
#define all(x) x.begin(),x.end()
namespace{
const int mxn=2e5+5;
}
std::vector<int> beechtree(int n, int m, std::vector<int> P, std::vector<int> c)
{
vector<vector<int>> adj(n);
for(int i=1;i<n;i++){
adj[P[i]].push_back(i);
}
vector<int> ans(n,1);
vector<map<int,int>> mp(n);
for(int v=0;v<n;v++){
for(auto u:adj[v]){
mp[v][c[u]]=u;
}
if((int)adj[v].size()!=(int)mp[v].size()) ans[v]=0;
}
vector<int> sz(n);
function<void(int)> dfs0=[&](int v){
sz[v]=1;
for(auto u:adj[v]){
dfs0(u);
sz[v]+=sz[u];
}
};
dfs0(0);
vector<set<pair<pair<int,int>,int>>> S(n);
int cur;
function<bool(int,int)> subset=[&](int a,int b){
//cout<<cur<<' '<<a<<' '<<b<<'\n';
if((int)adj[a].size()==(int)adj[b].size()){
if(sz[a]<sz[b]) return subset(b,a);
}
for(auto u:mp[b]){
if(mp[a].find(u.f)==mp[a].end() or sz[mp[a][u.f]]<sz[u.s]) return false;
}
return true;
};
function<void(int)> dfs=[&](int v){
S[v].insert({{(int)adj[v].size(),sz[v]},v});
for(auto u:adj[v]){
dfs(u);
ans[v]&=ans[u];
cur=v;
if((int)S[v].size()<(int)S[u].size()) swap(S[v],S[u]);
for(auto x:S[u]){
auto it=S[v].lower_bound(make_pair(x.f,0));
if(it!=S[v].end()) ans[v]&=subset((*it).s,x.s);
if(!S[v].empty() and it!=S[v].begin()) ans[v]&=subset(x.s,(*prev(it)).s);
S[v].insert(x);
}
}
};
dfs(0);
return ans;
}
