https://oi-wiki.org/graph/hld/
一些给自己看的补充说明：
重儿子指的是：子树最大的子节点。如果有多个，取其一。如果没有子节点，就没有重儿子。

轻儿子：其它所有儿子。

若干条首尾衔接的重边构成 重链。

注意示意图：如果一个节点它不是重儿子，那么它所在的重链它就是“开头”。

$ fa(x)$ 表示节点 x 在树上的父亲。
$dep(x)$ 表示节点 x 在树上的深度。
$siz(x)$ 表示节点 x 的子树的节点个数。
$son(x)$ 表示节点 x 的 重儿子。
$top(x)$ 表示节点 x 所在 重链 的顶部节点（深度最小）。
$dfn(x)$ 表示节点 x 的 DFS 序，也是其在线段树中的编号。
$rnk(x)$ 表示 DFS 序所对应的节点编号，有 $rnk(dfn(x))=x。$

通过两次dfs处理出上面所有信息。第一次处理出$fa、dep、siz、son。$
第二次处理出$dfn、rnk、top。$
ps.该板子里有一个细节，运用$dep[u]!=0$来判断不是父节点，因此$dep[1]$要在开始dfs时设置为$1$

int dep[N],siz[N],fa[N],son[N];
int dfn[N],rnk[N],top[N],cnt=0;
vector<vector<int>> g;
void dfs1(int u){
    siz[u] = 1;
    son[u] = -1;
    for(auto v:g[u]){
        if(!dep[v]){
            dep[v] = dep[u]+1;
            fa[v] = u;
            dfs1(v);
            siz[u] += siz[v];
            if(son[u] == -1 || siz[v] > siz[son[u]])
                son[u] = v;
        }
    }
}
void dfs2(int u,int t){
    top[u] = t;
    dfn[u] = ++cnt;
    rnk[cnt] = u;
    if(son[u]== -1 ) return;
    dfs2(son[u],t);
    for(auto v:g[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

重链剖分的性质

1.树上每个节点都属于且仅属于一条重链。
2.所有的重链将整棵树 完全剖分。
3.在剖分时重边优先遍历，最后树的 DFS 序上，重链内的 DFS 序是连续的。按 DFN 排序后的序列即为剖分后的链。
4.当我们向下经过一条 轻边 时，所在子树的大小至少会除以二。
5.根据4，对于树上的任意一条路径，把它拆分成从 LCA 分别向两边往下走，分别最多走 $O(\log n)$ 次，因此，树上的每条路径都可以被拆分成不超过 $O(\log n) $条重链。所以以下三个用法为什么要用重链剖分，因为这一步的时间复杂度优化到了$O(logn)$

重链剖分的作用

1.求lca：

如果重链顶不同，就跳到重链顶的父节点。直到重链顶相同（即此时在一条重链上），此时深度较小的节点就是lca。注意跳的时候不是u和v同时跳，而是每次要选择深度更大的点跳

int lca(int u, int v) {
  while (top[u] != top[v]) {
    if (dep[top[u]] > dep[top[v]])
      u = fa[top[u]];
    else
      v = fa[top[v]];
  }
  return dep[u] > dep[v] ? v : u;
}

2.路径上信息

可以求路径上权值和、或这路径上最大权值等等，需要结合线段树或者树状数组等数据结构。
可以分析一下u，v组成的路径和重链的关系。u、v组成的路径是u和v一直往重链顶的父亲跳，其间的路径，以及当u和v跳到同一条重链，此时深度较大的节点再到深度较小的节点的路径。
注意到u，v在往重链顶的父亲跳时，其dfn序是连续的。所以可以用线段树或者树状数组快速维护和获得这一段路径的信息。

3.子树维护

维护子树上的信息，譬如将以 x 为根的子树的所有结点的权值增加 v。
注意到在 DFS 搜索的时候，子树中的结点的 DFS 序是连续的。
则每一个结点记录 bottom 表示所在子树连续区间末端的结点。这样就把子树信息转化为连续的一段区间信息。

例题:树上统计

对一棵有 n 个节点，节点带权值的静态树，进行三种操作共 q 次：
1.修改单个节点的权值；
2.查询 u 到 v 的路径上的最大权值；
3.查询 u 到 v 的路径上的权值之和。
保证 $1\le n\le 30000，0\le q\le 200000。$
这就用到上面提到的重链剖分维护路径上信息的作用，我们选择线段树来进行单点修改和区间查询。
将每个点的dfn序映射到线段树的”l,r”。具体的逻辑上面说得比较清楚了，具体看代码中的querymax和querysum函数即可:

#include<bits/stdc++.h>
#define LOCAL//delete when submit!!!!!!

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

const int N = 3e4+10;
int dep[N],siz[N],fa[N],son[N];
int dfn[N],rnk[N],top[N],cnt=0;
int w[N];//节点的权值
vector<vector<int>> g;
int n;
struct SegmentTree{
    int sum[N<<2],maxv[N<<2];
    void pushup(int u){
        sum[u] = sum[u<<1]+sum[u<<1|1];
        maxv[u] = max(maxv[u<<1],maxv[u<<1|1]);
    }
    void build(int u,int l,int r){
        if(l==r){
            sum[u] = w[rnk[l]];
            maxv[u] = w[rnk[l]];
            return;
        }
        int mid = (l+r)>>1;
        build(u<<1,l,mid);
        build(u<<1|1,mid+1,r);
        pushup(u);
    }
    void modify(int u,int l,int r,int co,int val){
        if(l==r){
            sum[u] = val;
            maxv[u] = val;
            return;
        }
        int mid = l+r>>1;
        if(co<=mid)
            modify(u<<1,l,mid,co,val);
        else
            modify(u<<1|1,mid+1,r,co,val);
        pushup(u);
    }   

    int query_sum(int u,int l,int r,int x,int y){
        if(l>y||x>r) return 0;
        if(x<=l&&y>=r) return sum[u];
        int mid = (l+r)>>1;
        //由于设置了if(l>y||x>r) return 0;  所以这里不需要判断x是否小于等于mid，y是否大于mid 直接query即可。
        return query_sum(u<<1,l,mid,x,y) + query_sum(u<<1|1,mid+1,r,x,y);
    }
    int query_max(int u,int l,int r,int x,int y){
        if(l>y||x>r) return -1e9;
        if(x<=l&&y>=r) return maxv[u];
        int mid = (l+r)>>1;
        int res = -1e9;
        // if(x<=mid) res = max(res,query_max(u<<1,l,mid,x,y));
        // if(y>mid) res = max(res,query_max(u<<1|1,mid+1,r,x,y));
        // return res;
        //由于设置了if(l>y||x>r) return -1e9;  所以这里不需要判断x是否小于等于mid，y是否大于mid 直接query即可。
        //否则就要像上面两行一样判断一下
        return max(query_max(u<<1,l,mid,x,y),query_max(u<<1|1,mid+1,r,x,y));
    }
}st;
void dfs1(int u){
    siz[u] = 1;
    son[u] = -1;//用-1来表示没有重儿子 即自身是叶子节点
    for(auto v:g[u]){
        if(!dep[v]){
            dep[v] = dep[u]+1;
            fa[v] = u;
            dfs1(v);
            siz[u] += siz[v];
            if(son[u] == -1 || siz[v] > siz[son[u]])
                son[u] = v;
        }
    }
}
void dfs2(int u,int t){
    top[u] = t;
    dfn[u] = ++cnt;
    rnk[cnt] = u;
    if(son[u]== -1 ) return;
    dfs2(son[u],t);
    for(auto v:g[u]){
        if(v==fa[u]||v==son[u]) continue;
        dfs2(v,v);
    }
}

int querymax(int x,int y){
    int fx = top[x],fy = top[y];
    int ret = -1e9;
    while(fx!=fy){
        if(dep[fx]>dep[fy]){
            ret = max(ret,st.query_max(1,1,n,dfn[fx],dfn[x]));
            //统计x到重链顶的路径信息
            x = fa[fx];
        }else{
            ret = max(ret,st.query_max(1,1,n,dfn[fy],dfn[y]));
            y = fa[fy];
        }
        fx = top[x];
        fy = top[y];
    }
    //到了同一条重链上，但是记得深度较大的节点还需要走到深度较小的节点上。
    //这个时候x和y的点的信息都是没有算过的
    if(dfn[x] < dfn[y]){
        ret = max(ret,st.query_max(1,1,n,dfn[x],dfn[y]));
    }else{
        ret = max(ret,st.query_max(1,1,n,dfn[y],dfn[x]));
    }
    return ret;
}
int querysum(int x,int y){
    int ret = 0;
    int fx = top[x],fy = top[y];
    while(fx!=fy){
        if(dep[fx]>dep[fy]){
            ret += st.query_sum(1,1,n,dfn[fx],dfn[x]);
            x = fa[fx];
        }else{
            ret += st.query_sum(1,1,n,dfn[fy],dfn[y]);
            y = fa[fy];
        }
        fx = top[x];
        fy = top[y];
    }
    if(dfn[x]<dfn[y]){
        ret += st.query_sum(1,1,n,dfn[x],dfn[y]);
    }else{
        ret += st.query_sum(1,1,n,dfn[y],dfn[x]);
    }
    return ret;
}

void solve(){
    cin>>n;
    g = vector<vector<int>>(n+1);
    for(int i=0;i<n-1;i++){
        int u,v; cin>>u>>v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++) cin>>w[i];
    dep[1] = 1;
    dfs1(1);
    dfs2(1,1);
    st.build(1,1,n);
    int q; cin>>q;
    while(q--){
        string op;
        int u,v;
        cin>>op>>u>>v;
        if(op=="CHANGE"){
            st.modify(1,1,n,dfn[u],v);
        }else if(op=="QMAX"){
            cout<<querymax(u,v)<<endl;
        }else {
            cout<<querysum(u,v)<<endl;
        }
    }
}

int main(){     
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    std::ios::sync_with_stdio(0);std::cout.tie(0);std::cin.tie(0);
    int T = 1;
#ifdef MULTI_TEST
    cin>>T;
#endif
    while(T--){
        solve();
    }
    return 0;
}