4.CF383C Propagating tree 线段树+树上问题

4.CF383C Propagating tree 线段树+树上问题

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

给定树，要求支持给树的单点连续反转加值，查询指定节点的权值。

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

CF传送门：C. Propagating tree (codeforces.com)

题目分析

给定树，每个点都有一个权值，你需要完成这两种操作：

1 1 1 u u u v a l val val 表示给 u u u节点的权值增加 v a l val val

2 2 2 u u u 表示查询 u u u节点的权值

它还有个神奇的性质：当某个节点的权值增加 v a l val val时，它的子节点权值都增加 − v a l -val −val，它子节点的子节点权值增加 − ( − v a l ) -(-val) −(−val)… 如此一直进行到树的底部。

对于 2 2 2操作，我们线段树 O ( l o g 2 n ) O(log_2n) O(log2​n)查询即可

对于 1 1 1操作，我们直接在xx子树这一段的线段树标记上，为了方便维护我们分情况标记

如果当前x节点深度为奇数，我们就加上val，为偶数就加上 − v a l -val −val，对于查询的节点就是深度为奇数的加上懒惰标记，深度为偶数的减去懒惰标记

实际上， t r e e tree tree和 l a z y lazy lazy可以合并， t r e e tree tree数组仅当叶节点时表示实际值，非叶节点则表示 l a z y lazy lazy标记值

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