1. 前言

如果给你一棵树，求点 u 到点 v 路径上点的权值之和，你可能会说：倍增啊！

那如果出题人：我还要你支持修改某个点的权值！

或者再 j 一点：我还要你支持修改点 u 到点 v 路径上点的权值！

那就得用树链剖分了。

2. 什么是树链剖分

上面那个问题，树上区间修改。

区间修改最常见做法就是线段树了。

那我们怎么用线段树维护一颗。。。普通的树呢？

那就给普通的树的每个节点标个号，然后放线段树里呗。区间维护。

但如果随便标号，那点 u 到点 v 路径不一定标号是连续的啊，你线段树维护个 j 啊

所以我们现在引入一个（堆）姿势：

那么这些姿势有什么用呢？先看一道题吧！

传送门=￣ω￣=

我们先来看张图：

图中标在边上了，但也不影响我们学。。。

标号方法是：跑 dfs，先给当前节点标号，再给重儿子标号（重儿子和当前节点在一个重链上），然后对重儿子递归，最后给剩下的别的儿子标号（别的儿子不和当前节点在一个重链上，所以新建重链，把新建的重链的顶端节点设为那个” 别的儿子 “）、递归（图中是先给重 (zhong) 边标号，再给剩下的边标号）。标号从小到大。

不难发现一条重链上的标号是连续的，比如点 1 到点 14，点 2 到点 12

这意味着在线段树中，它们是在一个连续的区间里的，而不是像随便标号时断断续续的。

这样就很好用线段树处理了。

如果两个节点不在一条重链上呢？比如图中的点 11 和点 10，我们要求它们之间的路径上的点权和

那我们就看，点11所在的重链是11->6->2，点10所在的重链是10（10所在的重链只有一个点，就是10）。所以我们就先求出重链11->6->2 上的点权和、重链 10 上的点权和。这两条重链在线段树上都是一段连续的区间，可以直接 log₂n 求出

这时候我们发现还有4->1 的重链没有计算，就把它的点权和计算出来，三个重链的点权和加在一起就得到了答案。

所以我们要记录的是：
1. pos[i] 点 i 的标号
2. top[i] 点 i 所在重链的顶端节点
3. siz[i] 以点 i 为根的子树的大小
4. dep[i] 点 i 的深度
5. fa[i] 点 i 的父亲节点

我们先跑一边 dfs，算出 fa、size、dep

然后再跑一边 dfs，根据 size[i] 找出点 i 的重儿子，然后算出 pos、top。

具体代码：

void init1(int u)//第一个 dfs
{
    siz[u]=1,dep[u]=dep[fa[u]]+1;
    for(int i=0;i<g[u].size();i++)//g[u] 为点 u 的邻接表
        if(g[u][i]!=fa[u])fa[g[u][i]]=u,init1(g[u][i]),siz[u]+=siz[g[u][i]];//向下递归
}
void init2(int u)//第二个 dfs
{
    int nxt=0,maxn=0;pos[u]=cnt++;//设置 pos[u]
    for(int i=0;i<g[u].size();i++)//找出重儿子
        if(g[u][i]!=fa[u]&&siz[g[u][i]]>maxn)nxt=g[u][i],maxn=siz[g[u][i]];
    if(!nxt)return;//不存在重儿子就 return
    top[nxt]=top[u],init2(nxt);//把重儿子加到 u 所在的重链里，然后递归重儿子
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&g[u][i]!=nxt)
            top[g[u][i]]=g[u][i],init2(g[u][i]);//新建重链
}

搞完这些就很 easy 了，因为一段重链在线段树里是一段连续的区间（这是坠重要的）。

我们在查询/修改从点 u 到点 v 的路径时，先找到所在重链的顶端节点（top）深度较深的（因为这样能让 u 和 v 同步提升，防止一个提到根节点了，另一个还没提，这时候你就不知道提谁了），注意不能按照 u 和 v 的深度来提！比如 top 较深的点是 u，然后就用线段树处理区间 $[pos[top[u]],pos[u]]$（因为 top[u] 的标号一定比 u 要小），再设置 u 为 fa[top[u]]，把 u 往上提，直至 u 和 v 在一条重链上（即 top[u]==top[v]）。这时候可能 u 和 v 之间还有一段距离，此时 u 和 v 已经在一条重链上，直接处理它们之间的区间就行了。

然后复杂度就是：$O(Nlog_{2} N+Qlog^{2} N)$

