树链剖分固然可以搞。
但还有另一种做法，可以看出，增加一个节点的权值会对以它为根的整棵子树都有影响，相当于给整棵子树增加一个值。
而给以某一节点 x 为根的子树增加一个权值也会影响当前子树，节点 y 所增加的值为 dis[y] * z - (dis[x] - 1) * z，每个节点都会增加 -(dis[x] - 1) * z ，
询问时只用加上 dis[y] * y 和当前节点 y 的权值。
给整棵子树增加一个权值可以用 dfs 序 + 线段树搞， dis 数组可以预处理出来。
——代码
#include <cstdio>
#include <cstring>
#define LL long long
#define root 1, 1, n
#define ls now << 1, l, mid
#define rs now << 1 | 1, mid + 1, r using namespace std; const int MAXN = ;
int n, m, cnt, tot;
int head[MAXN], next[MAXN << ], to[MAXN << ], tid[MAXN], size[MAXN];
LL a[MAXN << ], b[MAXN << ], val[MAXN], dis[MAXN]; inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void dfs(int u)
{
int i, v;
tid[u] = ++tot;
size[u] = ;
for(i = head[u]; i != -; i = next[i])
{
v = to[i];
if(!size[v])
{
dis[v] = dis[u] + ;
dfs(v);
size[u] += size[v];
}
}
} inline void push_down(int now)
{
a[now << ] += a[now];
a[now << | ] += a[now];
b[now << ] += b[now];
b[now << | ] += b[now];
a[now] = b[now] = ;
} inline void update(LL x, LL y, int ql, int qr, int now, int l, int r)
{
if(ql <= l && r <= qr)
{
a[now] += x;
b[now] += y;
return;
}
push_down(now);
int mid = (l + r) >> ;
if(ql <= mid) update(x, y, ql, qr, ls);
if(mid < qr) update(x, y, ql, qr, rs);
} inline LL query(int u, int x, int now, int l, int r)
{
if(l == r) return dis[u] * a[now] + b[now];
push_down(now);
int mid = (l + r) >> ;
if(x <= mid) return query(u, x, ls);
else return query(u, x, rs);
} int main()
{
int i, x, z;
LL y;
scanf("%d %d", &n, &m);
for(i = ; i <= n; i++) scanf("%lld", &val[i]);
memset(head, -, sizeof(head));
for(i = ; i < n; i++)
{
scanf("%d %d", &x, &y);
add(x, y);
add(y, x);
}
dis[] = ;
dfs();
for(i = ; i <= n; i++) update(, val[i], tid[i], tid[i] + size[i] - , root);
for(i = ; i <= m; i++)
{
scanf("%d %d", &z, &x);
if(z == )
{
scanf("%lld", &y);
update(, y, tid[x], tid[x] + size[x] - , root);
}
else if(z == )
{
scanf("%lld", &y);
update(y, -((dis[x] - ) * y), tid[x], tid[x] + size[x] - , root);
}
else printf("%lld\n", query(x, tid[x], root));
}
return ;
}