// D. Beech Tree
#include<bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using g_t = vector<vector<int>>;
using dVal = tuple<map<int, int>, list<set<pair<int, int>>>, int>;
dVal dfs(int n, g_t &g, vector<bool> &po, vector<int> &c) {
map<int, int> r;
map<int, vector<pair<int, int>>> ve;
list<set<pair<int, int>>> se;
int seSi = 0;
for (auto e: g[n]) {
if (r.find(c[e]) != r.end()) po[n] = false;
r[c[e]] = 1;
ve[c[e]] = {};
}
for (auto e: g[n]) {
auto [re, li, si] = dfs(e, g, po, c);
if (!po[e]) {
po[n] = false;
}
if (!po[n]) continue;
for (auto &[co, d]: re) {
if (r.find(co) == r.end()) {
po[n] = false;
break;
}
if (co == c[e]) r[c[e]] = d + 1;
ve[co].emplace_back(d, e);
}
if (!po[n]) continue;
if (si > seSi) {
swap(se, li);
swap(si, seSi);
}
auto itS = se.begin();
for (auto &it: li) {
assert(itS->empty());
while (itS != se.end() && itS->size() <= it.size()) {
for (auto cos: *itS) {
if (it.erase(cos) == 0) {
po[n] = false;
break;
}
}
if (!po[n]) break;
itS++;
}
if (!po[n]) break;
if (!it.empty()) {
auto act = itS;
itS = se.insert(itS, set<pair<int, int>>());
for (auto cos: it) {
if (act->erase(cos) == 0) {
po[n] = false;
break;
}
itS->insert(cos);
}
}
if (!po[n]) break;
}
}
if (!po[n]) return {};
se.emplace_back();
for (auto &[co, vec]: ve) {
bool dD = true;
for (auto [d, e]: vec) {
if (d > r[co]) {
po[n] = false;
return {};
} else if (d == r[co]) {
dD = false;
break;
}
}
if (dD) {
se.back().insert({co, r[co]});
seSi++;
}
}
if (se.back().empty()) se.pop_back();
return {std::move(r), std::move(se), seSi};
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
g_t g(N);
for (int i = 1; i < N; ++i) {
g[P[i]].push_back(i);
}
vector<bool> po(N, true);
dfs(0, g, po, C);
return {po.begin(), po.end()};
}
