树链剖分是极其恶心的要用到其他数据结构的一种数据结构（或者说处理策略）。在应用之前，需要熟练掌握树形 Dp，Dfs，Dfs 序，对数相关概念，线段树/Splay/…。这道题就要用到树链剖分。

题意

给定一棵 n 节点树 (n<=５×10^４)，和 q 次操作 (q<=10⁵)，操作有两种：１. 将连接 a,b 的链上的所有节点的权值加 c；２. 求点 a 的权值。有多组数据。

思路

由于 LCA 我们最快可以 O(1) 求，但是更新权值需要 O(n) 的复杂度。那么暴力算法的复杂度就是 O(qn)，不再可承受范围内。
所以我们有这么几个思路：
1. 讨论如何用数据结构优化区间修改操作。
2. 讨论如何在快速求出 LCA 的同时还可以快速更新。
于是傻×都可以看出来这个要用树链剖分。具体神码是树链剖分详见本博客的另一篇教程。
简单来讲，我们为了可以比 O(n) 快地求 LCA 并且可以成段更新，我们将树划分成两种颜色不同的边。同种颜色的相连边可以保存深度最小的点是谁，于是就可以跳跃着求出 LCA，过程与倍增类似。通过良好的划分方式，我们可以得到一个双色的树，这棵树的每一个点到根节点只需要跳跃 logn 级别的次数。对于每一次跳跃跳过的链，我们可以依次将链上的节点编号，放入线段树中。每一条边的节点在线段树中是连续的。所以可以 logn 修改。这样我们就得到了 O(nlognlogn) 的解法。

#include <iostream>
#include <cstring>
#include <cstdio>

#define MX 100009
#define ls (node<<1)
#define rs ((node<<1)+1)
#define mid ((l+r)>>1)

using namespace std;

int siz[MX];                                                        //子树大小
int top[MX];                                                      //重链 (其中一种颜色的连续边) 的顶端节点
int son[MX];                                                      //重儿子 (详见教程)
int dep[MX];                                                     //每个点的深度
int fa[MX];                                                         //父节点
int tid[MX];                                                        //节点编号
int rak[MX];                                                       //编号对应的节点
int fst[MX],nxt[MX*2],v[MX*2],lnum=-1;
int n,m,p,w[MX],tim;

void addeg(int nu,int nv)
{
    lnum++;
    nxt[lnum]=fst[nu];
    fst[nu]=lnum;
    v[lnum]=nv;
}

void dfs1(int x,int fat,int d)
{
    dep[x]=d;
    fa[x]=fat;
    siz[x]=1;
    for(int i=fst[x];i!=-1;i=nxt[i])
    {
        if(v[i]==fat)continue;
        dfs1(v[i],x,d+1);
        siz[x]+=siz[v[i]];
        if(son[x]==-1||siz[v[i]]>siz[son[x]])son[x]=v[i];
    }
}

void dfs2(int x,int tp)
{
    top[x]=tp;
    tid[x]=++tim;
    //cout<<"set:"<<x<<" "<<tid[x]<<endl;
    rak[tid[x]]=x;
    if(son[x]==-1)return;
    dfs2(son[x],tp);
    for(int i=fst[x];i!=-1;i=nxt[i])
    {
        if(v[i]==son[x]||v[i]==fa[x])continue;
        dfs2(v[i],v[i]);
    }
}

typedef struct tnode
{
    int sm,l,r,x;
}treenode;
treenode tree[MX*4];

void build(int node,int l,int r)
{
    tree[node].sm=0;
    tree[node].l=l;
    tree[node].r=r;
    if(l==r)tree[node].x=w[rak[l]];
    else build(ls,l,mid),build(rs,mid+1,r);
}

void pushdown(int node)
{
    tree[node].x+=tree[node].sm;
    tree[ls].sm+=tree[node].sm;
    tree[rs].sm+=tree[node].sm;
    tree[node].sm=0;
}

void add(int node,int ql,int qr,int x)
{
    pushdown(node);
    int l=tree[node].l,r=tree[node].r;
    if(l>=ql&&r<=qr)
    {
        tree[node].sm+=x;
        pushdown(node);
    }
    else if(l>qr||r<ql)return ;
    else add(ls,ql,qr,x),add(rs,ql,qr,x);
}

int qsm(int node,int qp)
{
    pushdown(node);
    int l=tree[node].l,r=tree[node].r;
    if(l==r)return tree[node].x;
    else if(qp<=mid)return qsm(ls,qp);
    else return qsm(rs,qp);
}

void change(int s,int t,int x)
{
    int f1=top[s],f2=top[t];
    while(f1!=f2)
    {
        if(dep[f1]<dep[f2])swap(f1,f2),swap(s,t);
        add(1,tid[f1],tid[s],x);
        s=fa[f1];
        f1=top[s];
    }
    if(dep[s]>dep[t])swap(s,t);
    add(1,tid[s],tid[t],x);
}

void init()
{
    memset(fst,0xff,sizeof(fst));
    memset(son,0xff,sizeof(son));
    lnum=-1;
    tim=0;
}

void input()
{
    int a,b;
    for(int i=1;i<=n;i++)scanf("%d",&w[i]);
    for(int i=1;i<=m;i++)scanf("%d%d",&a,&b),addeg(a,b),addeg(b,a);
}

void work()
{
    int a,b,c;
    char com[10];
    for(int i=1;i<=p;i++)
    {
        scanf("%s",com);
        if(com[0]=='I'){scanf("%d%d%d",&a,&b,&c);change(a,b,c);}
        else if(com[0]=='D'){scanf("%d%d%d",&a,&b,&c);change(a,b,-c);}
        else if(com[0]=='Q'){scanf("%d",&a);printf("%d\n",qsm(1,tid[a]));}
    }
}

int main()
{
    while(~scanf("%d%d%d",&n,&m,&p))
    {
        init();
        input();
        dfs1(1,0,1);
        dfs2(1,1);
        build(1,1,n);
        work();
    }

    return 0;
}