#\(\mathcal{\color{red}{Description}}\)

一道\(zz\)的树剖题\(qwq\)。

#\(\mathcal{\color{red}{Solution}}\)

我天\(NOI\)怎么可能有这种水题啊……

很显然的就是线段树区间染色 + 统计根到每个节点的距离 + 子树和 + 修改子树 ……

纯纯的板子啊！

\(emmmmm\)于是这道题就完了~

#include 
    
     #include 
     
      #include 
      
       #define il inline#define MAXN 200010#define ls(x) (x << 1)#define rs(x) (x << 1 | 1)#define mid ((l + r) >> 1)using namespace std ;char in[30] ;vector 
       
         sons[MAXN] ; int Id[MAXN], tot ;int dis[MAXN << 1], s[MAXN << 1], tag[MAXN << 1], i ; int N, M, In, fa[MAXN], dep[MAXN], Top[MAXN], sub[MAXN], hs[MAXN] ;inline int qrr(){    int k = 0 ; char c = getchar() ;    while (c < '0' || c > '9') c = getchar() ;    while (c <= '9' && c >= '0') k = (k << 1) + (k << 3) + c - 48, c = getchar() ;    return k ;}void _dfs1(int deep, int now, int f){    dep[now] = deep, fa[now] = f ; sub[now] = 1 ;    int _hs = -1 ;    for (int k = 0 ; k < sons[now].size() ; ++ k){        _dfs1(deep + 1, sons[now][k], now) ;        sub[now] += sub[sons[now][k]] ;        if(sub[sons[now][k]] > _hs)             _hs = sub[sons[now][k]], hs[now] = sons[now][k] ;    }}void _dfs2(int now, int Tp){    Top[now] = Tp, Id[now] = ++ tot ;    if (!hs[now]) return ;    _dfs2(hs[now], Tp) ;    for (int k = 0 ; k < sons[now].size() ; ++ k){        if (sons[now][k] == hs[now]) continue ;        _dfs2(sons[now][k], sons[now][k]) ;    }}void build(int rt, int l, int r){    if (l == r) {dis[rt] = 1 ; return  ;}    build(ls(rt), l, mid) ;    build(rs(rt), mid + 1, r) ;    dis[rt] = dis[ls(rt)] + dis[rs(rt)] ; }il void p_d(int rt, int l, int r){    if(tag[rt] != -1){        s[ls(rt)] = (mid - l + 1) * tag[rt] ;        s[rs(rt)] = (r - mid) * tag[rt] ;        tag[ls(rt)] = tag[rs(rt)] = tag[rt] ;        tag[rt] = -1 ;    }}int query_D(int rt, int l, int r, int ql, int qr){    int res = 0 ;    if (ql <= l && r <= qr){res += dis[rt] ; return res ;}    if (ql <= mid) res += query_D(ls(rt), l, mid, ql, qr) ;    if (qr > mid) res += query_D(rs(rt), mid + 1, r, ql, qr) ;    return res ;  }int query_C(int rt, int l, int r, int ql, int qr){    int res = 0 ;    if (ql <= l && r <= qr){res += s[rt] ; return res ;}    p_d(rt, l, r) ;    if (ql <= mid) res += query_C(ls(rt), l, mid, ql, qr) ;    if (qr > mid) res += query_C(rs(rt), mid + 1, r, ql, qr) ;    return res ;  }void update_C(int rt, int l, int r, int ul, int ur, int k){    if (ul <= l && r <= ur){         s[rt] = (r - l + 1) * k ;         tag[rt] = k ;         return  ;     }     p_d(rt, l, r) ;    if (ul <= mid) update_C(ls(rt), l, mid, ul, ur, k) ;    if (ur > mid) update_C(rs(rt), mid + 1, r, ul, ur, k) ;    s[rt] = s[rs(rt)] + s[ls(rt)] ;} inline void qv(int now){    int ans = 0, dif = 0 ;    while (Top[now] != Top[1]){        ans += query_D(1, 1, N, Id[Top[now]], Id[now]) ;        dif += query_C(1, 1, N, Id[Top[now]], Id[now]) ;        now = fa[Top[now]] ;    }    ans += query_D(1, 1, N, 1, Id[now]) ;    dif += query_C(1, 1, N, 1, Id[now]) ;    printf("%d\n", ans - dif) ;}inline void uv(int now){    while (Top[now] != Top[1]){        update_C(1, 1, N, Id[Top[now]], Id[now], 1) ;        now = fa[Top[now]] ;    }    update_C(1, 1, N, 1, Id[now], 1) ;}int main(){    //freopen("manager.in", "r", stdin) ;    //freopen("manager.out", "w", stdout) ;    N = qrr() ;    fill (tag + 1, tag + (MAXN << 1) + 1, -1) ;     for (i = 2; i <= N ;i ++){        fa[i] = qrr() + 1,         sons[fa[i]].push_back(i) ;    } M = qrr() ;     _dfs1(1, 1, 0), _dfs2(1, 1), build(1, 1, N) ;    for (i = 1; i <= M ; i ++){        scanf("%s", in) ;        if (in[0] == 'u'){            In = qrr() + 1 ;            printf("%d\n", query_C(1, 1, N, Id[In], Id[In] + sub[In] - 1)) ;            update_C(1, 1, N, Id[In], Id[In]+ sub[In] - 1, 0) ;            continue ;          }        In = qrr() + 1 ;        qv(In), uv(In) ;    }}

番外：以下是三次评测：