#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/ioi/contests/ioi23_d2/debug.h"
#else
#define debug(...) void(37)
#endif
/*
template<typename T, using F = function<T(const T&, const T&)>>
struct SegTree {
F op;
vector<T> tree; T def;
int n;
SegTree(int _n, T _def, F _op) : n(_n), op(_op), def(_def) {
tree.resize(2 * n);
}
T get(int l, int r) {
T res = def;
for (l += n, r += n + 1; l < r; l >> 1, r >> 1) {
if (l % 2) res = op(res, tree[l++]);
if (r % 2) res = op(res, tree[--r]);
}
return res;
}
void modify(int p, T x) {
for (tree[p += n] = x; p > 1; p >>= 1) {
tree[p >> 1] = op(tree[p], tree[p ^ 1]);
}
}
};
*/
struct Fenwick {
vector<int> sum;
int n;
Fenwick() { }
Fenwick(int _n) : n(_n) {
sum.resize(n + 1);
}
int get(int x) {
x += 1;
int res = 0;
while (x > 0) {
res += sum[x];
x -= x & -x;
}
return res;
}
void modify(int x, int v) {
x += 1;
while (x <= n) {
sum[x] += v;
x += x & -x;
}
}
};
std::vector<int> beechtree(int N, int M, std::vector<int> P, std::vector<int> C) {
for (auto& x : C) --x;
vector<vector<int>> g(N);
for (int i = 1; i < N; ++i) {
g[P[i]].push_back(i);
}
vector<vector<int>> sub(N);
vector<int> s(N, 1);
for (int i = N - 1; i > 0; --i) {
s[P[i]] += s[i];
sub[P[i]].push_back(C[i]);
}
vector<bool> bad(N, false);
for (int i = 0; i < N; ++i) {
sort(sub[i].begin(), sub[i].end());
for (int j = 0; j < int(sub[i].size()) - 1; ++j) {
if (sub[i][j] == sub[i][j + 1]) bad[i] = true;
}
}
for (int i = 0; i < N; ++i) {
for (auto u : g[i]) {
if (int(g[u].size()) > int(g[i].size())) bad[i] = true;
}
}
vector<vector<int>> all(M);
for (int i = 1; i < N; ++i) {
all[C[i]].push_back(s[i]);
}
debug(all);
for (int i = 0; i < M; ++i) {
sort(all[i].begin(), all[i].end());
all[i].erase(unique(all[i].begin(), all[i].end()), all[i].end());
}
vector<int> ind(N, -1);
for (int i = 1; i < N; ++i) {
ind[i] = int(all[C[i]].size()) - 1 - int(lower_bound(all[C[i]].begin(), all[C[i]].end(), s[i]) - all[C[i]].begin());
}
debug(ind);
vector<Fenwick> fenws(M);
for (int i = 0; i < M; ++i) {
fenws[i] = Fenwick(int(all[i].size()));
}
vector<int> ct(M);
set<array<int, 2>> sizes;
vector<array<int, 2>> fenwick_updates;
bool still_good = true;
vector<bool> cur_color(M);
auto Add = [&](int v) {
int l = 0, r = N;
for (auto u : g[v]) {
cur_color[C[u]] = true;
}
{
auto it = sizes.begin();
while (it != sizes.end()) {
if (!cur_color[(*it)[1]]) {
l = -(*it)[0];
break;
}
it = next(it);
}
}
for (auto u : g[v]) {
r = min(r, fenws[C[u]].get(ind[u]));
l = max(l, fenws[C[u]].get(ind[u] - 1));
}
still_good &= l <= r;
for (auto u : g[v]) {
cur_color[C[u]] = false;
sizes.erase({-ct[C[u]], C[u]});
ct[C[u]]++;
sizes.insert({-ct[C[u]], C[u]});
fenws[C[u]].modify(ind[u], +1);
fenwick_updates.push_back({C[u], ind[u]});
}
};
auto Reset = [&] {
still_good = true;
sizes.clear();
for (auto[c, x] : fenwick_updates) {
fenws[c].modify(x, -1);
ct[c] = 0;
}
fenwick_updates.clear();
};
auto Dfs = [&](int v, bool calculating, auto&& Dfs) -> void {
debug(v, calculating);
for (int i = 0; i < int(g[v].size()); ++i) {
if (s[g[v][0]] < s[g[v][i]]) swap(g[v][0], g[v][i]);
}
if (calculating) {
for (int i = int(g[v].size()) - 1; i >= 0; --i) {
Reset();
Dfs(g[v][i], true, Dfs);
}
for (int i = int(g[v].size()) - 1; i > 0; --i) {
Dfs(g[v][i], false, Dfs);
}
Add(v);
if (!still_good) bad[v] = true;
} else {
Add(v);
for (auto u : g[v]) {
Dfs(u, false, Dfs);
}
}
};
Dfs(0, true, Dfs);
for (int i = N - 1; i > 0; --i) {
if (bad[i]) bad[P[i]] = true;
}
vector<int> res(N);
for (int i = 0; i < N; ++i) res[i] = 1 ^ bool(bad[i]);
return res;
}
