代码如下
```cpp
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10, M = 2 * N;
int n, m;
int h[N], e[M], ne[M], idx;
int w[N], dep[N], fa[N], son[N], sz[N];
int top[N], nw[N], id[N], cnt;
struct warma
{
int l, r;
LL sum, add;
} tr[N * 4];
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
return;
}
void dfs1(int u, int father, int depth)
{
fa[u] = father;
dep[u] = depth;
sz[u] = 1;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == father) continue;
dfs1(j, u, depth + 1);
sz[u] += sz[j];
if (sz[son[u]] < sz[j]) son[u] = j;
}
return;
}
void dfs2(int u, int t)
{
id[u] = ++ cnt;
nw[cnt] = w[u];
top[u] = t;
if (!son[u]) return;
dfs2(son[u], t);
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == son[u] || j == fa[u]) continue;
dfs2(j, j);
}
return;
}
void pushup(int idx)
{
tr[idx].sum = tr[idx << 1].sum + tr[idx << 1 | 1].sum;
return;
}
void eval(warma &t, LL ad)
{
t.add += ad;
t.sum += (t.r - t.l + 1) * ad;
return;
}
void pushdown(int idx)
{
if (tr[idx].add)
{
eval(tr[idx << 1], tr[idx].add);
eval(tr[idx << 1 | 1], tr[idx].add);
tr[idx].add = 0;
}
return;
}
void build(int idx, int L, int R)
{
if (L == R) tr[idx] = {L, R, nw[R], 0};
else
{
tr[idx] = {L, R, 0, 0};
int mid = L + R >> 1;
build(idx << 1, L, mid);
build(idx << 1 | 1, mid + 1, R);
pushup(idx);
}
return;
}
void monify(int idx, int L, int R, int ad)
{
if (L <= tr[idx].l && tr[idx].r <= R) eval(tr[idx], ad);
else
{
pushdown(idx);
int mid = tr[idx].l + tr[idx].r >> 1;
if (L <= mid) monify(idx << 1, L, R, ad);
if (R > mid) monify(idx << 1 | 1, L, R, ad);
pushup(idx);
}
return;
}
LL query(int idx, int L, int R)
{
if (L <= tr[idx].l && tr[idx].r <= R) return tr[idx].sum;
else
{
pushdown(idx);
LL res = 0;
int mid = tr[idx].l + tr[idx].r >> 1;
if (L <= mid) res = query(idx << 1, L, R);
if (R > mid) res += query(idx << 1 | 1, L, R);
return res;
}
}
void point_monify(int idx, int pos, int val)
{
if (tr[idx].l == tr[idx].r && tr[idx].l == pos) tr[idx].sum += val;
else
{
pushdown(idx);
int mid = tr[idx].l + tr[idx].r >> 1;
if (pos <= mid) point_monify(idx << 1, pos, val);
else point_monify(idx << 1 | 1, pos, val);
pushup(idx);
}
return;
}
void tree_monify(int x, int val)
{
monify(1, id[x], id[x] + sz[x] - 1, val);
return;
}
LL path_query(int u, int v)
{
LL res = 0;
while (top[u] != top[v])
{
if (dep[top[u]] < dep[top[v]]) swap(u, v);
res += query(1, id[top[u]], id[u]);
u = fa[top[u]];
}
if (dep[u] < dep[v]) swap(u, v);
res += query(1, id[v], id[u]);
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i ++ ) cin >> w[i];
for (int i = 1; i < n; i ++ )
{
int a, b;
cin >> a >> b;
add(a, b);
add(b, a);
}
dfs1(1, -1, 1);
dfs2(1, 1);
build(1, 1, n);
while (m -- )
{
int opt;
cin >> opt;
if (opt == 1)
{
int pos, val;
cin >> pos >> val;
point_monify(1, pos, val);
}
else if (opt == 2)
{
int x, val;
cin >> x >> val;
tree_monify(x, val);
}
else
{
int x;
cin >> x;
cout << path_query(1, x) << endl;
}
}
return 0;
}
```
by LittleMoMol @ 2022-08-15 19:54:18
树上差分不比树剖好写
by ppip @ 2022-08-15 20:14:14
@[ppip](/user/374433) 树上差分能过？
by jor蛋 @ 2022-11-18 20:20:23
@[jor蛋](/user/72921) 可做啊，用一个线段树维护，单log的
by ppip @ 2022-11-18 21:00:36