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

皎月半洒花 · 2020-06-16 21:28:35 · 题解

这是真神题。

首先观察发现，操作的复杂度向修改倾斜，即询问复杂度比较低，可以考虑询问的时候搞点事情。

考虑 (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 的复杂度解决这个问题了。

#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 ;
}