前置

树

别说你不知道什么是树。。。不知道就去睡觉吧。

教你百度？

DFN 序

记录 \(dfs\) 的时候每个点访问起始时间与结束时间，记录起始时间是前序遍历，结束时间是后序遍历。
可以轻易地发现树的一棵子树在 \(dfs\) 序上是连续的一段。
\(dfn\) 序是节点按照 \(dfs\) 进入节点的顺序排列的序列。
一般 \(dfn\) 序可以认为是 \(dfs\) 序的一半、是 \(dfs\) 序的子序列。

一些可能用到的概念

重儿子
- 在所有的节点中拥有子树节点最多的一个父节点
- 是个节点
轻儿子
- 除去重儿子其它所有的父节点
- 也是个节点
重边
- 父节点和重儿子连成的边
- 是一条边
轻边
- 父节点和轻儿子连成的边
- 也是一条边
重链
- 由多条重边连接而成的路径
轻边
- 有多条轻边链接而成的路径

对于上图：

1 号节点的子结点中，4 号节点的子树节点比 2、3 号的多，所以 4号节点是重儿子；

4 号节点的子节点中，9 号节点的子树节点比 8、10 号的多，所以 9号节点是重儿子；

以此类推。

那么：

图中加粗的节点都是重儿子，其它节点都是轻儿子；

红色边都是重边，黑色边都是轻边；

\(1 \to 4 \to 9 \to 12 \to 14\) 、 \(3 \to 7\) 和 \(2 \to 6 \to 11\) 是重链。

来张更详细具体的图片：

图片来自 ChinHhh's blog

定义

百度者云：

一种对树进行划分的算法，它先通过轻重边剖分将树分为多条链，保证每个点属于且只属于一条链，然后再通过数据结构（树状数组、BST、SPLAY、线段树等）来维护每一条链。

简单来说就是对树进行轻重边剖分，分割成多条链，然后通过某些数据结构进行维护。

其实本质上来说还是一种优化暴力。

~~算法的本质不就是加速枚举么~~

by attack

功能实现

对于上述两张图片的分析，可以发现一个规律：

叶节点没有重儿子，非叶节点有且只有一个重儿子，并不是轻儿子之后全是轻儿子。

或者换句话说：

当一个节点选了他的重儿子之后，我们并不能保证它的轻儿子就是叶节点，所以我们就以这个轻儿子为根，再去选这个轻儿子的轻重儿子。

其实这就是一个 \(dfs\) 过程，而且通过上述操作，我们可以得到许多重链。

变量声明

int n, m;

const int _ = 100010;

struct edge
{
    int to;
    int nxt;
} e[2 * _];
int cnt, head[_];

struct Node
{
    int sum;
    int lazy;
    int l;
    int r;
    int ls;
    int rs;
} node[2 * _];

int fa[_], dep[_], siz[_], mson[_], rk[_], top[_], id[_];

名称	含义
fa[u]	节点 u 的父亲节点
dep[u]	节点 u 的深度
siz[u]	以节点 u 为根的子树节点数目
mson[u]	max_weight_son 重儿子
rk[u]	当前 dfs 标号在树中所对应的节点
top[u]	当前节点所在链的顶端节点
id[i]	节点 i 在树链剖分后的新编号（ dfs 序）

实现思路

通过两次 \(dfs\) 实现。

dfs1()

对于某个节点：

求出它所在的子树大小
找到该子树的重儿子

（处理出 siz 和 mson 数组）

记录其父亲以及深度

（处理出 f ， d 数组）

/*

代码来自网络。

*/
void dfs1(int u, int fa, int depth) //当前节点、父节点、层次深度
{
    fa[u] = fa_;
    d[u] = depth;
    siz[u] = 1; //对于这个点本身来说siz=1
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v == fa)
            continue;
        dfs1(v, u, depth + 1); //层次深度+1
        siz[u] += siz[v];    //子节点的siz已被处理，用它来更新父节点的siz
        if (siz[v] > siz[mson[u]])
            mson[u] = v; //选取siz最大的作为重儿子
    }
}
//进入
dfs1(root, 0, 1);

图片来自 Ivanovcraft's blog

dfs2()

链接重链
标记每个节点的 \(dfs\) 序
用数据结构维护重链，保证每一条重链上各个节点 \(dfs\) 序上是连续的一段

（处理出 top 、 id 、rk 数组）

/*

代码来自网络。

*/
void dfs2(int u, int t) //当前节点、重链顶端
{
    top[u] = t;
    id[u] = ++cnt; //标记dfs序
    rk[cnt] = u;   //序号cnt对应节点u
    if (!mson[u])
        return;
    dfs2(mson[u], t);
    /*我们选择优先进入重儿子来保证一条重链上各个节点dfs序连续，
一个点和它的重儿子处于同一条重链，所以重儿子所在重链的顶端还是t*/
    for (int i = head[u]; i; i = e[i].nxt)
    {
        int v = e[i].to;
        if (v != mson[u] && v != fa[u])
            dfs2(v, v); //一个点位于轻链底端，那么它的top必然是它本身
    }
}

图片来自 Ivanovcraft's blog

时间复杂度

如果 \((u, v)\) 是一条轻边，那么 \(siz(v) < siz(u)/2\)
从根结点到任意结点的路所经过的轻重链的个数必定都小于 \(\log n\)

总体时间复杂度为：

\(\huge O(n \log ^ 2 n)\)

『笔记』树链剖分

前置

树