树链剖分入门

Jadebo1 · 2022-07-04 21:35:08 · 个人记录

树链剖分是把一棵树分成若干条链，以便于将树上问题转化为序列问题的一种方法。常用剖分方式有重链剖分、长链剖分、实链剖分等。本文介绍的为重链剖分。

想要学习重链剖分，首先要引入几个概念。

• 重儿子 ：为其父节点的所有子节点中子树最大的一个。如果出现若干个子节点子树大小均为最大，则从中任选一个作为重儿子。
• 轻儿子：除了重儿子以外的其他子节点。
• 重链：由一个轻儿子（包括根节点）出发，不断连接重儿子的一条链称为重链。
• 轻链：除了重链以外的所有树链。

由定义可知，若该树轻儿子的数量为 x ，则该树将会被划分成 x 条链。

按重链剖分后的树有一条性质需要注意：对于节点数为 x 的树，从根节点到任意节点，路径中所包含的轻边数量均不会超过 \log n 。

附简略证明：

若从父节点沿轻边向下至某节点,则说明兄弟节点中存在子树大于该节点的点，所以父节点的子树大小至少为该节点子树大小的两倍及以上。 每走过一次轻边，子树大小都会缩小至少一倍。

重链剖分的操作需要通过两次 dfs 实现，第一次 dfs 我们需要得到的信息有 f （父节点）、 dep （深度）、 sz （子树大小）、 son （重儿子节点编号）。

void dfs1(int now, int fa)
{
    dep[now] = dep[fa] + 1;//子节点深度为父节点深度+1
    f[now] = fa;
    sz[now] = 1;//子树包含自己
    int mx = -1;
    for (auto x : e[now])
    {
        if (x == fa)
            continue;
        dfs1(x, now);
        sz[now] += sz[x];
        if (sz[x] > mx)//获取当前节点重儿子的编号
        {
            mx = sz[x];
            son[now] = x;
        }
    }
}

第二次 dfs 我们需要正式将树转化为链，将树上问题转化为序列问题解决。这一次我们需要知道当前节点 id（编号）、 top （所在重链中，深度最小的节点编号）。在大部分问题当中，我们还需要将 b （点权）按照编号重新赋值，以便在后续中可以使用线段树、树状数组等数据结构进行信息维护。

void dfs2(int now,int tt)
{
    id[now]=++tot;//按照dfs序给各节点重新赋值
    a[tot]=b[now];
    top[now]=tt;
    if(!son[now])
    return;
    dfs2(son[now],tt);//重儿子的链头依然为其父节点的链头（重链）
    for(auto x :e[now])
    {
        if(x==f[now]||x==son[now])
        continue;
        dfs2(x,x);//轻儿子的链头为自己（轻链）
    }
}

此时该树已经被彻底划分为链，可以更便捷地进行信息统计了。

下面看一道树链剖分的例题

https://www.luogu.com.cn/problem/P3384

题目描述

如题，已知一棵包含 N 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作：

• 1 x y z，表示将树从 x 到 y 结点最短路径上所有节点的值都加上 z。

• 2 x y，表示求树从 x 到 y 结点最短路径上所有节点的值之和。

• 3 x z，表示将以 x 为根节点的子树内所有节点值都加上 z。

• 4 x 表示求以 x 为根节点的子树内所有节点值之和

既然我们已经通过树链剖分得到原树各节点的 dfs 序，易得 3 、 4 操作只需要利用数据结构在 id[x] 到 id[x]+sz[x]-1 这个区间里分别进行区间加法以及区间求和功能。

那么我们如何实现 1 、2 操作呢？

由于我们将树已经剖分成一条条的树链，因此我们可以以 o(1) 的复杂度在树链上进行跳转，链与链之间由轻边连接，因此所经过的轻边数目不超过 \log n ，再配合上数据结构，我们可以实现 o(\log^2 n) 的区间修改和区间查询。

//区间修改
void modify(int x,int y,ll k)
{
    while(top[x]!=top[y])//若两节点不再同一条树链上
    {
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);
        seg.add(1,1,n,id[top[x]],id[x],k);//先处理链头较深的一部分
        x=f[top[x]];//爬升至链头
    }
    if(dep[x]>dep[y])
    swap(x,y);
    seg.add(1,1,n,id[x],id[y],k);//处理同一条树链上的区间
}
//区间查询
ll qRange(int x,int y)
{
    ll res=0;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])
        swap(x,y);
        res+=seg.query(1,1,n,id[top[x]],id[x]);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])
    swap(x,y);
    res+=seg.query(1,1,n,id[x],id[y]);
    return res;
}

这样我们就可以轻松A掉这道题了。

当然我们除了维护点权以外还可以维护边权，具体做法为将边权赋值为深度较深点的点权即可，感兴趣可以自己尝试。非常之恶心