题意：给你一棵树，然后有三种操作
I L R K: 把L与R的路径上的所有点权值加上K
D L R K：把L与R的路径上的所有点权值减去K
Q X：查询节点编号为X的权值
思路：树链剖分裸题（我还没有怎么学懂，但基本已经没有什么太大的问题，主要的问题就在于点或者边对于数据结构的映射关系是，主要没有单独手写过树链剖分，所以对这部分 没有什么体会）
我们知道树链剖分是一种将树剖为链的一种算法，其思想和dfs序差不多，但根据树链剖分的性质，我们的重链是连续的区间，这样对于重链或者重链上的点我们可以方便的用数据结构维护，对于修改操作，是一种类似于LCA的算法，但感觉本质上还是一种LCA，只不过每次向上跳的部分是跳到top，其他的就是两次dfs，分别维护组时候大小以及一些其他的东西，第二遍dfs 找出重链
代码：
#include <bits/stdc++.h> using namespace std; const int maxn=50008; const int maxm=100008; int n,m,Q; int a[maxn],sz[maxn],dep[maxn],fa[maxn],top[maxn],w[maxn],son[maxn]; int Rank[maxn]; int sum[maxn<<2],lazy[maxn<<2]; struct line { int u,v,nxt; }eg[maxm]; int head[maxn],summ,cnt; void addedge(int u,int v) { eg[++summ].u=u; eg[summ].v=v; eg[summ].nxt=head[u]; head[u]=summ; } void add(int u,int v) { addedge(u,v);addedge(v,u); } void dfs1(int u) { sz[u]=1;son[u]=0; for(int i=head[u];i;i=eg[i].nxt){ int v=eg[i].v; if(v!=fa[u]){ fa[v]=u; dep[v]=dep[u]+1; dfs1(v); sz[u]+=sz[v]; if(sz[v]>sz[son[u]])son[u]=v; } } } void dfs2(int u,int tp,int x) { top[u]=tp;w[u]=++cnt;Rank[cnt]=u; if(son[u])dfs2(son[u],tp,1); for(int i=head[u];i;i=eg[i].nxt){ int v=eg[i].v; if(v==son[u]||v==fa[u])continue; dfs2(v,v,2); } } void init() { memset(head,0,sizeof(head)); summ=1;cnt=0; dep[1]=1;fa[1]=0; } void pushup(int rt) { sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void pushdown(int rt,int len) { if(lazy[rt]){ lazy[rt<<1]+=lazy[rt]; lazy[rt<<1|1]+=lazy[rt]; sum[rt<<1]+=lazy[rt]*(len-len/2); sum[rt<<1|1]+=lazy[rt]*(len/2); lazy[rt]=0; } } void build(int l,int r,int rt) { lazy[rt]=0; if(l==r){ sum[rt]=a[Rank[l]]; return ; } int mid=(l+r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt); } void update(int L,int R,int val,int l,int r,int rt) { if(L<=l&&r<=R){ sum[rt]+=val*(r-l+1); lazy[rt]+=val; return ; } pushdown(rt,r-l+1); int mid=(l+r)>>1; if(L<=mid)update(L,R,val,l,mid,rt<<1); if(mid<R)update(L,R,val,mid+1,r,rt<<1|1); pushup(rt); } int query(int x,int l,int r,int rt) { if(l==r){ return sum[rt]; } pushdown(rt,r-l+1); int mid=(l+r)>>1; if(x<=mid)return query(x,l,mid,rt<<1); if(mid<x)return query(x,mid+1,r,rt<<1|1); } void modify(int x,int y,int val) { while(top[x]!=top[y]){ if(dep[top[x]]<dep[top[y]])swap(x,y); update(w[top[x]],w[x],val,1,n,1); x=fa[top[x]]; } if(dep[x]>dep[y])swap(x,y); update(w[x],w[y],val,1,n,1); } int main() { while(~scanf("%d%d%d",&n,&m,&Q)){ init(); for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); } dfs1(1); dfs2(1,1,1); build(1,cnt,1); while (Q--){ char s[2]; int x,y,z; scanf("%s",s); if (s[0]=='I'){ scanf("%d %d %d",&x,&y,&z); modify(x,y,z); } if (s[0]=='D'){ scanf("%d %d %d",&x,&y,&z); modify(x,y,-z); } if (s[0]=='Q'){ scanf("%d",&x); printf("%d ",query(w[x],1,n,1)); } } } return 0; }