CF1017G The Tree

· · 题解

CF1017G The Tree

先考虑树是一条链的情况。换言之，考虑 x 及其祖先 a。对 a 进行一次操作一，对 x 的影响为找到从根到 x 这条链上从 a 开始第一个白点并将其染黑。对 a 进行一次操作二，对 x 的影响为将 a 到 x 的所有点染黑。

我们必须找到在执行操作一不依赖于找到第一个白点的算法，否则算法无法扩展到树上。换种角度考虑，存在 x 的祖先 b 使得路径 b \to x 上所有节点被执行操作一的次数之和不小于路径长度，这是 x 为黑点的充要条件。因此，考虑线段树维护每个节点被执行操作一的次数 减 1，查询时求根到 x 路径上后缀最大值是否 \geq 0。

对于二操作呢？首先 x 子树内的所有操作一全部作废。问题在于这样做了之后并不能保证 x 子树内全部变成白点。但我们发现 x 子树内的黑点一定是从 dep_x 到某个深度 d 的所有节点，因为子树内不存在操作一，黑点只能从 x 的祖先贡献。这启发我们进行 d - dep_x + 1 次 “负操作一”，也就是把黑节点吸回去。

具体地，求出根到 x 路径后缀最大值 v，若 v \geq 0 说明节点 v 为黑色，需要执行 v + 1 次负操作 1，即将 x 被执行操作一的次数减去 v + 1。

线段树维护区间赋值，单点修改，区间查询后缀最大值。套上树剖，时间复杂度 \mathcal{O}(n + q\log ^ 2 n)。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define TIME 1e3 * clock() / CLOCKS_PER_SEC
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
inline int read() {
  int x = 0;
  char s = getchar();
  while(!isdigit(s)) s = getchar();
  while(isdigit(s)) x = x * 10 + s - '0', s = getchar();
  return x;
}
inline void print(int x) {
  if(x < 0) return putchar('-'), print(-x);
  if(x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}
bool Mbe;
constexpr int N = 1e5 + 5;
bool laz[N << 2];
int len[N << 2];
struct dat {
  int sum, suf;
  dat operator + (const dat &x) {return {sum + x.sum, max(x.suf, suf + x.sum)};}
} val[N << 2];
void tag(int x) {val[x] = {-len[x], -1}, laz[x] = 1;}
void down(int x) {if(laz[x]) tag(x << 1), tag(x << 1 | 1), laz[x] = 0;}
void build(int l, int r, int x) {
  len[x] = r - l + 1, val[x] = {-len[x], -1};
  if(l == r) return;
  int m = l + r >> 1;
  build(l, m, x << 1), build(m + 1, r, x << 1 | 1);
}
void modify(int l, int r, int ql, int qr, int x) {
  if(ql <= l && r <= qr) return tag(x);
  int m = l + r >> 1;
  down(x);
  if(ql <= m) modify(l, m, ql, qr, x << 1);
  if(m < qr) modify(m + 1, r, ql, qr, x << 1 | 1);
  val[x] = val[x << 1] + val[x << 1 | 1];
}
void toggle(int l, int r, int p, int x, int v, int type) {
  if(l == r) return val[x].sum = val[x].suf = type ? v : val[x].sum + v, void();
  int m = l + r >> 1;
  down(x);
  if(p <= m) toggle(l, m, p, x << 1, v, type);
  else toggle(m + 1, r, p, x << 1 | 1, v, type);
  val[x] = val[x << 1] + val[x << 1 | 1];
}
dat query(int l, int r, int ql, int qr, int x) {
  if(ql <= l && r <= qr) return val[x];
  int m = l + r >> 1;
  dat ans = {0, -1};
  down(x);
  if(m < qr) ans = query(m + 1, r, ql, qr, x << 1 | 1) + ans;
  if(ql <= m) ans = query(l, m, ql, qr, x << 1) + ans;
  return ans;
}
int n, q;
vector<int> e[N];
int sz[N], dep[N], fa[N], son[N];
int dn, dfn[N], top[N];
void dfs1(int id) {
  sz[id] = 1, dep[id] = fa[id] + 1;
  for(int it : e[id]) {
    dfs1(it), sz[id] += sz[it];
    if(sz[it] > sz[son[id]]) son[id] = it;
  }
}
void dfs2(int id, int tp) {
  dfn[id] = ++dn, top[id] = tp;
  if(son[id]) dfs2(son[id], tp);
  for(int it : e[id]) if(it != son[id]) dfs2(it, it);
}
bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin);
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  ios::sync_with_stdio(0);
  cin >> n >> q;
  for(int i = 2; i <= n; i++) cin >> fa[i], e[fa[i]].push_back(i);
  dfs1(1), dfs2(1, 1);
  build(1, n, 1);
  for(int i = 1; i <= q; i++) {
    int op, x;
    cin >> op >> x;
    if(op == 1) toggle(1, n, dfn[x], 1, 1, 0);
    if(op == 2) {
      modify(1, n, dfn[x], dfn[x] + sz[x] - 1, 1);
      dat cur = {0, -1};
      int u = fa[x];
      while(u) cur = query(1, n, dfn[top[u]], dfn[u], 1) + cur, u = fa[top[u]];
      if(cur.suf >= 0) toggle(1, n, dfn[x], 1, -cur.suf - 1, 1);
    }
    if(op == 3) {
      dat cur = {0, -1};
      while(x && cur.suf < 0) cur = query(1, n, dfn[top[x]], dfn[x], 1) + cur, x = fa[top[x]];
      if(cur.suf >= 0) puts("black");
      else puts("white");
    }
  }
  cerr << TIME << " ms\n";
  return 0;
}
/*
2022/9/8
author: Alex_Wei
start coding at 13:00
finish debugging at 13:45
*/