20200615 SCOI模拟T2（树链剖分）

CF1017G The Tree

思路：
发现暴力感染复杂度过高，转换一下思路

感染一次将点权加一，对于一个节点 u，它要感染到子节点 v，那么 u 到 v 的路径和要大于路径距离
即$sum-(dep[v]-dep[u])\geq 0$sum−(dep[v]−dep[u])≥0
发现询问时 dep 不好维护，于是 玄学 变换一下
将每个点的初始点权赋为 -1
查询即一段路径和大于等于零
于是维护右区间和的最大值
如果存在最大值大于零，即被感染

考虑二操作
对于节点 u 执行二操作，将 u 的子树区间覆盖为 -1
但是 u 节点的权值不对，查询 u 时可能被感染
灵机一动
将 u 的权值赋为其到根节点的右区间和的最大值的相反数减一，这样无论怎么查询都不可能被感染
正确性证明不会

代码：

#include <bits/stdc++.h>
using namespace std;
#define in Read()

inline char ch() {
  static char buf[1 << 21], *p1 = buf, *p2 = buf;
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2)
             ? EOF
             : *p1++;
}

inline int in {
  int s = 0, f = 1;
  char x;
  for (x = getchar(); x < '0' || x > '9'; x = getchar())
    if (x == '-') f = -1;
  for (; x >= '0' && x <= '9'; x = getchar()) s = (s * 10) + (x & 15);
  return f == 1 ? s : -s;
}

const int A = 4e5 + 5;
const int INF = 1e9;
int n, Q;
int head[A], tot_road;
struct Road {
  int nex, to;
} road[2 * A];
inline void edge(int x, int y) {
  road[++tot_road] = {head[x], y};
  head[x] = tot_road;
}

int f[A], dep[A], sz[A], son[A], top[A], pos[A], idx[A], tot;
inline void DFS1(int fa, int x) {
  f[x] = fa, dep[x] = dep[fa] + 1, sz[x] = 1;
  for (int y = head[x]; y; y = road[y].nex) {
    int z = road[y].to;
    if (z == fa) continue;
    DFS1(x, z);
    sz[x] += sz[z];
    if (sz[z] > sz[son[x]]) son[x] = z;
  }
  return;
}
inline void DFS2(int x) {
  pos[x] = ++tot, idx[pos[x]] = x;
  if (son[x]) {
    top[son[x]] = top[x];
    DFS2(son[x]);
  }
  for (int y = head[x]; y; y = road[y].nex) {
    int z = road[y].to;
    if (top[z]) continue;
    top[z] = z;
    DFS2(z);
  }
  return;
}
inline void tree_cut() {
  DFS1(0, 1);
  top[1] = 1;
  DFS2(1);
  return;
}

#define lch p << 1
#define rch p << 1 | 1
struct SGT {
  int l, r, sum, max, tag;
} tr[4 * A];
inline void clean(SGT &x) {
  x.l = x.r = 0;
  x.sum = 0;
  x.max = -INF;
  x.tag = 0;
  return;
}
inline void pushup(int p) {
  tr[p].sum = tr[lch].sum + tr[rch].sum;
  tr[p].max = max(tr[rch].max, tr[rch].sum + tr[lch].max);
  return;
}
inline void pushdown(int p) {
  if (tr[p].l != tr[p].r && tr[p].tag) {
    tr[lch].sum = -(tr[lch].r - tr[lch].l + 1);
    tr[rch].sum = -(tr[rch].r - tr[rch].l + 1);
    tr[lch].max = -1;
    tr[rch].max = -1;
    tr[lch].tag = 1;
    tr[rch].tag = 1;
    tr[p].tag = 0;
  }
  return;
}
inline void build(int p, int l, int r) {
  tr[p].l = l, tr[p].r = r;
  if (l == r) {
    tr[p].sum = -1;
    tr[p].max = -1;
    tr[p].tag = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(lch, l, mid), build(rch, mid + 1, r);
  pushup(p);
  return;
}
inline void add(int p, int w, int val) {
  if (tr[p].l == tr[p].r) {
    tr[p].sum += val;
    tr[p].max += val;
    return;
  }
  pushdown(p);
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (w <= mid)
    add(lch, w, val);
  else
    add(rch, w, val);
  pushup(p);
  return;
}
inline SGT merge(SGT x, SGT y) {
  if (x.max == -INF) return y;
  if (y.max == -INF) return x;
  SGT ans;
  clean(ans);
  ans.sum = x.sum + y.sum;
  ans.max = max(y.max, y.sum + x.max);
  return ans;
}
inline SGT qurey(int p, int l, int r) {
  if (tr[p].l >= l && tr[p].r <= r) return tr[p];
  pushdown(p);
  int mid = (tr[p].l + tr[p].r) >> 1;
  SGT ans;
  clean(ans);
  if (l <= mid) ans = merge(ans, qurey(lch, l, r));
  if (r >= mid + 1) ans = merge(ans, qurey(rch, l, r));
  return ans;
}
inline void cover(int p, int l, int r) {
  if (tr[p].l >= l && tr[p].r <= r) {
    tr[p].sum = -(tr[p].r - tr[p].l + 1);
    tr[p].max = -1;
    tr[p].tag = 1;
    return;
  }
  pushdown(p);
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (l <= mid) cover(lch, l, r);
  if (r >= mid + 1) cover(rch, l, r);
  pushup(p);
  return;
}
inline void change(int p, int w, int val) {
  if (tr[p].l == tr[p].r) {
    tr[p].sum = val;
    tr[p].max = val;
    return;
  }
  pushdown(p);
  int mid = (tr[p].l + tr[p].r) >> 1;
  if (w <= mid)
    change(lch, w, val);
  else
    change(rch, w, val);
  pushup(p);
  return;
}
#undef lch
#undef rch

inline int find(int x) {
  SGT ans;
  clean(ans);
  while (x) {
    ans = merge(qurey(1, pos[top[x]], pos[x]), ans);
    x = f[top[x]];
  }
  return ans.max;
}

inline void color(int x) {
  cover(1, pos[x], pos[x] + sz[x] - 1);
  int k = find(x);
  if (k >= 0) change(1, pos[x], -k - 2);
  return;
}

signed main() {
  n = in, Q = in;
  for (int i = 2; i <= n; i++) {
    int u = in;
    edge(u, i), edge(i, u);
  }
  tree_cut();
  build(1, 1, n);
  while (Q--) {
    int opt = in;
    if (opt == 1) {
      int u = in;
      add(1, pos[u], 1);
    } else if (opt == 2) {
      int u = in;
      color(u);
    } else {
      int u = in;
      puts(find(u) >= 0 ? "black" : "white");
    }
  }
  return 0;
}