/******************************************************************************
Online C++ Compiler.
Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.
*******************************************************************************
*
*/
//#define DEBUG
#ifndef DEBUG
#include "beechtree.h"
#endif
#include <bits/stdc++.h>
using namespace std;
//#define DEBUG
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C)
{
set<int> level1;
int col = -1;
vector<int> res(N);
vector<vector<int>> adj(N);
for (int i = 1; i < N; ++i) {
adj[P[i]].push_back(i);
}
vector<int> sz(N,1);
auto dfs = [&](auto& dfs, int node) -> void {
/// << node << " = ";
bool ok = true;
res[node] = 1;
for (auto& u : adj[node]) {
dfs(dfs, u);
sz[node]+=sz[u];
}
for (auto& u : adj[node]) {
if (!res[u]) {
res[node] = 0;
return;
}
}
vector<int> ord;
priority_queue<std::array<int, 3> >pq;
pq.push({sz[node],-(int)ord.size(),node});
while(pq.size()){
int v =pq.top()[2];
pq.pop();
ord.push_back(v);
for(int x : adj[v]){
pq.push({sz[x],-(int)ord.size(),x});
}
}
map<int, int> cnt;
int need = 0;
#ifdef DEBUG
cout << "at node = " << node << ":\n";
#endif
for (auto i : ord) {
#ifdef DEBUG
cout << " node = " << i << ", with color = " << C[i] << ", need = " << need << "\n";
#endif
if(need++==0)continue;
int p = ord[cnt[C[i]]++];
if(p!=P[i]){
res[node]=0;
break;
}
}
};
dfs(dfs, 0);
return res;
}
#ifdef DEBUG
int main(){
int n,m;
cin>>n>>m;
vector<int>p(n),c(n);
for(int&x:p)cin>>x;
for(int&x:c)cin>>x;
for(auto x:beechtree(n,m,p,c)){
cout << x << " ";
}
}
#endif
