【题目链接】
【算法】
树链剖分
子树的DFS序是连续的一段！
【代码】
#include<bits/stdc++.h> using namespace std; #define MAXN 100010 struct Edge { int to,nxt; } e[MAXN*2]; int i,opt,n,m,q,x,y,val,tot,timer; int dfn[MAXN],pos[MAXN],head[MAXN],size[MAXN], son[MAXN],top[MAXN],fa[MAXN],dep[MAXN]; long long a[MAXN]; template <typename T> inline void read(T &x) { long long f = 1; x = 0; char c = getchar(); for (; !isdigit(c); c = getchar()) { if (c == '-') f = -f; } for (; isdigit(c); c = getchar()) x = (x << 3) + (x << 1) + c - '0'; x *= f; } template <typename T> inline void write(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x/10); putchar(x%10+'0'); } template <typename T> inline void writeln(T x) { write(x); puts(""); } struct SegmentTree { struct Node { int l,r; long long sum,tag; } Tree[MAXN*4]; inline void update(int index) { Tree[index].sum = Tree[index<<1].sum + Tree[index<<1|1].sum; } inline void pushdown(int index) { int l = Tree[index].l,r = Tree[index].r; int mid = (l + r) >> 1; if (Tree[index].tag) { Tree[index<<1].sum += Tree[index].tag * (mid - l + 1); Tree[index<<1|1].sum += Tree[index].tag * (r - mid); Tree[index<<1].tag += Tree[index].tag; Tree[index<<1|1].tag += Tree[index].tag; Tree[index].tag = 0; } } inline void build(int index,int l,int r) { int mid; Tree[index].l = l; Tree[index].r = r; if (l == r) { Tree[index].sum = a[pos[l]]; return; } mid = (l + r) >> 1; build(index<<1,l,mid); build(index<<1|1,mid+1,r); update(index); } inline void add1(int index,int pos,long long val) { int mid; if (Tree[index].l == Tree[index].r) { Tree[index].sum += val; return; } pushdown(index); mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= pos) add1(index<<1,pos,val); else add1(index<<1|1,pos,val); update(index); } inline void add2(int index,int l,int r,long long val) { int mid; if (Tree[index].l == l && Tree[index].r == r) { Tree[index].sum += val * (r - l + 1); Tree[index].tag += val; return; } pushdown(index); mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= r) add2(index<<1,l,r,val); else if (mid + 1 <= l) add2(index<<1|1,l,r,val); else { add2(index<<1,l,mid,val); add2(index<<1|1,mid+1,r,val); } update(index); } inline long long query(int index,int l,int r) { int mid; if (Tree[index].l == l && Tree[index].r == r) return Tree[index].sum; pushdown(index); mid = (Tree[index].l + Tree[index].r) >> 1; if (mid >= r) return query(index<<1,l,r); else if (mid + 1 <= l) return query(index<<1|1,l,r); else return query(index<<1,l,mid) + query(index<<1|1,mid+1,r); } } T; inline void add(int u,int v) { tot++; e[tot] = (Edge){v,head[u]}; head[u] = tot; } inline void dfs1(int x) { int i,y; size[x] = 1; for (i = head[x]; i; i = e[i].nxt) { y = e[i].to; if (fa[x] != y) { fa[y] = x; dep[y] = dep[x] + 1; dfs1(y); size[x] += size[y]; if (size[y] > size[son[x]]) son[x] = y; } } } inline void dfs2(int x,int tp) { int i,y; top[x] = tp; dfn[x] = ++timer; pos[timer] = x; if (son[x]) dfs2(son[x],tp); for (i = head[x]; i; i = e[i].nxt) { y = e[i].to; if (fa[x] != y && son[x] != y) dfs2(y,y); } } inline long long query(int x) { long long ans = 0; int tx = top[x]; while (tx != 1) { ans += T.query(1,dfn[tx],dfn[x]); x = fa[tx]; tx = top[x]; } ans += T.query(1,1,dfn[x]); return ans; } int main() { read(n); read(q); for (i = 1; i <= n; i++) read(a[i]); for (i = 1; i < n; i++) { read(x); read(y); add(x,y); add(y,x); } dfs1(1); dfs2(1,1); T.build(1,1,timer); while (q--) { read(opt); if (opt == 1) { read(x); read(val); T.add1(1,dfn[x],val); } if (opt == 2) { read(x); read(val); T.add2(1,dfn[x],dfn[x]+size[x]-1,val); } if (opt == 3) { read(x); writeln(query(x)); } } return 0; }