/* https://oj.uz/submission/841403 (model_code) */
#include "beechtree.h"
#include <cstdlib>
#include <vector>
using namespace std;
typedef vector<int> vi;
const int N = 200000, M = 200000, LN = 18, N_ = N * (LN + 1) + 1, MD = 0x7fffffff, X = 123456789; /* LN = ceil(log2(N)) */
int n;
int *ej[N], eo[N], pp[N], cc[N], sz[N];
int min_(int i, int j) { return sz[i] < sz[j] ? i : j; }
int max_(int i, int j) { return sz[i] > sz[j] ? i : j; }
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
long long *ek[M]; int *ev[M], eo_[M];
int hash_(long long k) {
return (k / MD * X + k % MD) % MD * X % MD % M;
}
int add(long long k, int v) {
int h = hash_(k);
for (int o = eo_[h]; o--; )
if (ek[h][o] == k)
return 0;
int o = eo_[h]++;
if (o >= 2 && (o & o - 1) == 0) {
ek[h] = (long long *) realloc(ek[h], o * 2 * sizeof *ek[h]);
ev[h] = (int *) realloc(ev[h], o * 2 * sizeof *ev[h]);
}
ek[h][o] = k, ev[h][o] = v;
return 1;
}
int get(long long k) {
int h = hash_(k);
for (int o = eo_[h]; o--; )
if (ek[h][o] == k)
return ev[h][o];
return -1;
}
int contained(int i1, int i2) {
for (int o = eo[i1]; o--; ) {
int j1 = ej[i1][o], j2 = get((long long) i2 * M + cc[j1]);
if (j2 == -1 || sz[j1] > sz[j2])
return 0;
}
return 1;
}
int ll[N_], rr[N_], mn[N_], mx[N_];
int node(int l, int r, int s, int i) {
static int _ = 1;
int t_ = _++;
mn[t_] = mx[t_] = i;
if (r - l > 1) {
int m = (l + r) / 2;
if (s < m)
ll[t_] = node(l, m, s, i);
else
rr[t_] = node(m, r, s, i);
}
return t_;
}
int incr, i_, type;
int merge(int t1, int t2, int l, int r) {
if (t1 == 0 && t2 == 0)
return 0;
if (t1 == 0) {
if (i_ != -1 && type != 1 && !contained(i_, mn[t2]))
incr = 0;
i_ = mx[t2], type = 1;
return t2;
}
if (t2 == 0) {
if (i_ != -1 && type != 2 && !contained(i_, mn[t1]))
incr = 0;
i_ = mx[t1], type = 2;
return t1;
}
if (r - l == 1) {
if (!contained(mn[t1], mn[t2]))
incr = 0;
i_ = mx[t1], type = 1;
return t1;
}
int m = (l + r) / 2;
ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r);
mn[t1] = min_(mn[t1], mn[t2]), mx[t1] = max_(mx[t1], mx[t2]);
return t1;
}
vi good; int tt[N];
void dfs(int i) {
sz[i] = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j);
sz[i] += sz[j];
}
if (!good[i])
return;
tt[i] = node(0, n, sz[i] - 1, i);
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (!good[j]) {
good[i] = 0;
return;
}
incr = 1, i_ = -1, type = -1, tt[i] = merge(tt[i], tt[j], 0, n);
if (!incr) {
good[i] = 0;
return;
}
}
}
vi beechtree(int n_, int m, vi pp_, vi cc_) {
n = n_;
for (int i = 0; i < n; i++)
pp[i] = pp_[i], cc[i] = cc_[i] - 1;
for (int i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (int i = 1; i < n; i++)
append(pp[i], i);
good.clear(); good.resize(n, 1);
for (int h = 0; h < M; h++) {
ek[h] = (long long *) malloc(2 * sizeof *ek[h]);
ev[h] = (int *) malloc(2 * sizeof *ev[h]);
}
for (int i = 1; i < n; i++)
if (!add((long long) pp[i] * M + cc[i], i))
good[pp[i]] = 0;
dfs(0);
return good;
}