同时这个复杂度也是一般的树链剖分的复杂度。因为重链个数不会超过 $log_{2} N$个，线段树复杂度是 $log_{2} N$的。网上有证明，我就不做过多赘述

代码：

#include <bits/stdc++.h>
#define LS(a) (a<<1)
#define RS(a) ((a<<1)|1)
#define NS (30005)
using namespace std;
struct N{int l,r,max,sum;N(){l=r=max=sum=0;}}e[NS<<2];
int n,fa[NS],dep[NS],siz[NS],pos[NS],top[NS],w[NS],cnt=1,q;
char opt[10];
vector<int> g[NS];
void update(int a)
{e[a].max=max(e[LS(a)].max,e[RS(a)].max),e[a].sum=e[LS(a)].sum+e[RS(a)].sum;}
void build(int l,int r,int a)
{
    e[a].l=l,e[a].r=r;
    if(l==r){e[a].sum=e[a].max=w[l];return;}
    build(l,(l+r)>>1,LS(a)),build(((l+r)>>1)+1,r,RS(a)),update(a);
}
void change(int x,int k,int a)
{
    if(e[a].l==x&&e[a].r==x){e[a].sum=e[a].max=k;return;}
    if(x<=((e[a].l+e[a].r)>>1))change(x,k,LS(a));
    else change(x,k,RS(a));
    update(a);
}
int query_sum(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].sum;
    int tot=0;
    if(l<=((e[a].l+e[a].r)>>1))tot+=query_sum(l,r,LS(a));
    if(r>((e[a].l+e[a].r)>>1))tot+=query_sum(l,r,RS(a));
    return tot;
}
int query_max(int l,int r,int a)
{
    if(l<=e[a].l&&e[a].r<=r)return e[a].max;
    int tot=INT_MIN;
    if(l<=((e[a].l+e[a].r)>>1))tot=max(tot,query_max(l,r,LS(a)));
    if(r>((e[a].l+e[a].r)>>1))tot=max(tot,query_max(l,r,RS(a)));
    return tot;
}
void init1(int u)
{
    siz[u]=1,dep[u]=dep[fa[u]]+1;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u])fa[g[u][i]]=u,init1(g[u][i]),siz[u]+=siz[g[u][i]];
}
void init2(int u)
{
    int nxt=0,maxn=0;pos[u]=cnt++;
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&siz[g[u][i]]>maxn)nxt=g[u][i],maxn=siz[g[u][i]];
    if(!nxt)return;
    top[nxt]=top[u],init2(nxt);
    for(int i=0;i<g[u].size();i++)
        if(g[u][i]!=fa[u]&&g[u][i]!=nxt)
            top[g[u][i]]=g[u][i],init2(g[u][i]);
}
int query(int a,int b,bool f)
{
    int tot=f?0:INT_MIN;
    while(top[a]!=top[b])
    {
        if(dep[top[a]]>dep[top[b]])swap(a,b);
        if(f)tot+=query_sum(pos[top[b]],pos[b],1);
        else tot=max(tot,query_max(pos[top[b]],pos[b],1));
        b=fa[top[b]];
    }
    if(pos[a]>pos[b])swap(a,b);
    if(f)tot+=query_sum(pos[a],pos[b],1);
    else tot=max(tot,query_max(pos[a],pos[b],1));
    return tot;
}
int main()
{
    scanf("%d",&n);
    for(int i=1,a,b;i<n;i++)
        scanf("%d%d",&a,&b),g[a].push_back(b),g[b].push_back(a);
    init1(1),top[1]=1,init2(1);
    for(int i=1;i<=n;i++)scanf("%d",&w[pos[i]]);
    build(0,cnt-1,1),scanf("%d",&q);
    for(int i=1,a,b;i<=q;i++)
    {
        scanf("%s%d%d",opt,&a,&b);
        if(!strcmp(opt,"CHANGE"))change(pos[a],b,1);
        else if(!strcmp(opt,"QMAX"))printf("%d\n",query(a,b,0));
        else printf("%d\n",query(a,b,1));
    }
    return 0;
}

void init1(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)
        {
                init1(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 init2(int x,int tp)                               //tp=重链父节点
{
    top[x]=tp,pos[x]=++tim,rak[tid[x]]=x;
    if(son[x]==-1)return;
    init2(son[x],tp);
    for(int i=fst[x];i!=-1;i=nxt[i])if(v[i]!=son[x]&&v[i]!=fa[x])init2(v[i],v[i]);
}