题面

大秦为你打开题目传送门

题目描述

有一棵点数为 $N$ 的树，以点 $1$ 为根，且树有点权。然后有 $M$ 个操作，分为三种：

  • 操作 $1$：把某个节点 $x$ 的点权增加 $a$。
  • 操作 $2$：把某个节点 $x$ 为根的子树中所有点的点权都增加 $a$。
  • 操作 $3$：询问某个节点 $x$ 到根的路径中所有点的点权和。

输入格式

第一行包含两个整数 $N,M$。表示点数和操作数。
接下来一行 $N$ 个整数，表示树中节点的初始权值。
接下来 $N-1$ 行每行两个正整数 $\mathit{from},\mathit{to}$， 表示该树中存在一条边 $(\mathit{from},\mathit{to})$。
再接下来 $M$ 行，每行分别表示一次操作。其中第一个数表示该操作的种类，之后接这个操作的参数。

输出格式

对于每个询问操作，输出该询问的答案。答案之间用换行隔开。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
5 5
1 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3

样例输出 #1

1
2
3
6
9
13

提示

对于 $100\%$ 的数据，$1\le N,M\le10^5$，且所有输入数据的绝对值都不会超过 $10^6$。

题意

非常的简单，直接树剖上去秒了。

代码

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
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
#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 = 1e5 + 10;
const int M = 2e5 + 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; }
};

int n, m;
int a[N];
Graph G;

int it[N], ot[N], hsh[N << 2], cntd;

int dep[N], fa[N], ct[N], mx[N];
int top[N];

class SegTree {
private:
    struct Node {
        int l, r;
        long long sum;
        long long lazy;
    }node[N << 2];

public:
    void Add(int p, long long v) {
        node[p].sum += v * (node[p].r - node[p].l + 1);
        node[p].lazy += v;
    }
    void DownAdd(int p) {
        if (node[p].lazy == 0) return;
        Add(p * 2, node[p].lazy);
        Add(p * 2 + 1, node[p].lazy);
        node[p].lazy = 0;
    }
    void Build(int p, int l, int r) {
        node[p] = { l, r, 0, 0 };
        if (l == r) {
            node[p].sum = a[hsh[l]];
            return;
        }
        int mid = (l + r) >> 1;
        Build(p * 2, l, mid);
        Build(p * 2 + 1, mid + 1, r);
        node[p].sum = node[p * 2].sum + node[p * 2 + 1].sum;
    }
    void ModifyRange(int p, int L, int R, long long v) {
        if (L <= node[p].l && node[p].r <= R) {
            Add(p, v);
            return;
        }
        DownAdd(p);
        int mid = (node[p].l + node[p].r) >> 1;
        if (L <= mid) ModifyRange(p * 2, L, R, v);
        if (mid < R) ModifyRange(p * 2 + 1, L, R, v);
        node[p].sum = node[p * 2].sum + node[p * 2 + 1].sum;
    }
    long long QueryRange(int p, int L, int R) {
        if (L <= node[p].l && node[p].r <= R) {
            return node[p].sum;
        }
        DownAdd(p);
        int mid = (node[p].l + node[p].r) >> 1;
        long long sum = 0;
        if (L <= mid) sum += QueryRange(p * 2, L, R);
        if (mid < R) sum += QueryRange(p * 2 + 1, L, R);
        return sum;
    }
};

SegTree tree;

inline void Input() {
    read(n, m);
    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 x, int f) {
    dep[x] = dep[f] + 1;
    fa[x] = f;
    ct[x] = 1, mx[x] = 0;
    for (int i = G.head(x); i; i = G.nt(i)) {
        int v = G.to(i);
        if (v == f) continue;
        dfs(v, x);
        ct[x] += ct[v];
        if (ct[v] > ct[mx[x]]) mx[x] = v;
    }
}

void Dfs(int x, int t) {
    top[x] = !t ? x : top[fa[x]];
    it[x] = ++cntd;
    hsh[cntd] = x;
    if (mx[x]) Dfs(mx[x], 1);
    for (int i = G.head(x); i; i = G.nt(i)) {
        int v = G.to(i);
        if (v == fa[x] || v == mx[x]) continue;
        Dfs(v, 0);
    }
    ot[x] = cntd;
}

long long Getanswer(int x, int y) {
    long long ans = 0;
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        ans += tree.QueryRange(1, it[top[x]], it[x]);
        x = fa[top[x]];
    }
    if (dep[x] > dep[y]) swap(x, y);
    return ans + tree.QueryRange(1, it[x], it[y]);
}

inline void Work() {
    dfs(1, 0);
    Dfs(1, 0);
    tree.Build(1, 1, n);
    int op, x, v;
    while (m--) {
        read(op, x);
        if (op == 3) {
            printf("%lld\n", Getanswer(1, x));
        }
        else {
            read(v);
            tree.ModifyRange(1, it[x], op == 1 ? it[x] : ot[x], v);
        }
    }
}

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