#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 pp[N], 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;
}
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 sz[N], qu[N], ta[N], tb[N];
void dfs(int i) {
static int time;
sz[i] = 1, qu[ta[i] = time++] = i;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs(j);
sz[i] += sz[j];
}
tb[i] = time;
}
int compare_sz(int i, int j) {
while (i != -1 && j != -1) {
if (sz[i] != sz[j])
return sz[j] - sz[i];
i = pp[i], j = pp[j];
}
return ta[i] - ta[j];
}
int compare_eo(int i, int j) { return eo[i] - eo[j]; }
int (*compare)(int, int);
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) {
int c = compare(ii[j], i_);
if (c == 0)
j++;
else if (c < 0) {
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;
}
}
int qu_[N], kk[M];
int hh[N];
vi beechtree(int n, int m, vi pp_, vi cc_) {
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);
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 if (n <= 200) {
dfs(0);
for (int i = 0; i < n; i++) {
for (int h = ta[i]; h < tb[i]; h++)
qu_[h - ta[i]] = qu[h];
compare = compare_sz, sort(qu_, 0, tb[i] - ta[i]);
ans[i] = 1;
for (int h = 1; h < tb[i] - ta[i]; h++) {
int j = qu_[h];
if (qu_[kk[cc[j]]++] != pp[j]) {
ans[i] = 0;
break;
}
}
for (int h = 0; h < tb[i] - ta[i]; h++) {
int j = qu_[h];
kk[cc[j]] = 0;
}
}
} 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;
}
compare = compare_eo, 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;
}
