题目链接：传送门
题目大意：给你一棵无根树，每个树节点上有权值，有三种操作，I x y v（从x到y的路径上每个点权值+v）
D x y v（从x到y的路径上每个点权值-v）Q x（树节点为x 的权值是多少，权值可以为负）
题目思路：树链剖分
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <cstring> #include <stack> #include <cctype> #include <queue> #include <string> #include <vector> #include <set> #include <map> #include <climits> #define lson rt<<1,l,mid #define rson rt<<1|1,mid+1,r #define fi first #define se second #define ping(x,y) ((x-y)*(x-y)) #define mst(x,y) memset(x,y,sizeof(x)) #define mcp(x,y) memcpy(x,y,sizeof(y)) using namespace std; #define gamma 0.5772156649015328606065120 #define MOD 1000000007 #define inf 0x3f3f3f3f #define N 50005 #define maxn 30010 typedef pair<int,int> PII; typedef long long LL; LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} return x*f; } int n,m,k,L,R; struct Node{int to,nxt,v;}node[N<<1]; int head[N],hcnt; int a[N],seg[N<<2],mrk[N<<2]; int siz[N]; ///当前节点所含儿子的数量 int top[N]; ///当前节点所在链的顶端 int son[N]; ///当前节点的重儿子 int fa[N]; ///当前节点的父节点 int dep[N]; ///当前节点的深度 int id[N],tid; ///当前节点的新编号 int posi[N]; ///当前节点在线段树中位置 void init(){ mst(head,-1);mst(mrk,0);hcnt=tid=0; mst(son,0);mst(siz,0);mst(id,0);mst(seg,0); } inline void addedge(int x,int y){ node[hcnt].to=y,node[hcnt].nxt=head[x],head[x]=hcnt++; node[hcnt].to=x,node[hcnt].nxt=head[y],head[y]=hcnt++; } void dfs1(int u,int f,int deep){ ///确定重边和节点深度 fa[u]=f; siz[u]=1; dep[u]=deep; for(int i=head[u];~i;i=node[i].nxt){ int e=node[i].to; if(e==f)continue; dfs1(e,u,deep+1); siz[u]+=siz[e]; if(!son[u]||siz[son[u]]<siz[e]) son[u]=e; } } void dfs2(int u,int tp){ ///连边成链 top[u]=tp; id[u]=++tid; posi[id[u]]=u; if(!son[u])return; dfs2(son[u],tp); for(int i=head[u];~i;i=node[i].nxt){ int e=node[i].to; if(!id[e]) dfs2(e,e);///***和 e!=son[u]&&e!=fa[u] 无区别？ } } void build(int rt,int l,int r){ if(l==r){ seg[rt]=a[posi[l]]; return; } int mid=l+r>>1; build(lson);build(rson); } void pushdown(int rt){ mrk[rt<<1]+=mrk[rt]; mrk[rt<<1|1]+=mrk[rt]; seg[rt<<1]+=mrk[rt]; seg[rt<<1|1]+=mrk[rt]; mrk[rt]=0; } void add(int rt,int l,int r,int v){ if(L<=l&&r<=R){ seg[rt]+=v; mrk[rt]+=v; return; } if(mrk[rt])pushdown(rt); int mid=l+r>>1; if(L<=mid)add(lson,v); if(R>mid)add(rson,v); } int query(int rt,int l,int r,int pos){ if(l==r){return seg[rt];} int mid=l+r>>1; if(mrk[rt])pushdown(rt); if(pos<=mid)return query(lson,pos); else return query(rson,pos); } int main(){ //freopen("in.txt","r",stdin); int i,j,group,x,y,v,Case=0; while(scanf("%d",&n)!=EOF){ init(); m=read();k=read(); for(i=1;i<=n;++i) a[i]=read(); while(m--){ x=read();y=read(); addedge(x,y); } dfs1(1,1,1); dfs2(1,1); build(1,1,n); char ch; while(k--){ scanf(" %c",&ch); if(ch=='Q'){ x=read(); printf("%d ",query(1,1,n,id[x])); continue; } x=read();y=read();v=read();if(ch=='D')v=-v; while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); L=id[top[x]];R=id[x]; add(1,1,n,v); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); L=id[x],R=id[y]; add(1,1,n,v); } } return 0; }