树链剖分（Heavy-Light Decomposition）小结

树链剖分，可以把一棵树划分成多条链，对于每条链可以用线段树等数据结构进行维护，将树形结构的问题转化。

常见的方法是轻重链剖分，即 Heavy-Light Decomposition。

[notice]这是一篇意识流式的总结，如果要入门树链剖分请不要看这篇……[/notice]

前置知识

LCA、线段树……

一些定义

需要构造如下数组：

• size[x]：以 x 为根的子树的节点总数；
• deep[x]：x 的深度；
• son[x]：x 通过重链通向的儿子节点；
• fa[x]：x 的父节点；
• top[x]：x 所在重链的顶端节点；
• id[x]：节点 x 在线段树中的下标位置；
• v[x]：节点 x 的权值（对于边权，可以把边的权值归属于其下面的点，转化为点权处理）。

另建一棵线段树存储重链信息。

如果 v 是 u 的儿子中 size 最大的一个，则 (u,v) 是重边，v 是 u 的重儿子，u 通向的其他儿子是轻边。

连续的重边形成重链。通过 id[] 可以将一条重链映射到线段树上的一条线段。

关于复杂度的结论

结论一： 如果 $(u,v)$ 为轻边，则 size[v] 不会大于 size[u]/2。 结论二： 重链和轻边的数量级相当。 由此可以得到： 结论三： 从某一个点到根上经过的重链或轻边的总数在 $\log (n)$ 级别。这是树链剖分的核心。

据此，对于一条链上的操作可以做到 $\log(n)$。对于链上的修改，整条重链可以对应线段树的一个区间，存储 top[] 可以实现直接调到重链顶端，达到优化时间复杂度的目的。

实现

第一遍 DFS 构造出 size[],son[],fa[],deep[]，第二遍 DFS 造出 top[],id[]。

对于两点的路径修改，直接求出 LCA 后一直往上跳即可。 对于子树修改，直接当成 DFS 序处理。

对于构造 id[] 的 DFS 需要注意：本质上 id[] 是一个时间戳，即 DFS 序。为了使得重边在造出来的序中连续，便于线段树的处理，在遍历的时候要先遍历重儿子。涉及子树的操作也会方便很多。

代码

洛谷模板题 P3384：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>

using namespace std;
// #define int long long

inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}

const int maxn=1e5+5;
const int maxe=2*maxn;

int n,m,root,tt;

void add(int &x,int y){
    x=(x+y%tt)%tt;
}

class SegmentTree{

    #define mid (((tr-tl)>>1)+tl)
    #define ls ((p<<1))
    #define rs ((p<<1)+1)

    private:
        int tree[maxn*4],tag[maxn*4];

        void push_down(int tl,int tr,int p){
            add(tree[ls],tag[p]*(mid-tl+1)%tt);
            add(tag[ls],tag[p]);
            add(tree[rs],tag[p]*(tr-(mid+1)+1)%tt);
            add(tag[rs],tag[p]);
            tag[p]=0;
        }

    public:
        SegmentTree(){
            memset(tree,0,sizeof(tree));
            memset(tag,0,sizeof(tag));
        }

        void update(int x,int tl,int tr,int p,int delta){
            if (tl==tr && tl==x){
                add(tree[p],delta);
                return;
            }
            push_down(tl,tr,p);
            if (x<=mid  ) update(x,tl,mid,ls,delta);
            if (mid+1<=x) update(x,mid+1,tr,rs,delta);
            tree[p]=(tree[ls]+tree[rs])%tt;
        }

        void update(int sl,int sr,int tl,int tr,int p,int delta){
            if (sl<=tl && tr<=sr){
                add(tree[p],(tr-tl+1)*delta%tt);
                add(tag[p],delta);
                return;
            }
            push_down(tl,tr,p);
            if (sl<=mid  ) update(sl,sr,tl,mid,ls,delta);
            if (mid+1<=sr) update(sl,sr,mid+1,tr,rs,delta);
            tree[p]=(tree[ls]+tree[rs])%tt;
        }

        int query(int x,int tl,int tr,int p){
            if (tl==tr && x==tl) return tree[p]%tt;
            push_down(tl,tr,p);
            int ret=0;
            if (x<=mid  ) add(ret,query(x,tl,mid,ls));
            if (mid+1<=x) add(ret,query(x,mid+1,tr,rs));
            return ret;
        }

        int query(int sl,int sr,int tl,int tr,int p){
            if (sl<=tl && tr<=sr) return tree[p]%tt;
            push_down(tl,tr,p);
            int ret=0;
            if (sl<=mid  ) add(ret,query(sl,sr,tl,mid,ls));
            if (mid+1<=sr) add(ret,query(sl,sr,mid+1,tr,rs));
            return ret;
        }
};

