树链剖分

目录
  1. 1. 算法简介
  2. 2. 算法原理
  3. 3. 算法实现
  4. 4. Hint

算法简介

树链剖分是将树上的节点映射到一段连续的区间中，使得树上任意一条路径能用不
超过 $O(\log N)~$ 段连续区间表示。这样就可以对树上的路径做一些操作了。
常见的搭配是 线段树+树链剖分。

算法原理

  • $siz(u)$ $\hskip 1.3em$ 以 $u$ 为根的子树的节点数
  • $son(u)$ $\hskip 0.9em$ $u$ 的子节点中 $siz$ 值最大的节点
  • 重边 $\hskip 1.2em$ $u$ 与 $son(u)$ 的连边
  • 轻边 $\hskip 1.2em$ $u$ 与除 $son(u)$ 外其它子节点的连边
  • 重链 $\hskip 1.2em$ 由重边连成的路径

【定理1】 如果 $(u,v)$ 是一条轻边，那么 $siz(v) < \frac{siz(u)}{2}$。
$\quad$【证】
$\hskip 3em$ 因为 $(u,v)$ 是一条轻边，所以 $u$ 还有一个由重边相连的儿子 $son(u)$；
$\hskip 3em$ 若 $siz(v) \geqslant \frac{siz(u)}{2}$；
$\hskip 3em$ 根据定义，有 $siz \big( son(u) \big) \geqslant siz(v) \geqslant \frac{siz(u)}{2}$。
$\hskip 3em$ 而，$siz(u) \geqslant siz(v)+siz \big( son(u) \big) +1 > siz(u)$，矛盾。
$\hskip 3em$ 故，$siz(v) < \frac{siz(u)}{2}$。
$\quad$【证毕】

【定理2】 任意非根节点 $u$ 到根节点的路径上，轻边+重链 总数不超过 $O(\log_2 N)$。
$\quad$【证】
$\hskip 3em$ 不难证明，最多会遇到 $\log_2 N$ 条轻边；
$\hskip 3em$ 因为，从根节点到 $u$ 的路径中，每遇到一条轻边，节点个数就会减半；
$\hskip 3em$ 所以轻边的数目不超过 $\log_2 N$。
$\hskip 3em$ 而，整条路径上 $\log_2 N$ 条轻边最多隔开 $\log_2 N +1$ 条重链；
$\hskip 3em$ 故，轻边+重链 总数不超过 $O(\log_2 N)$。
$\quad$【证毕】

当我们将一棵树沿着重链剖分后，将重链依次映射到一段连续的区间后，
就可以将任何一条到根的链分成 $\log N$ 段连续区间了。
也就是用 $\log N$ 条重链的覆盖这一条路径。

算法实现

  • $fat(u)$ $\hskip 1.15em$ $u$ 的父亲
  • $son(u)$ $\hskip 0.95em$ $u$ 的子节点中 $siz$ 值最大的节点
  • $dep(u)$ $\hskip .9em$ $u$ 的深度，根节点深度为 1
  • $siz(u)$ $\hskip 1.3em$ 以 $u$ 为根的子树的节点数
  • $pos(u)$ $\hskip 1em$ $u$ 在连续区间的映射值
  • $top(u)$ $\hskip 1.05em$ $u$ 所在重链的顶端节点

求出 $siz,dep,son,fat$

1
2
3
4
5
6
7
8
9
10
11
12
13
int fat[MAXN], son[MAXN], dep[MAXN], siz[MAXN];
void DFS(int o, int f, int d) {
    fat[o] = f; son[o] = 0;
    dep[o] = d; siz[o] = 1;
    for(int u=from[o]; u; u=nxt[u]) {
        int v = to[u];
        if( v == f ) continue;
        DFS(v, o, d+1);
        siz[o] += siz[v];
        if( siz[son[o]] < siz[v] ) son[o] = v;
    }
}

求出 $top, pos$，

