树链剖分（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;
}

 {

    
    
    

    :
         tree[maxn*],tag[maxn*];

        {
            (tree[ls],tag[p]*(mid-tl)%tt);
            (tag[ls],tag[p]);
            (tree[rs],tag[p]*(tr-(mid))%tt);
            (tag[rs],tag[p]);
            tag[p]=;
        }

    :
        (){
            (tree,,(tree));
            (tag,,(tag));
        }

        {
             (tl==tr && tl==x){
                (tree[p],delta);
                ;
            }
            (tl,tr,p);
             (x<=mid  ) (x,tl,mid,ls,delta);
             (mid<=x) (x,mid,tr,rs,delta);
            tree[p]=(tree[ls]+tree[rs])%tt;
        }

        {
             (sl<=tl && tr<=sr){
                (tree[p],(tr-tl)*delta%tt);
                (tag[p],delta);
                ;
            }
            (tl,tr,p);
             (sl<=mid  ) (sl,sr,tl,mid,ls,delta);
             (mid<=sr) (sl,sr,mid,tr,rs,delta);
            tree[p]=(tree[ls]+tree[rs])%tt;
        }

        {
             (tl==tr && x==tl)  tree[p]%tt;
            (tl,tr,p);
             ret=;
             (x<=mid  ) (ret,(x,tl,mid,ls));
             (mid<=x) (ret,(x,mid,tr,rs));
             ret;
        }

        {
             (sl<=tl && tr<=sr)  tree[p]%tt;
            (tl,tr,p);
             ret=;
             (sl<=mid  ) (ret,(sl,sr,tl,mid,ls));
             (mid<=sr) (ret,(sl,sr,mid,tr,rs));
             ret;
        }
};

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

{
    tot++;to[tot]=y;
    nxt[tot]=lnk[x];lnk[x]=tot;
}

 f[maxn][];

{
     (deep[x]<deep[y]) (x,y);
     ( i=;i>=;i--)  (deep[f[x][i]] >= deep[y]) x=f[x][i];
     (x==y)  x;
     ( i=;i>=;i--)  (f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
     fa[x];
}

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

    {
        size[x]=;
        f[x][]=fa[x]; ( i=;i<=;i++) f[x][i]=f[f[x][i]][i];
         max_size=,k=;
         ( i=lnk[x];i;i=nxt[i])  (to[i]!=fa[x]){
            fa[to[i]]=x;deep[to[i]]=deep[x];
            (to[i]);
            size[x]+=size[to[i]];
             (size[to[i]]>max_size) max_size=size[to[i]],k=to[i];
        }
         (k!=) son[x]=k;
    }

    {
        id[x]=++id[];
         (son[fa[x]]!=x) top[x]=x;  top[x]=top[fa[x]];
         (son[x]) (son[x]);
         ( i=lnk[x];i;i=nxt[i])  (to[i]!=fa[x] && to[i]!=son[x]){
            (to[i]);
        }
    }

    {
         (x!=l){
             (top[x]!=x){
                 (deep[top[x]]>=deep[l]) tree.(id[top[x]],id[x],,n,,delta),x=top[x];
                 tree.(id[l],id[x],,n,,delta),x=l;
            }  tree.(id[x],,n,,delta),x=fa[x];
        }
        tree.(id[x],,n,,delta);
    }

    {
         l=(x,y);
        (x,l,delta,tree);
        (y,l,delta,tree);
        tree.(id[l],,n,,-delta);
    }

    {
         ret=;
         (x!=l){
             (top[x]!=x){
                 (deep[top[x]]>=deep[l]) (ret,tree.(id[top[x]],id[x],,n,)),x=top[x];
                 (ret,tree.(id[l],id[x],,n,)),x=l;
            }  (ret,tree.(id[x],,n,)),x=fa[x];
        }
        (ret,tree.(id[x],,n,));
         ret;
    }

    {
         l=(x,y);
         ((x,l,tree)+(y,l,tree)-tree.(id[l],,n,)+tt)%tt;
    }

    {
        tree.(id[x],id[x]+size[x],,n,,delta);
    }

    {
         tree.(id[x],id[x]+size[x],,n,);
    }
}

SegmentTree tree;

{
    n=(),m=(),root=(),tt=();
     ( i=;i<=n;i++) v[i]=();
     ( i=;i<n;i++){
         x=(),y=();
        (x,y);(y,x);
    }

    deep[root]=;
    HLD::(root);
    HLD::(root);

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

     (m--){
         opt=(),x,y,z;
        (opt){
             :
                x=(),y=(),z=()%tt;
                HLD::(x,y,z,tree);
                ;
             :
                x=(),y=();
                (,HLD::(x,y,tree));
                ;
             :
                x=(),z=()%tt;
                HLD::(x,z,tree);
                ;
             :
                x=();
                (,HLD::(x,tree));
                ;
        }
    }

     ;
}