重链剖分

对于任意一个位于树上的节点

重子节点 表示其子节点中子树最大的子结点。如果有多个子树最大的子结点，取其一。如果没有子节点，就无重子节点。

轻子节点 表示剩余的所有子结点

重边表示这个结点到重子节点的边

轻边表示这个结点到其他轻子节点的边为

重链表示若干条首尾衔接的重边

把落单的结点也当作重链，那么整棵树就被剖分成若干条重链

借用一下OI-wiki的图片

实现

首先，要先预处理几个变量

每个结点的父节点，子树大小，深度，重子节点，所在重链的链顶，重边优先遍历时的DFS序，DFS序对应的结点编号

struct node{
    int fa/*父节点*/,dep/*深度*/,siz/*子树大小*/,son/*重子节点*/,top/*所在链的链顶*/;
    int dfn/*DFS序*/,rnk/*对应编号*/;
}T[MAXM];

预处理的方法就是两个DFS

第一遍：记录父节点，深度，子树大小，重子节点

inline void Dfs1(int q){
    T[q].son=-1;
    T[q].siz=1;
    for(int j=head[q];j;j=NEXT[j]){
        if(j=T[q].fa) continue;
        T[j].dep=T[q].dep+1;
        T[j].fa=q;
        Dfs1(j);
        T[q].siz+=T[j].siz;
		if((T[q].son==-1)||(T[j].siz>T[T[q].son].siz)) T[q].son=j;
    }
}

第二遍：记录所在链的链顶，DFS序，对应的rank

inline void Dfs2(int q,int v){
    T[q].top=v;
	T[q].dfn=++cnt;
	T[cnt].rnk=q;
	if(T[q].son==-1)
        return;
	Dfs2(T[q].son,v);
    for(int j=head[q];j;j=NEXT[j]){
        if((j!=T[q].fa)&&(j!=T[q].son))
            Dfs2(j,j);
    }
}

有啥用

首先，要用线段树维护

然后就可以

求树上两点路径权值和
维护子树上的信息(譬如将以\(x\)为根的子树的所有结点的权值增加\(v\))
求LCA (\(O(\log n)\)甚至常数小)

根本思想：对于两个不在同一重链内的节点,让他们不断地跳,使得他们处于同一重链上

求树上两点路径权值和

这个比较抽象

首先，怎么跳？

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

结合深度dep

我们可以每次都让两个点的top中dep大的向上跳

每次跳直接让x跳到T[x].top即可，然后线段树上更新

在最后两个点处于同一重边时因为结论

x 到 T[x].top 中的节点在线段树上是连续的

所以可以直接进行线段树的查询

子树操作

因为一棵树的子树在线段树上是连续的

所以直接线段树修改即可

`LCA`

这个和求树上两点路径权值和差不多一样(

就是更简单一些

只要知道树上倍增求LCA的应该也都懂

甚至不用线段树

代码实现

int head[MAXM],NEXT[MAXM],TO[MAXM],cnt,tot,a[MAXM];
namespace Grape{
    inline void add(int u,int v){
        NEXT[++tot]=head[u];
        TO[tot]=v;
        head[u]=tot;
    }
}
namespace ST{
    #define mid (l+r)/2
    #define lC q<<1
    #define rC q<<1|1
    struct St{
        long long l,r,siz;
        long long lazy,dat;
    }t[0x66ccff];
    void build(int q,int l,int r){
        t[q].l=l;
        t[q].r=r;
        t[q].siz=r-l+1;
        if(l==r){
            t[q].dat=a[l];
            return;
        }
        build(lC,l,mid);
        build(rC,mid+1,r);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    void lazy(int q){
        t[lC].lazy+=t[q].lazy;
        t[lC].dat+=(t[lC].r-t[lC].l+1)*t[q].lazy;
        t[rC].lazy+=t[q].lazy;
        t[rC].dat+=(t[rC].r-t[rC].l+1)*t[q].lazy;
        t[q].lazy=0;
    }
    void change(int q,int l,int r,int v){
        if(t[q].l>r||t[q].r<l) return;
        if(t[q].l>=l && t[q].r<=r){
            t[q].lazy+=v;
            t[q].dat+=(t[q].r-t[q].l+1)*v;
            return;
        }
        if(t[q].lazy>0)
            lazy(q);
        change(lC,l,r,v);
        change(rC,l,r,v);
        t[q].dat=t[lC].dat+t[rC].dat;
    }
    long long asksum(int q,int l,int r){
        if(t[q].l>r || t[q].r<l) 
            return 0;
        if(t[q].l>=l && t[q].r<=r) 
            return t[q].dat;
        if(t[q].lazy>0) 
            lazy(q);
        return asksum(lC,l,r)+asksum(rC,l,r); 
    }
}
namespace killTree{
    struct node{
        int fa,dep,siz,son,top;
        int dfn,rnk;
    }T[MAXM];
    inline void Dfs1(int q){
        T[q].son=-1;
        T[q].siz=1;
        for(int j=head[q];j;j=NEXT[j]){
            if(j=T[q].fa) continue;
            T[j].dep=T[q].dep+1;
            T[j].fa=q;
            Dfs1(j);
            T[q].siz+=T[j].siz;
            if((T[q].son==-1)||(T[j].siz>T[T[q].son].siz)) T[q].son=j;
        }
    }
    inline void Dfs2(int q,int v){
        T[q].top=v;
        T[q].dfn=++cnt;
        T[cnt].rnk=q;
        if(T[q].son==-1)
            return;
        Dfs2(T[q].son,v);
        for(int j=head[q];j;j=NEXT[j]){
            if((j!=T[q].fa)&&(j!=T[q].son))
                Dfs2(j,j);
        }
    }
    inline void TreeAdd(int x,int y,int val){
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) 
                std::swap(x,y);
            ST::change(1,T[T[x].top].dfn,T[x].dfn,val);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) 
            std::swap(x,y);
        ST::change(1,T[x].dfn,T[y].dfn,val);
    }
    inline int TreeSum(int x,int y){
        int ans=0;
        while(T[x].top!=T[y].top){
            if(T[T[x].top].dep<T[T[y].top].dep) std::swap(x,y);
            ans=ans+ST::asksum(1,T[T[x].top].dfn,T[x].dfn);
            x=T[T[x].top].fa;
        }
        if(T[x].dep>T[y].dep) std::swap(x,y);
        return ans+ST::asksum(1,T[x].dfn,T[y].dfn);
    }
    inline void AddTree(int x,int y,int z){
        ST::change(1,T[x].dfn,T[x].dfn+T[x].siz-1,z);
    }
    inline int AskTree(){
        ST::asksum(1,T[x].dfn,T[x].dfn+T[x].siz-1);
    }
}