Propagating tree（欧拉序+线段树）

题目：

给你一棵 $n$ 个结点的有根树， $1$ 为根。结点有点权。 $m$ 个操作：
$1\space x\space val$ ：结点 $x$ 权值 $+val$ ， $x$ 的儿子们权值 $-val$ ， $x$ 的孙子们 $+val$ ...以此类推；
$2\space x$ ：询问 $x$ 当前的点权；
$n、m≤2e5$

做法：

$dfs$ 序：从根出发 $dfs$ 经过结点的顺序，每个结点只加一次，长度 $n$ 。
欧拉序：从根出发 $dfs$ 绕回根沿途经过的结点的顺序，每进入结点加一次，长度 $2n-1$ 。
这题的更新操作中，我们发现其在欧拉序中是有规律的。
图片说明
比如我们要给 $3$ 号结点 $+val$ ，在欧拉序中找到 $3$ 出现最左和最右的位置，这个区间就是以 $3$ 为根的整棵子树，我们发现按+-+-的顺序更新这个区间的点权正好满足题目要求。

再比如我们要给 $1$ 号结点 $+val$ 。

对应位置的更新完全是正确的。所以我们可以用线段树维护这个在欧拉序上+-+-的区间更新，以及单点查询。

代码：

#include <bits/stdc++.h>
#define lson rt<<1
#define rson rt<<1|1
#define IOS ios::sync_with_stdio(false), cin.tie(0)
#define debug(a) cout << #a ": " << a << endl
using namespace std;
typedef long long ll;
const int N = 2e5 + 7;
int n, m, a[N], dfn[N<<1], tag, in[N], out[N];
vector<int> g[N];
int T[N<<3], laz[N<<3];
void dfs(int u, int p){
    dfn[++tag] = u, in[u] = tag;
    for (auto &v : g[u]) if (v != p){
        dfs(v, u);
        dfn[++tag] = u;
    }
    out[u] = tag;
}
void pushdown(int l, int r, int rt){
    int val = laz[rt]; laz[rt] = 0;
    int mid = (l+r) >> 1, f = ((mid-l)&1 ? 1 : -1);
    T[lson] += val, laz[lson] += val;
    T[rson] += f*val, laz[rson] += f*val;
}
void build(int l, int r, int rt){
    if (l == r){
        T[rt] = a[dfn[l]]; return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, lson); build(mid+1, r, rson);
}
void update(int L, int R, int val, int l, int r, int rt){
    if (L == l && r == R){
        T[rt] += val;
        laz[rt] += val; return;
    }
    if (laz[rt] != 0) pushdown(l, r, rt);
    int mid = (l+r) >> 1;
    if (R <= mid){
        update(L, R, val, l, mid, lson);
    }else if (L > mid){
        update(L, R, val, mid+1, r, rson);
    }else{
        update(L, mid, val, l, mid, lson);
        update(mid+1, R, ((mid-L)&1 ? val : -val), mid+1, r, rson);
    }
}
int query(int x, int l, int r, int rt){
    if (l == r) return T[rt];
    if (laz[rt] != 0) pushdown(l, r, rt);
    int mid = (l+r) >> 1;
    if (x <= mid) return query(x, l, mid, lson);
    if (x > mid) return query(x, mid+1, r, rson);
}
int main(void){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    for (int i = 0; i < n-1; ++i){
        int u, v; scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    build(1, tag, 1);
    while (m--){
        int op, x, val;
        scanf("%d%d", &op, &x);
        if (op == 1){
            scanf("%d", &val);
            update(in[x], out[x], val, 1, tag, 1);
        }else{
            printf("%d\n", query(in[x], 1, tag, 1));
        }
    }
    return 0;
}