题面

题目链接

大秦 为你打开 题目传送门

题目翻译

给定一棵点数为 $N$ 的树，节点从 $1$ 到 $N$ 编号，以点 $1$ 为根，每个点有权值。

对树进行 $M$ 个操作，操作有两种：

  1. $1\ u\ val$ ：把节点 $u$ 的权值增加 $val$ ，$u$ 的儿子节点权值增加 $−val$ ，$u$ 的儿子的儿子的节点权值增加 $−(−val)$ ，依此类推。

  2. $2\ u$ ：查询节点 $u$ 的权值。

思路

这个加减加减的，很不好处理，网上大多数做法都是维护两颗线段树，这里提供一个不一样的做法。

我们考虑让深度为奇数的根的子树修改的时候直接加 val，偶数的直接减去 val。这样我们就消除了所加的子树根结点深度不同的问题，所以我们的懒标记就可以合并了。

因为先前我们对深度不同的结点做出的调整，所以最后我们只需要在访问到每个点的时候判断一下深度的奇偶性，对应的加减就行了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef __int128 int128;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 2e5 + 10;
const int M = 4e5 + 10;

class Graph {
private :
    struct Edge {
        int to, nt, wt;
        Edge() {}
        Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
    }e[M];
    int hd[N], cnte;
public :
    inline void AddEdge(int u, int v, int w = 0) {
        e[++cnte] = Edge(v, hd[u], w);
        hd[u] = cnte;
    }
    inline int head(int u) { return hd[u]; }
    inline int nt(int u) { return e[u].nt; }
    inline int to(int u) { return e[u].to; }
    inline int wt(int u) { return e[u].wt; }
};

struct Node {
    int L, R;
    ll val, lazy;
    Node() {}
    Node(int L, int R, ll val, ll lazy) : L(L), R(R), val(val), lazy(lazy) {}
    inline Node operator + (const Node & b) const {
        return Node(min(L, b.L), max(R, b.R), val + b.val, 0);
    }
};
class SegTree {
private :
    Node node[N << 2];
public :
    inline void Add(int p, int v) {
        node[p].val += 1LL * (node[p].R - node[p].L + 1) * v;
        node[p].lazy += v;
    }
    inline void PushDown(int p) {
        if(node[p].lazy == 0) return ;
        Add(p << 1, node[p].lazy);
        Add(p << 1 | 1, node[p].lazy);
        node[p].lazy = 0;
    }
    inline void Build(int p, int L, int R) {
        node[p] = Node(L, R, 0, 0);
        if(L == R) return ;
        int mid = L + R >> 1;
        Build(p << 1, L, mid), Build(p << 1 | 1, mid + 1, R);
        node[p] = node[p << 1] + node[p << 1 | 1];
    }
    inline void Modify(int p, int L, int R, int v) {
        // cout << node[p].L << ' ' << node[p].R << endl;
        if(L <= node[p].L && node[p].R <= R) {
            Add(p, v);
            return ;
        }
        PushDown(p);
        int mid = node[p].L + node[p].R >> 1;
        if(L <= mid) Modify(p << 1, L, R, v);
        if(mid < R) Modify(p << 1 | 1, L, R, v);
        node[p] = node[p << 1] + node[p << 1 | 1];
    }
    inline ll Query(int p, int x) {
        if(node[p].L == node[p].R) {
            return node[p].val;
        }
        PushDown(p);
        int mid = node[p].L + node[p].R >> 1;
        if(x <= mid) return Query(p << 1, x);
        else return Query(p << 1 | 1, x);
    }
};

int n, Q;
ll a[N];
Graph G;

int it[N], ot[N], cntd;
int dep[N];
SegTree tree;

inline void Input() {
    read(n, Q);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
    int u, v;
    for(int i = 1; i < n; i++) {
        read(u, v);
        G.AddEdge(u, v);
        G.AddEdge(v, u);
    }
}

void Dfs(int u, int fa) {
    dep[u] = dep[fa] + 1;
    it[u] = ++cntd;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(v == fa) continue;
        Dfs(v, u);
    }
    ot[u] = cntd;
}

inline void Work() {
    Dfs(1, 0);
    tree.Build(1, 1, n);
    int op, x, y;
    while(Q--) {
        read(op, x);
        if(op == 1) {
            read(y);
            int flag = dep[x] & 1 ? -1 : 1;
            tree.Modify(1, it[x], ot[x], y * flag);
        }
        else {
            int flag = dep[x] & 1 ? -1 : 1;
            int ans = tree.Query(1, it[x]);
            printf("%lld\n", a[x] + ans * flag);
        }
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}