#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> beechtree(int n, int m, vector<int> p, vector<int> c) {
vector<vector<int>> ch(n);
for (int i = 1; i < n; i++) {
ch[p[i]].push_back(i);
}
vector<vector<int>> my(n);
for (int i = 0; i < n; i++) {
for (int j : ch[i]) {
my[i].push_back(c[j]);
}
}
vector<bool> diff(n);
for (int i = 0; i < n; i++) {
set<int> st(my[i].begin(), my[i].end());
diff[i] = (st.size() == my[i].size());
}
vector<int> tin(n);
vector<int> tout(n);
int T = 0;
function<void(int)> Dfs = [&](int v) {
tin[v] = ++T;
for (int u : ch[v]) {
Dfs(u);
}
tout[v] = T;
};
Dfs(0);
auto IsAnc = [&](int x, int y) {
return tin[x] <= tin[y] && tout[y] <= tout[x];
};
auto IsSubset = [&](vector<int> a, vector<int> b) {
set<int> st(a.begin(), a.end());
for (int i : b) {
if (st.find(i) == st.end()) {
return false;
}
}
return true;
};
auto NoIntersect = [&](vector<int> a, vector<int> b) {
set<int> st;
for (int i : a) {
st.insert(i);
}
for (int i : b) {
st.insert(i);
}
return st.size() == a.size() + b.size();
};
vector<int> res(n);
for (int v = 0; v < n; v++) {
bool ok = true;
vector<int> ver;
for (int i = 0; i < n; i++) {
if (IsAnc(v, i)) {
ver.push_back(i);
}
}
for (int i : ver) {
ok &= diff[i];
}
for (int i : ver) {
if (i == v) {
continue;
}
ok &= IsSubset(my[p[i]], my[i]);
}
for (int i : ver) {
for (int j : ver) {
if (IsAnc(i, j) || IsAnc(j, i)) {
continue;
}
ok &= NoIntersect(my[i], my[j]);
}
}
res[v] = ok;
}
return res;
}
