树链剖分入门

例题
POJ 3237（）
BZOJ 3083
BZOJ 3531
BZOJ 3589
BZOJ 3626
将树上问题通过dfs序的性质转换为区间问题，从而对树上修改时就可转化为相应的区间修改。再通过引入重儿子，重链一系列概念将时间复杂度也变成了可以接受的层次

通过两次dfs求出树上一系列的信息

void dfs1(int u){
     sz[u]=1;
     dep[u]=dep[fa[u]]+1;

     for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v==fa[u]) continue;
        fa[v]=u;
        dfs1(v);
        sz[u]+=sz[v];

        if(sz[son[u]]<sz[v]) son[u]=v;
     }
}

void dfs2(int u){

    static int T=0;
    seq[pos[u]=++T]=u;

    if(son[fa[u]]==u) top[u] = top[fa[u]];
    else top[u]=u;

    if(son[u]) dfs2(son[u]);

    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].to;
        if(v!=fa[u]&&v!=son[u]) dfs2(v);
    }
}

更新树上信息可分为 更新点权和更新边权
由于dfs序rk[]和pos[]数组是点的相应顺序排列的
所以当处理点权的时候我们直接更新两点间的信息即可
而当更新边权时，我们选择架空根节点，那么点权就可以变成边权了，所以对应跳重链的过程也有一点不同。具体看代码

点权

int QueryMax(int x,int y){
    int re=-inf;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        re=max(re,treeQueryMax(1,1,n,pos[top[x]],pos[x]));
        x=fa[top[x]];
    }
    if(dep[x]<dep[y])
        swap(x,y);
    return re=max(re,treeQueryMax(1,1,n,pos[y],pos[x]));
}

边权
架空根节点后 dfs序的每个点的价值就变为该点与其父亲节点的边权值
那么在跳重链的过程中，假如dep[x]<dep[y]，我们更新的其实应该是son[x]-y对应的边权（即点权）因为每个点x对应的权值是只向他的父亲的。
所以当两个点相同时就已经更新完成了

int QueryMax(int x,int y){
    int re=-inf;
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        re=max(re,treeQueryMax(1,1,n,pos[top[x]],pos[x]));
        x=fa[top[x]];
    }
    if(x==y) return ;
    if(dep[x]<dep[y]) swap(x,y);
    return re=max(re,treeQueryMax(1,1,n,pos[son[y]],pos[x]));
}