LCA

对于一棵树 (可以是多叉树), 根为R

祖先
对于任意一个点x, 该点到R的 简单路径 (也就是从x一直往上走到R的路径)上的所有点
均是x的 祖先. (x也是自己的祖先!)

在x上面的 (即深度小于x的), 不一定就是x的祖先. 还必须在x与R的 简单路径上

令Depth[ R] = 0, 则x的祖先个数为: Depth[ x] + 1个

简单路径 (正式定义是: 路径上没有重复点)
在树上的简单路径, 比如对于ab两点间的简单路径

• ab简单路径一定是惟一的, 这由于树的特殊结构决定
• 令x = depth[ a], y = depth[ b], 则简单路径[a, ..., b]其对应的depth 有3种可能情况
  1, x, x+1, x+2, ..., y-1, y, 表示, a点一直往下走到b, 路径长度为y - x
  2, x, x-1, x-2, ..., y-1, y, 表示a点一直往上走到b, 路径长度为x - y
  3, x, x+1, x+2, ..., h+1, h, h-1, ..., y-1, y 表示, a先一直往上走到一个点c, 然后从c再一直往下走到b
  路径长度为(x-h) + (y-h)
  不存在: (先往下走, 再往上走)的情况!
  c点, 就是ab的 (LCA), 下面会讲到.

公共祖先
S点集为: 既是a的祖先, 也是b的祖先
则, S点集为 ab的公共祖先.

最低公共祖先算法实现

zip 0星 超过10%的资源 5KB

下载

S点集中, 所有点的深度均不同. 其实这个点集, 就是 (aR简单路径) 与 (bR简单路径) 的 交集.

最近公共祖先 LCA: least common ancestor
ab的LCA为: S点集(即公共祖先中), 深度最大的点, 他是唯一的

算法

倍增

求LCA( a, b), 假设depth[ a] >= depth[ b]

• 第一步, 将a往上走, 移动到和b同一层(同一深度) 点, 记为aa
  对于d = depth[ a] - depth[ b], 要走b步, 根据倍增原理, b = [0, 1, ..., N], 平均下来, 最少是O( logN)次. 即, 二进制拆分.
  因此, 我们需要一个Fa[ x][ k]数组, 表示: x点, 往上走$2^k$步后的祖先
  预处理这个数组是N * logN, 即dfs整个树
• 第二步, 此时aa 与 b是在同一层, 让他俩同时往上走, 走到LCA的儿子
  为什么不走到LCA呢? 而是走到他的儿子呢?
  假如Fa[ aa][ 0, 1, 2, ...]为: a0, a1, a2, a3, ...
  … … Fa[ b][ 0, 1, 2, ...]为: b0, b1, b2, b3, ...
  我们看他的bool( ai == bi)这个布尔数组, 记作c: c0, c1, c2, c3, ...
  假如, a2是LCA, 即: a2 == b2 == LCA, 则布尔数组为: 0, 0, 1, 1, 1, 1, ... 则, LCA为: 布尔数组中 最左侧的1
  但是, LCA可能是 介于a1 和 a2之间的, 此时其布尔数组为: 0, 0, 1, 1, 1...
  选择最左侧的1,即a2 == b2, 他确实是公共祖先, 但他不是最近公共祖先!!
  如果是 二分 , 你跳到a2, 还能往回跳 (即往下跳), 但这里是 倍增 , 只能单向往前走, 不能往回走!
  因此, 如果ci为真 (aa 与 b的公共祖先),就跳过去,这是不对的
  应该是: 跳到 最左侧的1的左侧0位置 , 即: aa 到 a1点, b 到 b1点 (当然a1 != b1)
  这样, 再以a1 b1继续跳, 仍然是跳到 最左侧的1的左侧0位置 , 最终, a b会跳到: LCA的两个儿子上 (LCA有>=2个儿子, 多叉树, 但a b在其中的两个上)

算法注意点

• 对于数, 我们知道, 树根Root是可以任意的! 即选择[1, ..., N]哪个点当做树根, 其仍然是一个树!
  这可以想象成: 只有树根有一个钉子, 定在那. 其他所有点都下垂
  但是, 不同的树根, ab两点的LCA可能是不同的!
  比如, 选择a作为树根, 自然LCA( a, b) = a; 选择b作为树根, 自然LCA( a, b) = b
  因此, 只有树根确定了, LCA才能确定.
  … 但是, 涉及到LCA的问题, 不一定题目会给出固定的树根! 比如, 树上前缀和/差分, 都会涉及到LCA
  … 但是, 树根选择哪个都是正确的, 都可以正确的求出前缀和/差分, 只要找到LCA即可, 不管是在哪个树根下.

