#include <bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<vector<int>> adj;
vector<int> sz;
bool cmp(int a, int b) {
return sz[a] < sz[b];
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
adj.resize(N);
sz.resize(N);
for (int i=1; i<N; i++) {
adj[P[i]].push_back(i);
}
for (int i=0; i<N; i++) {
sz[i] = adj[i].size();
}
for (int i=0; i<N; i++) {
sort(adj[i].begin(), adj[i].end(), cmp);
}
vector<bool> valid(N, false);
for (int i=0; i<N; i++) {
map<int, int> mp;
for (auto x : adj[i]) {
mp[C[x]]++;
}
if (mp.size() == adj[i].size()) valid[i] = true;
else valid[i] = false;
}
vector<int> ans(N, 0);
for (int i=0; i<N; i++) {
vector<int> p;
p.push_back(i);
queue<int> q;
q.push(i);
vector<int> mp(3, 0);
bool can = true;
while (!q.empty()) {
int u = q.front();
q.pop();
if (!valid[u]) can = false;
for (auto x : adj[u]) {
if (p[mp[C[x]]] != P[x]) can = false;
q.push(x);
p.push_back(x);
mp[C[x]]++;
}
}
if (can) ans[i] = 1;
}
return ans;
}
