Description
有一棵点数为 N 的树，以点 1 为根，且树点有边权。然后有 M 个操作，分为三种：
操作 1 ：把某个节点 x 的点权增加 a 。
操作 2 ：把某个节点 x 为根的子树中所有点的点权都增加 a 。
操作 3 ：询问某个节点 x 到根的路径中所有点的点权和。
Input
第一行包含两个整数 N, M 。表示点数和操作数。
接下来一行 N 个整数，表示树中节点的初始权值。
接下来 N-1 行每行三个正整数 fr, to ， 表示该树中存在一条边 (fr, to) 。
再接下来 M 行，每行分别表示一次操作。其中第一个数表示该操
作的种类（ 1-3 ） ，之后接这个操作的参数（ x 或者 x a ） 。
Output
对于每个询问操作，输出该询问的答案。答案之间用换行隔开。
Sample Input
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 2 3 4 5
1 2
1 4
2 3
2 5
3 3
1 2 1
3 5
2 1 2
3 3
Sample Output
6
9
13
9
13
HINT
对于 100% 的数据， N,M<=100000 ，且所有输入数据的绝对值都不会超过 10^6 。
Source
Solution
树链剖分，用线段树维护点权；对子树的修改就是区间修改，因为其dfs序是连续的
#include <bits/stdc++.h>
using namespace std;
struct edge
{
int v, nxt;
}e[];
struct point
{
int val, siz, fa, son, dfn, top;
}p[];
struct seg
{
long long val, lazy;
}a[];
int fst[], ptot; void addedge(int i, int u, int v)
{
e[i] = (edge){v, fst[u]}, fst[u] = i;
} void DFS1(int u)
{
p[u].siz = ;
for(int i = fst[u]; i; i = e[i].nxt)
if(p[u].fa != e[i].v)
{
p[e[i].v].fa = u;
DFS1(e[i].v);
p[u].siz += p[e[i].v].siz;
if(p[e[i].v].siz > p[p[u].son].siz)
p[u].son = e[i].v;
}
} void DFS2(int u, int top)
{
p[u].dfn = ++ptot, p[u].top = top;
if(p[u].son) DFS2(p[u].son, top);
for(int i = fst[u]; i; i = e[i].nxt)
if(e[i].v != p[u].fa && e[i].v != p[u].son)
DFS2(e[i].v, e[i].v);
} void push_up(int o, int l, int r)
{
a[o].val = a[o << ].val + a[o << | ].val;
a[o].val += a[o].lazy * (r - l + );
} void push_down(int o, int l, int r)
{
int mid = (l + r) >> ;
if(l == r) return;
if(a[o].lazy)
{
a[o << ].lazy += a[o].lazy;
a[o << ].val += a[o].lazy * (mid - l + );
a[o << | ].lazy += a[o].lazy;
a[o << | ].val += a[o].lazy * (r - mid);
a[o].lazy = ;
}
} void update(int o, int l, int r, int ql, int qr, int val)
{
int mid = (l + r) >> ;
push_down(o, l, r);
if(ql <= l && r <= qr)
{
a[o].lazy += val;
a[o].val += (long long)val * (r - l + );
return;
}
if(ql <= mid) update(o << , l, mid, ql, qr, val);
if(mid < qr) update(o << | , mid + , r, ql, qr, val);
push_up(o, l, r);
} long long query(int o, int l, int r, int ql, int qr)
{
int mid = (l + r) >> ;
long long ans = ;
push_down(o, l, r);
if(ql <= l && r <= qr) return a[o].val;
if(ql <= mid) ans = query(o << , l, mid, ql, qr);
if(mid < qr) ans += query(o << | , mid + , r, ql, qr);
return ans;
} int main()
{
int n, m, u, v, op, x, val;
long long ans;
scanf("%d%d", &n, &m);
for(int i = ; i <= n; ++i)
scanf("%d", &p[i].val);
for(int i = ; i < n; ++i)
{
scanf("%d%d", &u, &v);
addedge(i << , u, v);
addedge(i << | , v, u);
}
DFS1(), DFS2(, );
for(int i = ; i <= n; ++i)
update(, , n, p[i].dfn, p[i].dfn, p[i].val);
while(m--)
{
scanf("%d", &op);
if(op == )
{
scanf("%d%d", &x, &val);
update(, , n, p[x].dfn, p[x].dfn, val);
}
else if(op == )
{
scanf("%d%d", &x, &val);
update(, , n, p[x].dfn, p[x].dfn + p[x].siz - , val);
}
else
{
scanf("%d", &x);
ans = ;
while(x)
{
ans += query(, , n, p[p[x].top].dfn, p[x].dfn);
x = p[p[x].top].fa;
}
printf("%lld\n", ans);
}
}
return ;
}