int tot=0,lnk[maxn],nxt[maxe],to[maxe];
int size[maxn],deep[maxn],fa[maxn];
int v[maxn];

void add_edge(int x,int y){
    tot++;to[tot]=y;
    nxt[tot]=lnk[x];lnk[x]=tot;
}

int f[maxn][25];

int get_lca(int x,int y){
    if (deep[x]<deep[y]) swap(x,y);
    for (int i=23;i>=0;i--) if (deep[f[x][i]] >= deep[y]) x=f[x][i];
    if (x==y) return x;
    for (int i=23;i>=0;i--) if (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    return fa[x];
}

namespace HLD{
    int son[maxn],top[maxn],id[maxn];

    void make_tree(int x){
        size[x]=1;
        f[x][0]=fa[x];for (int i=1;i<=23;i++) f[x][i]=f[f[x][i-1]][i-1];
        int max_size=0,k=-1;
        for (int i=lnk[x];i;i=nxt[i]) if (to[i]!=fa[x]){
            fa[to[i]]=x;deep[to[i]]=deep[x]+1;
            make_tree(to[i]);
            size[x]+=size[to[i]];
            if (size[to[i]]>max_size) max_size=size[to[i]],k=to[i];
        }
        if (k!=-1) son[x]=k;
    }

    void make_chain(int x){
        id[x]=++id[0];
        if (son[fa[x]]!=x) top[x]=x; else top[x]=top[fa[x]];
        if (son[x]) make_chain(son[x]);
        for (int i=lnk[x];i;i=nxt[i]) if (to[i]!=fa[x] && to[i]!=son[x]){
            make_chain(to[i]);
        }
    }

    void change_single(int x,int l,int delta,SegmentTree &tree){
        while (x!=l){
            if (top[x]!=x){
                if (deep[top[x]]>=deep[l]) tree.update(id[top[x]]+1,id[x],1,n,1,delta),x=top[x];
                else tree.update(id[l]+1,id[x],1,n,1,delta),x=l;
            } else tree.update(id[x],1,n,1,delta),x=fa[x];
        }
        tree.update(id[x],1,n,1,delta);
    }

    void change_chain(int x,int y,int delta,SegmentTree &tree){
        int l=get_lca(x,y);
        change_single(x,l,delta,tree);
        change_single(y,l,delta,tree);
        tree.update(id[l],1,n,1,-delta);
    }

    int query_single(int x,int l,SegmentTree &tree){
        int ret=0;
        while (x!=l){
            if (top[x]!=x){
                if (deep[top[x]]>=deep[l]) add(ret,tree.query(id[top[x]]+1,id[x],1,n,1)),x=top[x];
                else add(ret,tree.query(id[l]+1,id[x],1,n,1)),x=l;
            } else add(ret,tree.query(id[x],1,n,1)),x=fa[x];
        }
        add(ret,tree.query(id[x],1,n,1));
        return ret;
    }

    int query_chain(int x,int y,SegmentTree &tree){
        int l=get_lca(x,y);
        return (query_single(x,l,tree)+query_single(y,l,tree)-tree.query(id[l],1,n,1)+tt)%tt;
    }

    void change_subtree(int x,int delta,SegmentTree &tree){
        tree.update(id[x],id[x]+size[x]-1,1,n,1,delta);
    }

    int query_subtree(int x,SegmentTree &tree){
        return tree.query(id[x],id[x]+size[x]-1,1,n,1);
    }
}

SegmentTree tree;

signed main(){
    n=read(),m=read(),root=read(),tt=read();
    for (int i=1;i<=n;i++) v[i]=read();
    for (int i=1;i<n;i++){
        int x=read(),y=read();
        add_edge(x,y);add_edge(y,x);
    }

    deep[root]=1;
    HLD::make_tree(root);
    HLD::make_chain(root);

    for (int i=1;i<=n;i++) tree.update(HLD::id[i],1,n,1,v[i]);

    while (m--){
        int opt=read(),x,y,z;
        switch(opt){
            case 1:
                x=read(),y=read(),z=read()%tt;
                HLD::change_chain(x,y,z,tree);
                break;
            case 2:
                x=read(),y=read();
                printf("%d\n",HLD::query_chain(x,y,tree));
                break;
            case 3:
                x=read(),z=read()%tt;
                HLD::change_subtree(x,z,tree);
                break;
            case 4:
                x=read();
                printf("%d\n",HLD::query_subtree(x,tree));
                break;
        }
    }

    return 0;
}