参考博客：

http://www.cnblogs.com/zwfymqz/p/8094500.html

https://www.cnblogs.com/ivanovcraft/p/9019090.html

http://www.cnblogs.com/chinhhh/p/7965433.html

定义

重儿子：父亲节点的所有儿子中子树结点数目最多（size最大）的结点；

轻儿子：父亲节点中除了重儿子以外的儿子；

重边：父亲结点和重儿子连成的边；

轻边：父亲节点和轻儿子连成的边；

重链：由多条重边连接而成的路径；

• 对于叶子节点，若其为轻儿子，则有一条以自己为起点的长度为1的链
• 每一条重链以轻儿子为起点

轻链：由多条轻边连接而成的路径；

如何对这些链进行维护？

首先，要对这些链进行维护，就要确保每个链上的节点都是连续的，因此我们需要对整棵树进行重新编号，然后利用dfs序的思想，用线段树或树状数组等进行维护。

对于一棵最基本的树：

给他标记重儿子：

蓝色为重儿子，红色为重边。

然后对树进行重新编号：

橙色表示的是该节点重新编号后的序号。

不难看出重链内的节点编号是连续的。

有一个性质：以i为根的子树的树在线段树上的编号为[i,i+子树节点数−1] 。

步骤

1.对整棵树dfs一遍，找出每个节点的重儿子。处理出每个节点的深度，以及他们的父亲节点。

处理出这些：

int par[100010];//该结点的父亲，用来往上跳
int dep[100010];//该结点的深度，用来往上跳
int tot[100010];//该结点子树的结点个数，用来更新权值和
int son[100010];//该结点的重儿子编号

2.对整棵树进行重新编号。

处理出这些：

int idx[100010];//该结点重新编号后的编号
int topp[100010];//该结点所在链的顶端结点
int aval[100010];//重新编号后该结点的权值

3.根据重新编完号的树，把这棵树的上每个点映射到线段树上。并写出线段树的基本操作函数。

4.实现对于树上的操作，

树链剖分的思想是:对于两个不在同一重链内的节点,让他们不断地跳,使得他们处于同一重链上。

那么如何”跳”呢？

用到top数组么？

有一个显然的结论：x到top[x]中的节点在线段树上是连续的。

结合deep数组，

假设两个节点为x,y，

我们每次让deep[top[x]]与deep[top[y]]中大的(在下面的)往上跳(有点类似于树上倍增)，

让x节点直接跳到top[x]，然后在线段树上更新，

最后两个节点一定是处于同一条重链的，前面我们提到过重链上的节点都是连续的，直接在线段树上进行一次查询就好。

结合一个例子说明：

还是上面那张图，假设我们要查询3.6这两个节点的之间的点权合，为了方便理解我们假设每个点的点权都是1，

刚开始时

top[3]=2,top[6]=1，

deep[top[3]]=2,deep[top[6]]=1，

我们会让3向上跳,跳到top[3]的爸爸,也就是1号节点

这是1号节点和6号节点已经在同一条重链内,所以直接对线段树进行一次查询即可。

对于子树的操作，利用性质直接query或update。

复杂度

$O(log_2n)^2$。

模板

已知一棵包含N个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

1 x y z 表示将树从x到y结点最短路径上所有节点的值都加上z；

2 x y 表示求树从x到y结点最短路径上所有节点的值之和；

3 x z 表示将以x为根节点的子树内所有节点值都加上z；

4 x 表示求以x为根节点的子树内所有节点值之和。

