#include "beechtree.h"
#include <cstdlib>
using namespace std;
typedef vector<int> vi;
const int N = 200000, M = 200000;
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int cc[N];
int *ej[N], eo[N];
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;
}
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (eo[ii[j]] == eo[i_])
j++;
else if (eo[ii[j]] < eo[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
char used[M];
int duplicate(int i) {
int dup = 0;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (used[cc[j]])
dup = 1;
used[cc[j]] = 1;
}
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
used[cc[j]] = 0;
}
return dup;
}
int contains(int i1, int i2) {
for (int o = eo[i1]; o--; ) {
int j = ej[i1][o];
used[cc[j]] = 1;
}
int cont = 1;
for (int o = eo[i2]; o--; ) {
int j = ej[i2][o];
if (!used[cc[j]])
cont = 0;
}
for (int o = eo[i1]; o--; ) {
int j = ej[i1][o];
used[cc[j]] = 0;
}
return cont;
}
int hh[N];
vi beechtree(int n, int m, vi pp, vi cc_) {
for (int i = 1; i < n; 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);
int line = 1;
for (int i = 1; i < n; i++)
if (pp[i] != i - 1) {
line = 0;
break;
}
vi ans(n, 0);
if (line) {
ans[n - 1] = 1;
for (int i = n - 2; i >= 0 && cc[i + 1] == cc[n - 1]; i--)
ans[i] = 1;
} else
for (int i = n - 1; i >= 0; i--) {
hh[i] = 0;
for (int o = 0; o < eo[i]; o++)
hh[i] = max(hh[i], hh[ej[i][o]] + 1);
if (hh[i] > 2) {
ans[i] = 0;
continue;
}
sort(ej[i], 0, eo[i]);
ans[i] = !duplicate(i);
for (int o = 0; o < eo[i]; o++)
if (duplicate(ej[i][o])) {
ans[i] = 0;
break;
}
for (int o = 0; o < eo[i]; o++)
if (!contains(o + 1 == eo[i] ? i : ej[i][o + 1], ej[i][o])) {
ans[i] = 0;
break;
}
}
return ans;
}
