// D. Beech Tree
#include<bits/stdc++.h>
#include "beechtree.h"
using namespace std;
using g_t = vector<vector<int>>;
using dVal = map<int, int>;
struct ValR {
int d, n, co;
};
dVal dfs(int n, g_t &g, vector<bool>& po, vector<int>& c) {
dVal r;
map<int, vector<pair<int,int>>> ve;
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]) {
dVal re = dfs(e, g, po, c);
if (!po[e]) {
po[n] = false;
}
if (po[n]) {
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].push_back({d, e});
}
}
}
if (!po[n]) return {};
map<int,int> val;
vector<ValR> si;
for (auto &[co, vec]: ve) {
si.push_back({r[co] - 1, 0, co});
si.push_back({r[co], 0, co});
for (auto [d, e]: vec) {
val[e] = 0;
if (d > r[co]) {
po[n] = false;
return {};
} else if (d == r[co]) {
si.back().n++;
si[si.size() - 2].n++;
} else if (d == r[co] - 1) {
si[si.size() - 2].n++;
}
}
}
std::sort(si.begin(), si.end(), [](const ValR& l, const ValR& r) {return l.n > r.n;});
int i = 1;
for (auto v: si) {
for (auto [d, e]: ve[v.co]) {
if (d >= v.d) {
if (val[e] != i - 1) {
po[n] = false;
return {};
}
val[e] = i;
}
}
i++;
}
return r;
}
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()};
}
