3.CF343D Water Tree 树剖+线段树区间覆盖

3.CF343D Water Tree 树剖+线段树区间覆盖

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

线段树维护树上覆盖问题，树剖序列化维护序列覆盖。

洛谷传送门：CF343D Water Tree - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

CF传送门：D. Water Tree (codeforces.com)

题目分析

给出一棵以 1 1 1 为根节点的 n n n 个节点的有根树。每个点有一个权值，初始为 0 0 0。

• m m m 次操作。操作有 3 3 3 种：
  1. 将点 u u u 和其子树上的所有节点的权值改为 1 1 1。
  2. 将点 u u u 到 1 1 1 的路径上的所有节点的权值改为 0 0 0。
  3. 询问点 u u u 的权值。

树上问题序列化，树剖一下，线段树维护区间 0 − 1 0-1 0−1推平操作

1. 对应线段树区间： [ d f n [ u ] , d f n [ u ] + s i z e [ u ] ] [dfn[u], dfn[u] + size[u]] [dfn[u],dfn[u]+size[u]]
2. 对应线段树区间：沿重链向上跳到根节点，至多log个区间，第一个区间： [ d f n [ t o p [ u ] ] , d f n [ u ] ] [dfn[top[u]], dfn[u]] [dfn[top[u]],dfn[u]]
3. 直接树上单点查询即可

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;

vector g[N];
int a[N];

int pfa[N], dep[N], siz[N], son[N], top[N], dfn[N], rnk[N], ind;

void dfs1(int u, int fa){
    pfa[u] = fa, dep[u] = dep[fa] + 1, siz[u] = 1;
    for(auto &v : g[u]){
        if(v == fa) continue;
        dfs1(v, u);
        siz[u] += siz[v];
        if(siz[v] > 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 > n >> m;
    for(int i = 1; i > a[i];
    for(int i = 1; i > u >> v;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    dfs1(1, 0), dfs2(1, 1);
    SegTree::build(1, 1, n);
    while(m--){
        int op, v; cin >> op >> v;
        if(op == 1){
            int x = 0; cin >> x;
            if(!(dep[v] & 1)) x *= -1;
            SegTree::update(SEGRG, dfn[v], dfn[v] + siz[v] - 1, x);
        } else {
            cout