#include "beechtree.h"
#include <bits/stdc++.h>
using namespace std;
vector<set<pair<int, int>>> S;
vector<map<int, int>> ch;
vector<int> sz;
vector<int> res;
bool check(int u, int v) {
for (auto [c, x]: ch[u]) {
auto it = ch[v].find(c);
if (it == ch[v].end()) {
return false;
}
if (sz[x] > sz[it->second]) {
return false;
}
}
return true;
}
void dfs(int u) {
if (res[u] == 0) {
return;
}
sz[u] = 1;
for (auto [c, v]: ch[u]) {
dfs(v);
if (res[v] == 0) {
res[u] = 0;
return;
}
sz[u] += sz[v];
}
S[u].emplace(sz[u], u);
for (auto [c, v]: ch[u]) {
if (S[u].size() < S[v].size()) {
S[u].swap(S[v]);
}
for (auto p: S[v]) {
auto it = S[u].insert(p).first;
if (it != S[u].begin() && !check(prev(it)->second, p.second)) {
res[u] = 0;
return;
}
if (next(it) != S[u].end() && !check(p.second, next(it)->second)) {
res[u] = 0;
return;
}
}
}
}
vector<int> beechtree(int N, int M, vector<int> P, vector<int> C) {
S.resize(N);
ch.resize(N);
sz.resize(N);
res.resize(N, 1);
for (int i = 1; i < N; i++) {
if (res[P[i]] == 0) {
continue;
}
auto it = ch[P[i]].find(C[i]);
if (it != ch[P[i]].end()) {
res[P[i]] = 0;
}
else {
ch[P[i]][C[i]] = i;
}
}
dfs(0);
int cut = -1;
for (int i = 0; i < N; i++) {
if (res[i] == 1) {
cut = i;
break;
}
}
if (cut != -1) {
for (int i = cut; i < N; i++) {
assert(res[i] == 1);
}
}
return res;
}
