22.CF877E Danil and a Part-time Job

22.CF877E Danil and a Part-time Job

个人Limitの线段树题单题解主目录：Limitの线段树题单 题解目录_HeartFireY的博客-CSDN博客

要求支持子树 01 01 01反转，子树求和。

树剖序列化一下，然后按照 0 − 1 0-1 0−1序列反转板子来就可以。

洛谷传送门：CF877E Danil and a Part-time Job - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：E. Danil and a Part-time Job (codeforces.com)

题目分析

大水题

有一棵 n n n 个点的树，根结点为 1 1 1 号点，每个点的权值都是 1 1 1 或 0 0 0

共有 m m m 次操作，操作分为两种

• g e t get get 询问一个点 x x x 的子树里有多少个 1 1 1

• p o w pow pow 将一个点 x x x 的子树中所有节点取反

对于每个 g e t get get 给出答案

首先树剖将树序列化，然后建线段树维护 0 − 1 0-1 0−1序列反转(建树初始化标记为 − 1 -1 −1，然后下放容斥即可)。

如上图，我们对一颗树求 d f n dfn dfn序及子树 s i z siz siz，不难发现同一子树内编号连续，那么可以将树映射到线段树上的连续区间， r t rt rt的子树就可以表示为 d f n [ r t ] + s i z [ r t ] − 1 dfn[rt] + siz[rt] - 1 dfn[rt]+siz[rt]−1。

属于非常经典的树上问题序列化且非常板。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 2e5 + 10, MOD = 1e9 + 7;

//快读板子

namespace ffastIO {
    inline int read(){
        int f = 1, x = 0; char s = getchar(); 
        while(s  '9'){ if(s == '-') f = -1; s = getchar(); } 
        while(s >= '0' && s  siz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp){
    dfn[u] = ++ind, rnk[ind] = u, top[u] = tp;
    if(!son[u]) return;
    dfs2(son[u], tp);
    for(auto & v: g[u]){
        if(v == pfa[u] || v == son[u]) continue;
        dfs2(v, v);
    }
}


namespace SegTree{
    #define ls rt  1;
        if(mid >= L) flip(lson, L, R);
        if(mid = L && r > 1, ans = 0;
        if(mid >= L) ans += query(lson, L, R);
        if(mid  v;
        g[v].emplace_back(i);
    }
    for(int i = 1; i  op;
        int st = read();
        if(op[0] == 'g') cout