「有趣的链剖题」 [Codeforces 1017G] The Tree

这是真神题。 首先观察发现，操作的复杂度向修改倾斜，即询问复杂度比较低，可以考虑询问的时候搞点事情。 考虑 $(1)$ 操作的本质。因为要向询问倾斜，所以考虑如果某个点 $z$ 会被 `1 x` 影响到 ，那么必然有 $x\sim z$ 这条路径上除了 $x$ 之外的所有点都已经被染黑了。 考虑忽略 $(2)$ 操作时，如何通过维护权值实现这个事情。一开始将全部的点权设为 $0$，每次 $(1)$ 操作就是对该点进行单点 $+1$ 。这样询问就可以考虑询问 $root\to x$ 这条路径上，是否存在一个后缀 $(s,x)$ 的权和等于 $(s,x)$ 的长度。这样直接做本质上是一个树链上的线段树二分，但其实可以用一个比较传统的技巧优化这个过程，即差分。考虑把每个点的初始点权设为 $-1$ ，这样就是询问是否存在一个后缀，其和 $\geqslant 0$ 。这个可以通过维护链上的最大后缀和来做，写起来简单一些。 然后考虑加上 $(2)$ 操作后如何快速维护。发现 $(2)$ 操作的本质是让整棵子树的点权均变为 $-1$ 。但这还不够，因为 $(2)$ 本质上是强制让某个点 $x$ 变成白色，而上面那个做法本质上是对修改离线，最后再分别确定每个修改对答案的贡献。不过也有比较简单的解决方式，即让 `2 x` 中的 $x$ 单点减一个权值 $v$ ，使得 $root\to x$ 上的最大后缀和也为 $-1$ 。不难发现 $v=qry(x)+1$ 。 于是最后就可以用 $n\log ^2n $ 的复杂度解决这个问题了。 ```cpp #include <cstdio> #include <vector> #include <cstring> #define p_b push_back using std :: max ; using std :: min ; using std :: vector ; const int N = 300010 ; int ans ; int cnt ; int n, q ; int sz[N] ; int fa[N] ; int _id[N] ; int dfn[N] ; int son[N] ; int dep[N] ; int top[N] ; vector <int> E[N] ; void dfs1(int x, int da){ dep[x] = dep[da] + 1 ; sz[x] = 1, fa[x] = da ; for (auto y : E[x]){ if (y == da) continue ; dfs1(y, x) ; sz[x] += sz[y] ; if (sz[y] > sz[son[x]]) son[x] = y ; } } void dfs2(int x, int tp){ top[x] = tp ; ++ cnt ; _id[dfn[x] = cnt] = x ; if (son[x]) dfs2(son[x], tp) ; for (auto y : E[x]) if (y != fa[x] && y != son[x]) dfs2(y, y) ; } int seg[N * 3] ; int val[N * 3] ; int tag[N * 3] ; #define lc (rt << 1) #define rc (rt << 1 | 1) void _up(int rt){ seg[rt] = seg[lc] + seg[rc] ; val[rt] = max(val[rc], val[lc] + seg[rc]) ; } void _down(int rt, int l, int r){ if (!tag[rt]) return ; int mid = (l + r) >> 1 ; seg[rc] = - (r - mid) ; seg[lc] = - (mid - l + 1) ; val[lc] = -1, val[rc] = -1 ; tag[rc] = tag[lc] = 1, tag[rt] = 0 ; } void build(int rt, int l, int r){ if (l == r) return void(seg[rt] = val[rt] = -1) ; int mid = (l + r) >> 1 ; build(rc, mid + 1, r) ; build(lc, l, mid) ; _up(rt) ; } void upd(int rt, int l, int r, int p, int v){ if (l == r){ seg[rt] += v ; val[rt] += v ; return void() ; } _down(rt, l, r) ; int mid = (l + r) >> 1 ; if (p <= mid) upd(lc, l, mid, p, v) ; else upd(rc, mid + 1, r, p, v) ; _up(rt) ; } void cov(int rt, int l, int r, int cl, int cr){ if (cl <= l && r <= cr){ seg[rt] = - (r - l + 1) ; val[rt] = -1 ; return void(tag[rt] = 1) ; } int mid = (l + r) >> 1 ; _down(rt, l, r) ; if (cr > mid) cov(rc, mid + 1, r, cl, cr) ; if (cl <= mid) cov(lc, l, mid, cl, cr) ; _up(rt) ; } int sum(int rt, int l, int r, int ql, int qr){ if (ql <= l && r <= qr) return seg[rt] ; int mid = (l + r) >> 1, ret = 0 ; _down(rt, l, r) ; if (ql <= mid) ret += sum(lc, l, mid, ql, qr) ; if (qr > mid) ret += sum(rc, mid + 1, r, ql, qr) ; return ret ; } int qry(int rt, int l, int r, int ql, int qr){ _down(rt, l, r) ; if (ql <= l && r <= qr) return val[rt] ; int mid = (l + r) >> 1, ret = - n ; _down(rt, l, r) ; if (ql <= mid) ret = max(ret, qry(lc, l, mid, ql, qr)) ; if (qr > mid) ret = max(ret + sum(rc, mid + 1, r, ql, qr), qry(rc, mid + 1, r, ql, qr)) ; return ret ; } int Q(int x){ int ret, v = 0 ; ret = -(n + 1) ; while (top[x] > 1){ ret = max(ret, v + qry(1, 1, n, dfn[top[x]], dfn[x])) ; v += sum(1, 1, n, dfn[top[x]], dfn[x]) ; x = fa[top[x]] ; } // printf("%d\n", qry(1, 1, n, dfn[top[x]], dfn[x])) ; ret = max(ret, v + qry(1, 1, n, 1, dfn[x])) ; return ret ; } int main(){ scanf("%d%d", &n, &q) ; int x, z ; for (int y = 2 ; y <= n ; ++ y) scanf("%d", &x), E[x].p_b(y), E[y].p_b(x) ; dfs1(1, 0) ; dfs2(1, 1) ; build(1, 1, n) ; // for (int i = 1 ; i <= n ; ++ i) printf("%d%c", top[i], " \n"[i == n]) ; // printf("%d %d\n", i, sz[i]) ; while (q --){ scanf("%d%d", &z, &x) ; if (z == 1) upd(1, 1, n, dfn[x], 1) ; else if (z == 2){ cov(1, 1, n, dfn[x], dfn[x] + sz[x] - 1) ; upd(1, 1, n, dfn[x], - Q(x) - 1) ; } else if (z == 3){ // printf("%d\n", Q(x)) ; ans = (bool)(Q(x) >= 0) ; puts(ans ? "black" : "white") ; } } return 0 ; } ```