• 让Depth[ Root] = 0, 这样做的好处是: 对于一点x, x 与 Root的简单路径上 正好有 Depth[ x]条边.
  也就是, x点, 往上跳Depth[ x]步, 就是Root

• 设置一个int Log[ N]数组, Log[ a] = b满足: 2^b <= a, 且b最大
  这样, 每次求lca( a, b)时, 往上跳时, 不需要从 Log( N) 从而产生一堆非法值
  而直接从Log( Depth[ a])开始.
  … 而且, 还有个好处是: 当constexpr int N_ = xx;点数改变了, 只需修改下: Fa[ N_ ][ 21]中的21这个数值
  … 其他代码不用改, 因为代码里用的都是Log, 而Log会根据N_的大小来进行循环
  … Log的大小是: int Log[ N_];, 也不用动.

• Log[ 0]是未定义的, Fa[ Root][ >= 0]都是未定义的, 也都是非法值.
  要避开这些.

代码

题目链接

LITERAL_ int N_ = int( 5e5) + 5;
int N, M, Root; //< (点数) (查询数) (根)
int Head[ N_], Ver[ N_ * 2], Nex[ N_ * 2], Edges;
int Log[ N_]; //< Log[ a] = b;  2^b <= a, 最大的b
int Depth[ N_], Fa[ N_][ 21];
//--
void Build_graph(){
    Edges = 0;
    memset( Head, -1, sizeof( Head));
}
void Add_edge( PAR_( int, _a), PAR_( int , _b)){
    Ver[ Edges] = _b;
    Nex[ Edges] = Head[ _a];
    Head[ _a] = Edges;
    ++ Edges;
}
void Dfs_lca( PAR_( int, _cur), PAR_( int, _fa)){
    for( int nex, i = Head[ _cur]; ~i; i = Nex[ i]){
        nex = Ver[ i];
        if( nex != _fa){
            Depth[ nex] = Depth[ _cur] + 1;
            //--
            Fa[ nex][ 0] = _cur;
            FOR_( step, 1, Log[ Depth[ nex]], 1){
                Fa[ nex][ step] = Fa[ Fa[ nex][ step - 1]][ step - 1];
//                DEBUG_( nex, step, Fa[ nex][ step]); //< 在`Build_lca()`完后, 最好调试测试下
            }
            //--
            Dfs_lca( nex, _cur);
        }
    }
}
void Build_lca(){
    { //* build `Log`
        FOR_( i, 1, N, 1){
            if( 1 == i){
                Log[ 1] = 0;
            }
            else{
                if( ( 1 << ( Log[ i - 1] + 1)) == i){
                    Log[ i] = Log[ i - 1] + 1;
                }
                else{
                    Log[ i] = Log[ i - 1];
                }
            }
        }
    }
    //--
    Depth[ Root] = 0;
    Dfs_lca( Root, -1);
}
int Lca( PAR_( int, _a), PAR_( int, _b)){
    int low = _a, hig = _b;
    if( Depth[ low] < Depth[ hig]){
        swap( low, hig);
    }
    while( Depth[ low] != Depth[ hig]){
        low = Fa[ low][ Log[ Depth[ low] - Depth[ hig]]];
    }
    if( low == hig){ //< 如果不判断, 假如low=Root, 则下面代码中的Log[ 0]是个未定义行为
        return low;
    }
    FOR_RE_( i, Log[ Depth[ low]], 0, 1){ //< 不是 `Log[ low]`!
        if( Fa[ low][ i] != Fa[ hig][ i]){
            low = Fa[ low][ i];
            hig = Fa[ hig][ i];
        }
    }
    assert( Fa[ low][ 0] == Fa[ hig][ 0]);
    return Fa[ low][ 0];
}
void __Solve(){
    Build_graph();
    scanf("%d%d%d", &N, &M, &Root);
    FOR_( i, 1, N-1, 1){
        int a, b;
        scanf("%d%d", &a, &b);
        Add_edge( a, b);
        Add_edge( b, a);
    }
    Build_lca();
    FOR_( i, 1, M, 1){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", Lca( a, b));
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88