最近来复习一遍图论的板子——LCA。

概念

最近公共祖先（英语：lowest common ancestor）是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。在这里，我们定义一个节点也是其自己的后代，因此如果v是w的后代，那么w就是v和w的最近公共祖先。(fron wiki)

算法设计

我们先来看看应该怎么解决此类问题。

一般思路

在一个树上，我们定义离根节点最远的与a,b相同的祖先为最近公共祖先(LCA)。我们需要怎么做呢，首先肯定是 dfs 跑一遍，把所有的点的层次遍历出来，时间复杂度为 $O(N)$。一般情况下 $LCA$ 问题会有多次询问，询问次数一般为 $q<10^5$ ，那么就意味着我们不能在线性时间内去计算 $LCA$，如果采取最朴素的方法：选定2个点，若深度不一样则先转为深度一样，深度较深的点不停求它的父亲节点直到深度一样，然后用如下代码去求解。

1
2
3
4
5
6
7
int LCA(int a,int b){
    while(a!=b){
        a=pre[a];
        b=pre[b];
    }
    return a;
}

这样当然可以，而且非常符合最近公共祖先的定义，只是只需要稍微构造一下数据就可以 $T$ 到飞起。

正确思路

有一点不难发现：如果我和你有一个公共祖先，则公共祖先的祖先一定也是我们的公共祖先。比如亲兄弟之间，它们的公共祖先就是它们的父母（这里我们假设父母是一个人，爷爷奶奶姥姥姥爷等也是一个人），父母的祖先也就是爷爷奶奶它们同样也是这亲兄弟的公共祖先。再有一个，如果我们两个人的父亲不相同，则我们的公共祖先也等于我们父亲之间的公共祖先，这个都是能直接得到的结论。那么它在一定意义上是有序的，我们就可以采用倍增+二分的思路。

假设 $fa[a][k]$ 为差 $a$ 点 $2^k$ 辈的祖先，$fa[a][0]$ 就表示 $a$ 的父亲。在搜索的时候我们先观察节点所在的深度然后取得离他们最远的公共祖先。也就是 $fa[a][log_2deep[a]]$

但是你可能会发现，如果深度为7，那么它最多只能往上找 $4$ 个祖先，而如果公共祖先刚好是根节点，那么怎么办呢？那么我们不选择缩小区间，而是把 $a,b$ 当成新的对象来算公共祖先。那你有会发现，如果再往上找4个，那么会没有这个值，那怎么办呢？其实我们不需要它有，我们只需要它相等即可。因为根节点一定是所有节点之间的公共祖先，所以我们直接就这么找，找到相等区间往里面缩小一半，就往上找2个祖先，这时候可以发现刚好在根节点之前，如果它们的最近公共祖先是根节点，那么同理，这次寻找又会往上再找两个祖先。又跑到了根节点之外，判断相等，区间缩小为1。区间缩小为1的时候退出循环，此时我们要找的最近公共祖先就在当前点的父亲节点。

不知道这是否能解决你在运用倍增法求 $LCA$ 的疑惑。

可以看到每次以树的高度为范围，区间缩小一半地求，效率是非常高的。求一次 $LCA$ 的时间复杂度仅仅为 $log_2n$。

题目练手

洛谷P3379

标版，直接打就完事了。这里需要注意一下，如果深度不一样那么先平衡深度这个操作，这个操作我们并不是也要一个一个平衡的，也可以用倍增的思路。我先算出两深度之差，把差拆分为二进制比特位，如果从第往高第 $i$ 位为 $1$，那么我就往前寻找 $2^i$ 个祖先，而从当前点往前寻找 $2^i$ 个祖先我们可以直接用 $fa[now][i]$ 来快速求得。如果它构造特殊数据，那么直接一位一位往前寻找平衡深度可能会导致超时。

标程

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
#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
struct eee{
    int to;
    int next;
}edge[maxn<<1];
int root[maxn],cnt,lg[maxn],n,q,s;
int fa[maxn][25],depth[maxn];
void add(int x,int y){
    edge[++cnt].to=y;
    edge[cnt].next=root[x];
    root[x]=cnt;
}
void dfs(int now,int p){
    fa[now][0]=p;
    depth[now]=depth[p]+1;
    //printf("point=%d deep=%d\n",now,depth[now]);
    for(int i=1;i<=lg[depth[now]];i++){
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    for(int i=root[now];i;i=edge[i].next){
        int to=edge[i].to;
        if(to!=p)
            dfs(to,now);
    }
}
int LCA(int a,int b){
    if(depth[a]>depth[b]){
        swap(a,b);
    }
    int x=depth[b]-depth[a];
    int k=0;
    //printf("a=%d,b=%d\n",a,b);
    while(x){
        if(x&1){
            b=fa[b][k];
        }
        k++;
        x>>=1;
    }
    //printf("deep=%d\n",depth[b]);
    k=lg[depth[a]];
    printf("a=%d,b=%d\n",a,b);
    while(k!=-1){
        printf("k=%d\n",k);
        printf("a=%d,b=%d\n",fa[a][k],fa[b][k]);
        if(fa[a][k]==fa[b][k])k--;
        else{
            a=fa[a][k];
            b=fa[b][k];
            //k=lg[depth[a]];
        }
        
    }
    
    if(a==b)return a;
    else return fa[a][0];
}
int main(){
    freopen("1.in","r",stdin);
    ios::sync_with_stdio(false);
    cin>>n>>q>>s;
    lg[1]=0;
    for(int i=2;i<=n;i++){
        if(i>>(lg[i-1]+1))lg[i]=lg[i-1]+1;
        else lg[i]=lg[i-1];
    }
    for(int i=1;i<n;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }
    depth[s]=0;
    dfs(s,s);
    while(q--){
        int a,b;
        cin>>a>>b;
        printf("%d\n",LCA(a,b));
    }
    return 0;
}