树上算法 • CoderXL's Blog

树上算法非常多，但此处只介绍课内涉及过的。

最近公共祖先（Lowest Common Ancestor, LCA）#

性质#

在有根树上，任意两个节点 $u,v$ 都具有公共的祖先，而这些公共祖先中最低的那个被称为最近公共祖先，记作 $LCA(u,v)$ . 最近公共祖先具有一些重要的性质：

$LCA(u,v) = LCA(v,u)$ .
从 $u$ 到 $v$ 的路径必然经过 $LCA(u,v)$ .
如果 $LCA(u,v) = v$ ，则 $v$ 是 $u$ 的祖先。
「从根到 $u$ 的路径」和「从根到 $v$ 的路径」的公共部分是「从根到 $LCA(u,v)$ 的路径」。

在处理有关树上两点之间路径的问题时，借助 LCA 的以上性质通常能大幅降低复杂度。

比如询问树上任意两点 $u,v$ 之间的距离 $\mathrm{dis}(u,v)$ ，朴素做法可以通过树上遍历，对每次查询都 $O(n)$ 地算出结果；但使用 LCA，可以先统计每个点 $i$ 到根的距离 $\mathrm{dep}(i)$ ，然后根据性质 4.，得到 $\mathrm{dis}(u,v) = \mathrm{dep}(u)+\mathrm{dep}(v)-2\mathrm{dep}(LCA(u,v))$ . 这样，只需要先预处理 $\mathrm{dep}$ 和 $LCA$ ，之后每次查询的复杂度就变成了求 $LCA$ 的复杂度。

算法#

朴素#

借助 PPT 上的代码理解一下：

C++
Python

int lca_naive(int u, int v)
{
    // 先将深度对齐
    while(node[u].depth > node[v].depth)
    {
        u = node[u].parent;
    }
    while(node[v].depth > node[u].depth)
    {
        v = node[v].parent;
    }
    // 同时向上移动直到相遇
    while(u != v)
    {
        u = node[u].parent;
        v = node[v].parent;
    }
    return u;
}

cpp

def lca_naive(u, v):
    # 先将深度对齐
    while u.depth > v.depth:
        u = u.parent
    while v.depth > u.depth: 
        v = v.parent
    
    # 同时向上移动直到相遇
    while u != v:
        u = u.parent
        v = v.parent
    
    return u

python

flowchart TD

1((1)) --- 2((2)) --- 4((4)) --- 6((6))
4 --- 7((7)) --- 9((9))
1 --- 3((3)) --- 5((5)) --- 8((8))

倍增优化#

刚刚的朴素方法是在寻找祖先时，让 $u,v$ 同时一步一步向上跳，直到两者相遇，也即重合。但实际上这个过程是具有单调性的：随着跳的步数增加，一定是从不重合到重合，而不会反过来。

既然有单调性，我们就可以尝试用倍增优化它。

在这里，向上的跳跃步数是可以合并的，比如跳 $13 = (1101)_2$ 步，等价于跳三次，每次 $8+4+1$ 步。而如果我们先预处理出跳 $2^k$ 的结果，那么跳 $n$ 步的复杂度就可以从 $O(n)$ 减小到 $O(\log n)$ .

具体到 LCA 的倍增做法，我们先预处理 fa[k][u]，表示结点 u 向上走 $2^k$ 步到达的祖先。查询 lca(u, v) 时分两步：

先把较深的点跳到和另一个点同一深度：从大到小枚举 k，如果 u 的 $2^k$ 级祖先还不比 v 浅，就把 u 向上跳这一段。
再同时向上跳：从大到小枚举 k，只要 fa[k][u] != fa[k][v]，就让 u，v 一起跳到各自的 $2^k$ 级祖先。这样结束后，u 和 v 已经分别停在 LCA 的两个儿子上，此时它们的父亲就是 lca(u, v).

int lca(int u,int v)
{
    if(dep[u]<dep[v])
        swap(u,v);
    for(int i=lgN-1;i>=0;i--)
        if(dep[f[i][u]]>=dep[v])
            u=f[i][u];
    if(u==v)
        return u;
    for(int i=lgN-1;i>=0;i--)
    {
        if(f[i][u]==f[i][v])
            continue;
        u=f[i][u];
        v=f[i][v];
    }
    return f[0][u];
}

cpp