给你n个点，m条边，p次操作。n个点相连后是一棵树。每次操作可以是x 到 y 增加 z，或者减z，或者问当前点的值是多少。
可以将树分成链，每个点在线段树上都有自己的点，然后线段树成段更新一下。
#pragma comment(linker, "/STACK:1024000000,1024000000") #include<queue> #include<stack> #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define INF 99999999 #define ll __int64 #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; const int MAXN = 50010; struct node { int to; int v; int next; }edge[MAXN*3]; int pre[MAXN],ind,top[MAXN],fa[MAXN],son[MAXN],w[MAXN],deq[MAXN],siz[MAXN],fn; int tree[MAXN<<2],mark[MAXN<<2]; int n,m,val[MAXN]; void add(int x,int y) { edge[ind].to = y; edge[ind].next = pre[x]; pre[x] = ind++; } void dfs1(int rt,int pa,int d) { deq[rt] = d; son[rt] = 0; fa[rt] = pa; siz[rt] = 1; int i; for(i=pre[rt]; i!=-1; i=edge[i].next){ int t = edge[i].to; if(t != fa[rt]){ dfs1(t,rt,d+1); siz[rt] += siz[t]; if(siz[son[rt]] < siz[t]){ son[rt] = t; } } } } void dfs2(int rt,int tp) { w[rt] = ++fn; top[rt] = tp; if(son[rt] != 0) dfs2(son[rt], tp); for(int i=pre[rt]; i!=-1; i=edge[i].next){ int t = edge[i].to; if(t != son[rt] && t != fa[rt]){ dfs2(t,t); } } } void build(int l,int r,int rt) { tree[rt] = 0; mark[rt] = 0; if(l == r) return ; int m = (l+r)/2; build(lson); build(rson); } void pushdown(int rt) { if(mark[rt] != 0){ mark[rt<<1|1] += mark[rt]; mark[rt<<1] += mark[rt]; tree[rt<<1|1] += mark[rt]; tree[rt<<1] += mark[rt]; mark[rt] = 0; } } void Insert(int p,int v,int l,int r,int rt) { if(l == r){ tree[rt] = v; return ; } int m = (l+r)/2; if(m >= p){ Insert(p,v,lson); } else Insert(p,v,rson); } void updata(int L,int R,int v,int l,int r,int rt) { if(L<=l && r<=R){ mark[rt] += v; tree[rt] += v; return ; } pushdown(rt); int m = (l+r)/2; if(m >= L){ updata(L,R,v,lson); } if(m < R){ updata(L,R,v,rson); } } int query(int p,int l,int r,int rt) { if(l == r){ return tree[rt]; } pushdown(rt); int m = (l+r)/2; if(m >= p){ return query(p,lson); } else { return query(p,rson); } } void updata_all(int x,int y,int z) { while(top[x] != top[y]) { if(deq[top[x]] < deq[top[y]]){ swap(x,y); } updata(w[top[x]],w[x],z,1,fn,1); x = fa[top[x]]; } if(deq[x] < deq[y]){ swap(x,y); } updata(w[y],w[x],z,1,fn,1); } int main() { int i,j,p; while(~scanf("%d%d%d",&n,&m,&p)) { for(i=1; i<=n; i++){ scanf("%d",&val[i]); } ind = 1; memset(pre,-1,sizeof(pre)); for(i=1; i<=m; i++){ int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); } dfs1(1,1,1); fn = 0; dfs2(1,1); build(1,n,1); for(i=1; i<=n; i++){ Insert(w[i],val[i],1,fn,1); } char s[10]; while(p--) { scanf("%s",s); if(s[0] == 'I'){ int x,y,z; scanf("%d%d%d",&x,&y,&z); updata_all(x,y,z); } else if(s[0] == 'D'){ int x,y,z; scanf("%d%d%d",&x,&y,&z); updata_all(x,y,-z); } else { int x; scanf("%d",&x); printf("%d ",query(w[x],1,fn,1)); } } } }