题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=4034
题意：中文题面
思路：树链剖分入门题。 剖分后就是一个简单的区间更新和区间求和问题。用线段树去维护一下。 由于有一个操作是关于子树的，可以用DFS序来求，但是由于剖分后的序列都是连续的，所以只需要记录下返回当前根时前一个点的位置即可进行子树操作。
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<queue>
#include<vector>
#include<stack>
#include<map>
#include<set>
#include<time.h>
#include<cmath>
#include<sstream>
#include<assert.h>
using namespace std;
#define L(x) x<<1
#define R(x) x<<1|1
typedef long long int LL;
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
const int MAXN = + ;
int val[MAXN], head[MAXN], tot, cnt;
struct Edge{
int to,next;
Edge(int _to = , int _next = ) :to(_to), next(_next){};
}Edges[MAXN * ];
void add(int u, int v){
Edges[tot].to = v;
Edges[tot].next = head[u];
head[u] = tot++;
}
int id[MAXN], endid[MAXN], son[MAXN], deep[MAXN], size[MAXN], fa[MAXN], reid[MAXN], top[MAXN];
void Init(){
tot = ; cnt = ;
memset(head, -, sizeof(head));
memset(son, -, sizeof(son));
}
void DFS1(int u, int p,int dep){
fa[u] = p; size[u] = ; deep[u] = dep;
for (int i = head[u]; i != -; i = Edges[i].next){
if (Edges[i].to != p){
DFS1(Edges[i].to, u,dep+);
size[u] += size[Edges[i].to];
if (son[u] == - || size[Edges[i].to] > size[son[u]]){
son[u] = Edges[i].to;
}
}
}
}
void DFS2(int u, int tp){
id[u] = ++cnt; reid[id[u]] = u; top[u] = tp;
if (son[u] == -){
endid[u] = cnt;
return;
}
DFS2(son[u], tp);
for (int i = head[u]; i != -; i = Edges[i].next){
if (son[u] != Edges[i].to&&Edges[i].to != fa[u]){
DFS2(Edges[i].to, Edges[i].to);
}
}
endid[u] = cnt;
}
struct Node{
int st, ed;
LL sum, lazy;
}Seg[MAXN * ];
void Build(int l, int r, int k){
Seg[k].st = l; Seg[k].ed = r; Seg[k].lazy = ;
if (l == r){
Seg[k].sum = val[reid[l]];
return;
}
int mid = (l + r) / ;
Build(l, mid, L(k)); Build(mid + , r, R(k));
Seg[k].sum = Seg[L(k)].sum + Seg[R(k)].sum;
}
void pushUp(int k){
Seg[k].sum = Seg[L(k)].sum + Seg[R(k)].sum;
}
void pushDown(int k){
if (Seg[k].lazy){
Seg[L(k)].sum += 1LL*Seg[k].lazy*(Seg[L(k)].ed - Seg[L(k)].st + );
Seg[L(k)].lazy += Seg[k].lazy;
Seg[R(k)].sum += 1LL*Seg[k].lazy*(Seg[R(k)].ed - Seg[R(k)].st + );
Seg[R(k)].lazy += Seg[k].lazy;
Seg[k].lazy = ;
}
}
void Add(int l, int r, int k,int val){
if (Seg[k].st == l&&Seg[k].ed == r){
Seg[k].lazy += val;
Seg[k].sum += 1LL * val * (r - l + );
return;
}
pushDown(k);
if (r <= Seg[L(k)].ed){
Add(l, r, L(k),val);
}
else if (l >= Seg[R(k)].st){
Add(l, r, R(k),val);
}
else{
Add(l, Seg[L(k)].ed, L(k), val);
Add(Seg[R(k)].st, r, R(k), val);
}
pushUp(k);
}
LL Query(int l, int r, int k){
if (Seg[k].st == l&&Seg[k].ed == r){
return Seg[k].sum;
}
pushDown(k);
LL sum = ;
if (r <= Seg[L(k)].ed){
sum=Query(l, r, L(k));
}
else if (l >= Seg[R(k)].st){
sum=Query(l, r, R(k));
}
else{
sum=Query(l, Seg[L(k)].ed, L(k)) + Query(Seg[R(k)].st, r, R(k));
}
pushUp(k);
return sum;
}
LL Query(int x){
LL ans = ;
while (top[x]!=){
ans += Query(id[top[x]], id[x],);
x = fa[top[x]];
}
ans += Query(,id[x], );
return ans;
}
int main(){
//#ifdef kirito
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
//#endif
// int start = clock();
int n, m;
while (~scanf("%d%d",&n,&m)){
Init();
for (int i = ; i <= n; i++){
scanf("%d", &val[i]);
}
for (int i = ; i < n; i++){
int u, v;
scanf("%d%d", &u, &v);
add(u, v); add(v, u);
}
DFS1(, , ); DFS2(, );
Build(, n, );
while (m--){
int ope, x, a;
scanf("%d", &ope);
switch (ope)
{
case :scanf("%d%d", &x, &a); Add(id[x],id[x] , , a); break;
case :scanf("%d%d", &x, &a); Add(id[x], endid[x], , a); break;
default: scanf("%d", &x); printf("%lld\n", Query(x)); break;
}
}
}
//#ifdef LOCAL_TIME
// cout << "[Finished in " << clock() - start << " ms]" << endl;
//#endif
return ;
}