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
| #include <iostream>
#include <vector>
#include <bitset>
#define maxn 100010
#define lowbit(i) ((i) & (-i))
using namespace std;
struct Edge {
int to, next, w;
} e[maxn * 2]; int c1, head[maxn];
inline void add_edge(int u, int v) {
e[c1].to = v; e[c1].next = head[u]; head[u] = c1++;
}
bool vis[maxn]; int mxd[maxn];
namespace DF {
int f[maxn], sz[maxn];
int sum, rt, maxdp;
inline void init(int n) { f[rt = 0] = n + 1; fill(vis + 1, vis + n + 1, false); }
void dfs_sz(int u, int fa) {
sz[u] = 1;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa || vis[v]) continue;
dfs_sz(v, u); sz[u] += sz[v];
}
}
void dfs_maxdp(int u, int fa, int d) {
maxdp = max(maxdp, d);
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa || vis[v]) continue;
dfs_maxdp(v, u, d + 1);
}
}
void dfs(int u, int fa) {
f[u] = 0;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa || vis[v]) continue;
dfs(v, u); f[u] = max(f[u], sz[v]);
} f[u] = max(f[u], sum - sz[u]);
if (f[u] < f[rt]) rt = u;
}
inline int get_rt(int u) {
rt = maxdp = 0; dfs_sz(u, 0); sum = sz[u];
dfs(u, 0); dfs_maxdp(rt, 0, 1); mxd[rt] = maxdp; return rt;
}
};
namespace LCA {
int id[maxn * 2], in[maxn], cnt;
void init() { cnt = 0; }
void dfs(int u, int fa) {
id[++cnt] = u; in[u] = cnt;
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dfs(v, u); id[++cnt] = u;
}
}
int st[maxn * 2][21], Log[maxn * 2];
inline int st_min(int l, int r) { return in[l] < in[r] ? l : r; }
void init_st(int n) { Log[0] = -1;
for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1;
for (int i = 1; i <= n; ++i) st[i][0] = id[i];
for (int j = 1; j <= 20; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[i][j] = st_min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
inline int get(int l, int r) {
l = in[l]; r = in[r]; if (l > r) swap(l, r);
int k = Log[r - l + 1];
return st_min(st[l][k], st[r - (1 << k) + 1][k]);
}
}
int n, m, a[maxn];
int dep[maxn];
void dfs(int u, int fa) {
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (v == fa) continue;
dep[v] = dep[u] + 1; dfs(v, u);
}
}
inline int D(int x, int y) { return dep[x] + dep[y] - 2 * dep[LCA::get(x, y)]; }
struct Fenwick {
int *Bit, n;
void init(int _n) { static int P[maxn * 60], *cur = P; Bit = cur, cur += (n = _n); }
void add(int i, int v) { ++i; while (i <= n) Bit[i] += v, i += lowbit(i); }
int get_sum(int i) {
int s = 0; i = min(i + 1, n);
while (i) s += Bit[i], i -= lowbit(i);
return s;
}
} B[maxn * 2];
int f[maxn];
void divide(int u) {
vis[u] = 1; B[u].init(mxd[u]);
for (int i = head[u]; ~i; i = e[i].next) {
int v = e[i].to; if (vis[v]) continue;
v = DF::get_rt(v); f[v] = u; B[v + n].init(mxd[u]); divide(v);
}
}
void update(int u, int v) {
int x = u; B[x].add(0, v);
while (f[u]) {
int dis = D(f[u], x);
B[f[u]].add(dis, v);
B[u + n].add(dis, v);
u = f[u];
}
}
int query(int u, int k) {
int x = u, s = B[x].get_sum(k);
while (f[u]) {
int dis = D(f[u], x);
if (dis <= k) {
s += B[f[u]].get_sum(k - dis);
s -= B[u + n].get_sum(k - dis);
} u = f[u];
} return s;
}
int lans;
int main() { fill(head, head + maxn, -1);
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i < n; ++i) {
int x, y; cin >> x >> y;
add_edge(x, y); add_edge(y, x);
}
LCA::init(); LCA::dfs(1, 0); LCA::init_st(2 * n - 1);
DF::init(n); divide(DF::get_rt(1));
dep[1] = 1; dfs(1, 0);
for (int i = 1; i <= n; ++i) update(i, a[i]);
for (int i = 1, lans = 0; i <= m; ++i) {
int opt, x, y; cin >> opt >> x >> y; x ^= lans; y ^= lans;
if (!opt) cout << (lans = query(x, y)) << "\n";
else update(x, y - a[x]), a[x] = y;
}
return 0;
}
|