CF1017G The Tree

$\text{link}$

对于询问 $\text{3 x}$ ，若操作 $\text{1 y}$ 使得 $x$ 染上了黑色，那么满足 $y$ 是 $x$ 的祖先并且 $y\longrightarrow$ 路径上操作 $1$ 的个数 $\ge$ 路径上的总点数（包括 $x,y$）。

考虑给每个点附一个权值 $-1$ ，操作 $\text{1 x}$ 则对 $x$ 单点 $+1$，那么查询时只需要判断 $x\longrightarrow rt$ 的路径上的后缀和最大值是否 $\ge 0$ 即可判断颜色，如果没有操作 $2$ 就做完了。

对于操作 $\text{2 x}$ ，将 $x$ 子树的权值覆盖为 $-1$ 可以使得子树内的点到 $x$ 的后缀和最大值正确，但是可能 $x\longrightarrow rt$ 的后缀和最大值出错，这需要将 $x$ 单点减小 “$rt\longrightarrow x$ 的后缀和最大值 + 1” ，然后就做完了。

时间复杂度 $\mathrm{O(n\log ^2 n)}$ 。

久违的 1A

$\texttt{Code:}$

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
vector<int> G[maxn];
int n, q, s[maxn], fa[maxn], depth[maxn], son[maxn], top[maxn], tms, dfn[maxn];
void dfs1(int u, int fath) {
    s[u] = 1; fa[u] = fath;
    depth[u] = depth[fath] + 1;
    for (int v : G[u]) {
        dfs1(v, u);
        s[u] += s[v];
        if (s[v] > s[son[u]]) son[u] = v;
    }
}
void dfs2(int u, int Top) {
    top[u] = Top; dfn[u] = ++tms;
    if (!son[u]) return;
    dfs2(son[u], Top);
    for (int v : G[u]) if (v ^ son[u]) dfs2(v, v);
}
namespace _Smt {
    #define ls u << 1
    #define rs u << 1 | 1
    #define lson ls, l, mid
    #define rson rs, mid + 1, r
    struct Node {
        int len, s, rx, tag;
        void ladd() {tag = 1; s = -len; rx = -1;}
    } t[maxn << 2], ept;
    Node merge(Node c, Node a, Node b) {
        c.s = a.s + b.s;
        c.rx = max(b.rx, a.rx + b.s);
        return c;
    }
    void build(int u, int l, int r) {
        t[u].len = r - l + 1;
        if (l == r) {t[u].s = t[u].rx = -1; return;}
        int mid = (l + r) >> 1;
        build(lson); build(rson);
        t[u] = merge(t[u], t[ls], t[rs]);
    }
    void pd(int u) {
        if (t[u].tag) {
            t[ls].ladd();
            t[rs].ladd();
            t[u].tag = 0;
        }
    }
    void mdf1(int u, int l, int r, int x, int y) {
        if (l == r) {t[u].s += y; t[u].rx += y; return;}
        int mid = (l + r) >> 1; pd(u);
        if (x <= mid) mdf1(lson, x, y);
            else mdf1(rson, x, y);
        t[u] = merge(t[u], t[ls], t[rs]);
    }
    void mdf2(int u, int l, int r, int x, int y) {
        if (x <= l && r <= y) {t[u].ladd(); return;}
        int mid = (l + r) >> 1; pd(u);
        if (x <= mid) mdf2(lson, x, y);
        if (y > mid) mdf2(rson, x, y);
        t[u] = merge(t[u], t[ls], t[rs]);
    }
    Node qry(int u, int l, int r, int x, int y) {
        if (x <= l && r <= y) return t[u];
        int mid = (l + r) >> 1; pd(u);
        if (y <= mid) return qry(lson, x, y);
        if (x > mid) return qry(rson, x, y);
        return merge(ept, qry(lson, x, y), qry(rson, x, y));
    }
    int ask(int u) {
        Node res = ept;
        res.rx = -1e9;
        while (top[u] ^ 1) {
            res = merge(ept, qry(1, 1, n, dfn[top[u]], dfn[u]), res);
            u = fa[top[u]];
        }
        return merge(ept, qry(1, 1, n, 1, dfn[u]), res).rx;
    }
    #undef ls
    #undef rs
    #undef lson
    #undef rson
}
using namespace _Smt;
int main() {
    scanf("%d%d", &n, &q);
    for (int i = 2; i <= n; i++) {
        int u; scanf("%d", &u);
        G[u].push_back(i);
    }
    dfs1(1, 0); dfs2(1, 1);
    build(1, 1, n);
    while (q--) {
        int opt, x; scanf("%d%d", &opt, &x);
        if (opt == 1) mdf1(1, 1, n, dfn[x], 1);
        if (opt == 2) {
            mdf2(1, 1, n, dfn[x], dfn[x] + s[x] - 1);
            mdf1(1, 1, n, dfn[x], -ask(x) - 1);
        }
        if (opt == 3) puts(ask(x) >= 0 ? "black" : "white");
    }
    return 0;
}