树剖后线段树维护。
此题要修改子树的权，根据树剖性质子树是连续的一段，运用时间戳思想即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i, j, k) for (i=(j);i<=(k);i++)
#define fd(i, k, j) for (i=(k);i>=(j);i--)
#define fe(i, u) for (i=head[u];i!=-1;i=e[i].next)
#define rd(a) scanf("%d", &a)
#define rd2(a, b) scanf("%d%d", &a, &b)
#define rd3(a, b, c) scanf("%d%d%d", &a, &b, &c)
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "bzoj4034"
using namespace std;
const int MAXN = 100000 + 5;
int n, m, head[MAXN], wi[MAXN], cnt;
struct data{int to, next;}e[MAXN*2];
int p[MAXN], top[MAXN], son[MAXN], siz[MAXN], fa[MAXN], dep[MAXN], pre, ll[MAXN], rr[MAXN];
void dfs1(int u, int pa) {
int i;
fa[u] = pa, dep[u] = dep[pa] + 1, siz[u] = 1;
fe (i, u) {
int v = e[i].to;
if (v!=pa) {
dfs1(v, u);
siz[u] += siz[v];
if (son[u]==-1||siz[son[u]]<siz[v]) son[u] = v;
}
}
}
void dfs2(int u, int chain) {
int i;
p[u] = ++pre, top[u] = chain, ll[u] = pre;
if (son[u]!=-1) {
dfs2(son[u], chain);
fe (i, u) {
int v = e[i].to;
if (v!=fa[u]&&v!=son[u]) dfs2(v, v);
}
}
rr[u] = pre;
}
LL sumv[MAXN*4], addv[MAXN*4];
#define lc (o<<1)
#define rc (o<<1|1)
#define M ((l+r)>>1)
void pushup(LL o) {
sumv[o] = sumv[lc] + sumv[rc];
}
void pushdown(int o,int len) {
if (addv[o]) {
addv[lc] += addv[o], addv[rc] += addv[o];
sumv[lc] += addv[o] * (len-len/2), sumv[rc] += addv[o] * (len/2);
addv[o] = 0;
}
}
void update(int o, int l, int r, int x, int y, LL v) {
if (x<=l&&r<=y) {
addv[o] += v;
sumv[o] += (r-l+1) * v;
return ;
}
pushdown(o, r-l+1);
if (x<=M) update(lc,l,M,x,y,v);
if (M<y) update(rc,M+1,r,x,y,v);
pushup(o);
}
LL query(int o, int l, int r, int x, int y) {
LL ret = 0;
if (x<=l&&r<=y) {
return sumv[o];
}
pushdown(o, r-l+1);
if (x<=M) ret += query(lc,l,M,x,y);
if (M<y) ret += query(rc,M+1,r,x,y);
return ret;
}
LL findSUM(int u, int v) {
int f1 = top[u], f2 = top[v]; LL ret = 0;
while (f1!=f2) {
if (dep[f1]<dep[f2]) swap(f1, f2), swap(u, v);
ret += query(1,1,n,p[f1],p[u]);
u = fa[f1], f1 = top[u];
}
if (dep[u]<dep[v]) swap(u, v);
return ret+query(1,1,n,p[v],p[u]);
}
void ins(int u, int v) {
cnt++, e[cnt].to = v, e[cnt].next = head[u], head[u] = cnt;
cnt++, e[cnt].to = u, e[cnt].next = head[v], head[v] = cnt;
}
void init() {
int i; cnt = pre = 0;
fo (i, 1, n) rd(wi[i]);
fo (i, 1, n) head[i] = -1, p[i] = 0, top[i] = 0, son[i] = -1, siz[i] = 0, fa[i] = 0, dep[i] = 0, ll[i] = rr[i] = 0;
fo (i, 1, n*2) e[i].to = 0, e[i].next = -1;
fo (i, 1, n*4) sumv[i] = addv[i] = 0;
fo (i, 1, n-1) {
int u, v; rd2(u, v);
ins(u, v);
}
}
void solve() {
int i;
dfs1(1, 0), dfs2(1, 1);
fo (i, 1, n) update(1,1,n,p[i],p[i],wi[i]);
fo (i, 1, m) {
int opt, x, a; rd(opt);
if (opt==1) {
rd2(x, a);
update(1,1,n,p[x],p[x],a);
} else if (opt==2) {
rd2(x, a);
update(1,1,n,ll[x],rr[x],a);
} else if (opt==3) {
rd(x);
printf("%lld\n", findSUM(x, 1));
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen(FN2".in","r",stdin);freopen("1.out","w",stdout);
#endif
while (rd2(n, m)==2) init(), solve();
return 0;
}