int val[100010];//该结点的权值
int top;
int head[100010];
struct edge
{
    int to;
    int next;
}eg[200010];
int par[100010];//该结点的父亲
int dep[100010];//该结点的深度
int tot[100010];//该结点子树的结点个数
int son[100010];//该结点的重儿子编号
int idx[100010];//该结点重新编号后的编号
int topp[100010];//该结点所在链的顶端结点
int aval[100010];//重新编号后该结点的权值
int cnt;
struct node
{
    int left,right;
    int sum;
    int f;
}node[100010<<2];
int ans;
void add(int a,int b)
{
    eg[top].to=b;
    eg[top].next=head[a];
    head[a]=top++;
}
int dfs1(int id,int fa,int depth)
{
    par[id]=fa;dep[id]=depth;
    tot[id]=1;
    int maxson=-1;
    son[id]=0;
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(temp==fa)continue;
        tot[id]+=dfs1(temp,id,depth+1);
        if(tot[temp]>maxson)
        {
            son[id]=temp;
            maxson=tot[temp];
        }
    }
    return tot[id];
}
void dfs2(int id,int topf)
{
    idx[id]=++cnt;
    aval[cnt]=val[id];
    topp[id]=topf;
    if(son[id]==0)return;     //子节点的son为0
    dfs2(son[id],topf);     //优先标记重儿子
    for(int i=head[id];i!=-1;i=eg[i].next)
    {
        int temp=eg[i].to;
        if(idx[temp]==0)
            dfs2(temp,temp);     //每一条链以轻儿子为起点
    }
}
void build(int l,int r,int id)
{
    node[id].left=l;node[id].right=r;
    node[id].f=0;
    if(l==r)
    {
        node[id].sum=aval[l];
        return;
    }
    int m=(l+r)>>1;
    build(l,m,id<<1);
    build(m+1,r,id<<1|1);
    node[id].sum=node[id<<1].sum+node[id<<1|1].sum;
}
void pushdown(int id)
{
    int l1=node[id<<1].left,r1=node[id<<1].right;
    int l2=node[id<<1|1].left,r2=node[id<<1|1].right;
    node[id<<1].f=node[id<<1].f+node[id].f;
    node[id<<1|1].f=node[id<<1|1].f+node[id].f;
    node[id<<1].sum=node[id<<1].sum+node[id].f*(r1-l1+1);
    node[id<<1|1].sum=node[id<<1|1].sum+node[id].f*(r2-l2+1);
    node[id].f=0;
}
void update(int L,int R,int c,int id)
{
    int l=node[id].left,r=node[id].right;
    if(l>=L&&r<=R)
    {
        node[id].sum=node[id].sum+c*(r-l+1);
        node[id].f=node[id].f+c;
        return;
    }
    if(node[id].f)pushdown(id);
    int m=(l+r)>>1;
    if(L<=m)update(L,R,c,id<<1);
    if(R>m)update(L,R,c,id<<1|1);
    node[id].sum=node[id<<1].sum+node[id<<1|1].sum;
}
void query(int L,int R,int id)
{
    int l=node[id].left,r=node[id].right;
    if(l>=L&&r<=R)
    {
        ans=ans+node[id].sum;
        return;
    }
    if(node[id].f)pushdown(id);
    int m=(l+r)>>1;
    if(L<=m)query(L,R,id<<1);
    if(R>m)query(L,R,id<<1|1);
}
void change1(int x,int y,int c)
{
    while(topp[x]!=topp[y])
    {
        if(dep[topp[x]]<dep[topp[y]])swap(x,y);     //谁的top低谁就往上走
        update(idx[topp[x]],idx[x],c,1);     //改变x~top[x]这条链的权值
        x=par[topp[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    update(idx[x],idx[y],c,1);     //改变x~top[x]这条链的权值
}
void change2(int id,int c)
{
    update(idx[id],idx[id]+tot[id]-1,c,1);
}
int ask1(int x,int y)
{
    int res=0;
    while(topp[x]!=topp[y])
    {
        if(dep[topp[x]]<dep[topp[y]])swap(x,y);   //谁的top低谁就往上走
        ans=0;
        query(idx[topp[x]],idx[x],1);     //查询x~top[x]这条链的权值
        res=res+ans;
        x=par[topp[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    ans=0;
    query(idx[x],idx[y],1);     //查询x~top[x]这条链的权值
    res=res+ans;
    return res;
}
int ask2(int id)
{
    ans=0;
    query(idx[id],idx[id]+tot[id]-1,1);
    return ans;
}
int main()
{
    int n,m,r,op,x,y,z;
    scanf("%d%d%d",&n,&m,&r);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&val[i]);
        head[i]=-1;
        idx[i]=0;
    }
    top=0;
    for(int i=1;i<=n-1;i++)
    {
        scanf("%d%d",&x,&y);
        add(x,y);add(y,x);
    }
    dfs1(r,0,1);
    cnt=0;
    dfs2(r,r);
    build(1,n,1);
    while(m--)
    {
        scanf("%d",&op);
        if(op==1)
        {
            scanf("%d%d%d",&x,&y,&z);
            change1(x,y,z);     //将树从x到y结点最短路径上所有节点的值都加上z
        }
        else if(op==2)
        {
            scanf("%d%d",&x,&y);
            printf("%d\n",ask1(x,y));     //求树从x到y结点最短路径上所有节点的值之和
        }
        else if(op==3)
        {
            scanf("%d%d",&x,&z);
            change2(x,z);     //将以x为根节点的子树内所有节点值都加上z
        }
        else if(op==4)
        {
            scanf("%d",&x);
            printf("%d\n",ask2(x));     //求以x为根节点的子树内所有节点值之和
        }
    }
    return 0;
}