题意：给你一棵树，然后有三种操作

　　I L R K: 把L与R的路径上的所有点权值加上K

　　D L R K：把L与R的路径上的所有点权值减去K

　　Q X：查询节点编号为X的权值

思路：树链剖分裸题（我还没有怎么学懂，但基本已经没有什么太大的问题，主要的问题就在于点或者边对于数据结构的映射关系是，主要没有单独手写过树链剖分，所以对这部分 没有什么体会）

我们知道树链剖分是一种将树剖为链的一种算法，其思想和dfs序差不多，但根据树链剖分的性质，我们的重链是连续的区间，这样对于重链或者重链上的点我们可以方便的用数据结构维护，对于修改操作，是一种类似于LCA的算法，但感觉本质上还是一种LCA，只不过每次向上跳的部分是跳到top，其他的就是两次dfs，分别维护组时候大小以及一些其他的东西，第二遍dfs 找出重链

代码：

#include 
     
      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
      
       <<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
       
        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\n",query(w[x],1,n,1));            }        }    }    return 0;}