1
2
3
4
5
6
7
8
9
10
11
int top[MAXN], pos[MAXN], dfs_colok;
void DFS(int u, int t) {
    pos[u] = ++dfs_clock;
    top[u] = t;
    if( !son[u] ) return;
    DFS(son[u], t);      // u 与 son(u) 在同一条重链上，故重链的顶端节点相同
    for(int i=from[u]; i; i=nxt[i]) {
        int v = to[i];
        if( v != fat[u] && v != son[u] ) DFS(v, v); // u 的其它非 son(u) 子节点为新的重链的顶端节点
    }
}

树链剖分完了！！怎么用呢？
先看下图：

左图中的粗线表示重边，虚线表示轻边； 黑色数字为节点编号，紫色数字为边编号。 左图中的 `0` 节点为一虚拟节点，引进它是方便理解下文; **在实际实现中，我们令 $fat($ 根节点 $)=$ 根节点，则上图的 `0` 节点指代 `1`。** **每条边上的紫色数字表示箭头所指的节点的 $pos$ 值。**

对于树的两个节点 $u$，$v$，若它们的最近公共祖先（LCA）为 $w$；
那么，如果我们想要对路径 $(u,v)$ 上的所有节点进行一个操作，
只需要让 $u$,$v$ 同时沿着各自的祖先节点走，并在 $w$ 处相遇就可以了。

$top$ 是为了加速往上走的过程；但是不难发现，由于每次可能不仅走一步，
如果 $u$ 和 $v$ 同时行动的话，很可能会错过 $w$ ！
为了解决这个问题，可以总是让 $dep(top)$ 值大的点先走（想一想，为什么）。

$\hskip 1em$
$\hskip 1em$

不妨假设 $dep \big( top(u) \big) \geqslant dep \big( top(v) \big)$

  • $top(u) \neq top(v)$ $\hskip 1em$ 得到一段连续的映射区间 $\Big[pos \big( top(u) \big),pos(u)\Big]$；并让 $u$ 走到 $fat \big( top(u) \big)$
  • $top(u) = top(v) $ $\hskip 1em$ $u$ 和 $v$ 在同一条重链中，显然， $w=dep(u) < dep(v)?u: v$；得到一段连续的映射区间 $\Big[ pos(w),pos \big(w==u?v:u\big) \Big]$

由于每次走到 $fat(top)$，可以放心的把轻边当做 长度为0的重链 来处理。

比如，我们现在要访问 节点6 –> 节点15 的路径：

  1. $u$ 走到 12，得到一段连续的映射区间 $[7,7]$
  2. $u$ 走到 1，得到一段连续的映射区间 $[2,3]$
  3. $v$ 走到 2，得到一段连续的映射区间 $[12,12]$
  4. $v$ 走到 1，得到一段连续的映射区间 $[11,11]$
  5. $top(u) = top(v)$，得到一段连续的映射区间 $[1,1]$；相遇，终止算法

所以，我们在映射区间里依次对 $\big\lbrace [7,7],[2,3],[12,12],[11,11],[1,1] \big\rbrace$ 进行操作就好了。

1
2
3
4
5
6
7
8
9
10
11
12
void Update(int L, int R) {
    while (top[L] != top[R]) {
        if (dep[top[L]] < dep[top[R]]) swap(L, R);  // 让 dep 大的走
        
        int l = pos[top[L]], r = pos[L];  // 得到连续映射区间 [l,r]
        fun(l, r); // 对 [l,r] 进行操作

        L = fat[top[L]];
    }
    if (dep[L] > dep[R]) swap(L, R);
    fun(pos[L], pos[R])
}

Hint

上文中讨论的是对 $(u,v)$ 路径上的所有节点进行操作。
若信息全维护在边上，即要对 $(u,v)$ 路径上的所有边进行操作，
则仅需在 $dep(u) = dep(v)$ 时，执行的区间改成 $\Big[ pos \big( son(u) \big),pos(v) \Big]$ 就行了。

*** 参考链接 ***