#include "beechtree.h"
#include <cstdlib>
#include <cstring>
using namespace std;
typedef vector<int> vi;
const int N = 200000, LN = 18, N_ = N * (LN + 1) + 1; /* LN = ceil(log2(N)) */
int min(int a, int b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
int n;
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;
}
int xx[N], ta[N], tb[N];
void dfs1(int i) {
static int time;
ta[i] = time++;
xx[i] = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs1(j);
xx[i] += xx[j];
}
tb[i] = time;
}
int qq[N], yy[N], ii[N], jj[N];
void extend() {
for (int i = n - 1; i >= 0; i--) {
yy[i] = qq[i] == -1 ? 0 : xx[qq[i]];
qq[i] = qq[i] == -1 ? -1 : qq[qq[i]];
}
}
void sort(int *xx, int *ii, int *jj) {
memset(kk, 0, (n + 2) * sizeof *kk);
for (int i = 0; i < n; i++) {
int j = ii[i];
kk[xx[j] + 1]++;
}
for (int x = 1; x <= n + 1; x++)
kk[x] += kk[x - 1];
for (int i = 0; i < n; i++) {
int j = ii[i];
jj[kk[xx[j]]++] = j;
}
}
void compress() {
for (int i = 0, x = 0; i < n; i++)
xx[ii[i]] = i + 1 == n || xx[ii[i + 1]] != xx[ii[i]] || yy[ii[i + 1]] != yy[ii[i]] ? x++ : x;
}
int ll[N_], rr[N_], kk_[N_];
int node(int l, int r, int x) {
static int _ = 1;
int t_ = _++;
kk_[t_] = 1;
if (r - l > 1) {
int m = (l + r) / 2;
if (x < m)
ll[t_] = node(l, m, x);
else
rr[t_] = node(m, r, x);
}
return t_;
}
int merge(int t1, int t2) {
if (t1 == 0)
return t2;
if (t2 == 0)
return t1;
ll[t1] = merge(ll[t1], ll[t2]), rr[t1] = merge(rr[t1], rr[t2]), kk_[t1] += kk_[t2];
return t1;
}
int query(int t, int l, int r, int k) {
if (r - l == 1)
return l;
int m = (l + r) / 2;
return k <= kk_[ll[t]] ? query(ll[t], l, m, k) : query(rr[t], m, r, k - kk_[ll[t]]);
}
int ll_[N_], rr_[N_], mn[N_], mx[N_];
int node_(int l, int r, int x) {
static int _ = 1;
int t_ = _++;
mn[t_] = mx[t_] = xx[pp[ii[x]]];
if (r - l > 1) {
int m = (l + r) / 2;
if (x < m)
ll_[t_] = node_(l, m, x);
else
rr_[t_] = node_(m, r, x);
}
return t_;
}
int x_, incr;
int merge_(int t1, int t2) {
if (t1 == 0 && t2 == 0)
return 0;
if (t1 == 0) {
if (x_ > mn[t2])
incr = 0;
x_ = mx[t2];
return t2;
}
if (t2 == 0) {
if (x_ > mn[t1])
incr = 0;
x_ = mx[t1];
return t1;
}
ll_[t1] = merge_(ll_[t1], ll_[t2]), rr_[t1] = merge_(rr_[t1], rr_[t2]);
mn[t1] = min(mn[t1], mn[t2]), mx[t1] = max(mx[t1], mx[t2]);
return t1;
}
int tt[N], tt_[N], kk[N]; char good[N];
void dfs2(int i) {
good[i] = 1;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
dfs2(j);
if (!good[j])
good[i] = 0;
}
if (!good[i])
return;
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
jj[cc[j]] = -1;
}
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (jj[cc[j]] != -1) {
good[i] = 0;
return;
}
jj[cc[j]] = j;
}
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
tt_[j] = node_(0, n, xx[j]), yy[j] = xx[i], kk[j] = 1;
}
tt[i] = node(0, n, xx[i]);
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
tt[i] = merge(tt[i], tt[j]);
for (int o = eo[j]; o--; ) {
int k = ej[j][o], j_ = jj[cc[k]];
if (j_ == -1) {
good[i] = 0;
return;
}
x_ = -1, incr = 1, tt_[j_] = merge_(tt_[j_], tt_[k]);
if (!incr) {
good[i] = 0;
return;
}
yy[j_] = max(yy[j_], yy[k]), kk[j_] += kk[k];
}
}
for (int o = eo[i]; o--; ) {
int j = ej[i][o];
if (yy[j] > query(tt[i], 0, n, kk[j])) {
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);
dfs1(0);
for (int i = 0; i < n; i++) {
xx[i] = n - xx[i];
qq[i] = pp[i];
ii[i] = i;
}
for (int l = 0; l <= LN; l++) {
extend();
sort(yy, ii, jj);
sort(xx, jj, ii);
compress();
}
for (int i = 0; i < n; i++)
yy[i] = ta[i];
sort(yy, ii, jj);
sort(xx, jj, ii);
compress();
for (int i = 0; i < n; i++)
jj[i] = -1;
dfs2(0);
vi good_(n, 0);
for (int i = 0; i < n; i++)
good_[i] = good[i];
return good_;
}
Compilation message
beechtree.cpp: In function 'void append(int, int)':
beechtree.cpp:26:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
26 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
beechtree.cpp: In function 'void sort(int*, int*, int*)':
beechtree.cpp:55:9: error: 'kk' was not declared in this scope
55 | memset(kk, 0, (n + 2) * sizeof *kk);
| ^~
