LCA 求法的整理

发表于 | 阅读次数：
本文字数： 36k | 阅读时长 ≈ 33 分钟

关于 LCA 这东西太平常了 …… 这里就给出几种做法！！

倍增

我相信各位 dalao 学 LCA 的时候必定第一个学的就是倍增。

倍增其实就是将暴力向上跳的过程改为跳 $2$ 的次幂。

这东西也没啥好说的，大概流程就是大力 DFS 一遍，把 $2$ 的次幂的父亲都给处理出来，然后在线搞 LCA。

LCA 里面就是将两个节点先提到同一个深度，然后不停地向上跳，最终会跳到 LCA 的儿子。

至于为什么正确么 …… LCA 必定只有一个父亲，所有在 LCA 上面的全都是同一个父亲。

所以这样就直接判跳上去的是否是同一个父亲就可以了。

总时间复杂度 $O((n+q) \log n)$。

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
#include <iostream>
#include <cstdio>
using namespace std;
const int INF=5e5+5;
int n,m,s,head[INF],tot,lg[INF],fa[INF][35],dep[INF];
struct _node_edge {
        int to_,next_;
} edge[INF<<1];
void add_edge(int x,int y) {
        edge[++tot]=(_node_edge){y,head[x]};
        head[x]=tot; return;
}
void DFS(int x,int fa1) {
        fa[x][0]=fa1; dep[x]=dep[fa1]+1;
        for (int i=1; i<=lg[dep[x]]; i++)
                fa[x][i]=fa[fa[x][i-1]][i-1];
        // 2^i = 2^(i-1)+2^(i-1) = 2^(i-1)*2 = 2^i
        for (int i=head[x]; i; i=edge[i].next_) {
                if (edge[i].to_==fa1) continue;
                DFS(edge[i].to_,x);
        }
        return;
}
int LCA(int x,int y) {
        if (dep[x]<dep[y]) x^=y^=x^=y;
        while (dep[x]!=dep[y])
                x=fa[x][lg[dep[x]-dep[y]]];
        // cout<<x<<"\n";
        if (x==y) return x;
        for (int i=lg[dep[x]]; i>=0; i--) {
                if (fa[x][i]==fa[y][i]) continue;
                x=fa[x][i]; y=fa[y][i];
        }
        return fa[x][0];
}
signed main()
{
        scanf("%d %d %d",&n,&m,&s);
        for (int i=1; i<n; i++) {
                int x=0,y=0;
                scanf("%d %d",&x,&y);
                add_edge(x,y); add_edge(y,x);
        }
        lg[0]=-1;
        for (int i=1; i<=n; i++) lg[i]=lg[i>>1]+1;
        //2^lg[i]<=i 2^lg[3]<=3 2^(lg[1]+1)<=3
        // lg[1]=0 2<=3
        dep[0]=-1;
        DFS(s,0);
        for (int i=1; i<=m; i++) {
                int x=0,y=0; scanf("%d %d",&x,&y);
                cout<<LCA(x,y)<<"\n";
        }
        return 0;
}

树剖

树剖这个东西其实没啥好说的，实际跟倍增差不多，就是把 $2$ 的次幂改成链顶端。

虽然说也是 $((n+q) \log n)$，但它能维护树上的链和子树信息 然而要多个 $\log n$。

还有一个优势就是常数比较小。

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
#include <iostream>
#include <cstdio>
using namespace std;
const int INF=5e5+5;
int n,m,fa1[INF],dep[INF],sz[INF],son1[INF],head[INF],tot;
int top1[INF];
struct _node_edge {
        int to_,next_;
} edge[INF<<1];
void add_edge(int x,int y) {
        edge[++tot]=(_node_edge){y,head[x]};
        head[x]=tot; return;
}
void DFS(int x,int fa) {
        fa1[x]=fa; dep[x]=dep[fa]+1;
        sz[x]=1; int Max=0,Max1=0;
        for (int i=head[x]; i; i=edge[i].next_) {
                if (edge[i].to_==fa) continue;
                DFS(edge[i].to_,x); sz[x]+=sz[edge[i].to_];
                if (Max<sz[edge[i].to_])
                        Max=sz[edge[i].to_],Max1=edge[i].to_;
        }
        son1[x]=Max1;
        return;
}
void DFS1(int x,int fa,int t) {
        top1[x]=t;
        if (!son1[x]) return;
        DFS1(son1[x],x,t);
        for (int i=head[x]; i; i=edge[i].next_) {
                if (edge[i].to_==fa) continue;
                if (edge[i].to_==son1[x]) continue;
                DFS1(edge[i].to_,x,edge[i].to_);
        }
        return;
}
int LCA(int x,int y) {
        while (top1[x]!=top1[y]) {
                if (dep[top1[x]]<dep[top1[y]]) x^=y^=x^=y;
                x=fa1[top1[x]];
                // cout<<dep[4]<<" "<<dep[2]<<" "<<top1[x]<<" "<<top1[y]<<"\n";
        }
        if (dep[x]>dep[y]) return y;
        else return x;
}
signed main()
{
        int s=0;
        scanf("%d %d %d",&n,&m,&s);
        for (int i=1; i<n; i++) {
                int x=0,y=0; scanf("%d %d",&x,&y);
                add_edge(x,y); add_edge(y,x);
        }
        DFS(s,0); // 父亲，重儿子，深度
        DFS1(s,0,s); // 链顶端，权值，链
        for (int i=1; i<=m; i++) {
                int a=0,b=0;
                scanf("%d %d",&a,&b);
                int ab=LCA(a,b);
                cout<<ab<<"\n";
        }
        return 0;
}

st 表

st 表的优势在于可以 $O(1)$ 求 LCA，但它预处理的复杂度还是 $O(n \log n)$。

主要的就是对树进行一次遍历，记录 DFS 序，然后用新的编号表示，越小的也意味着深度越浅。

然后 ST 表求出两个节点最先进入的区间里面的最小值。就这样完事了。

至于为什么正确 …… (OI 里拿分就可以了，管什么正确性呀！！！)。

这个我也不太好证明，你就想，当前遍历到两个节点必然是要经过 LCA 的对吧，那肯定是不会到上面的，而 LCA 在这里必然是最小值。

所以显然酱紫是可以的，注意 DFS 序用两倍空间。

总时间复杂度 $O(n \log n + q)$。

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
#include <iostream>
#include <cstdio>
using namespace std;
const int INF=1e6+5;
int cnt,n,m,pre[INF],pos[INF],dfn[INF<<1],head[INF],tot,lg[INF<<1],f[INF<<1][55];
struct _node_edge {
        int to_,next_;
} edge[INF<<1];
void add_edge(int x,int y) {
        edge[++tot]=(_node_edge){y,head[x]};
        head[x]=tot; return;
}
void DFS(int x,int fa) {
        tot++;
        dfn[tot]=tot; pos[x]=tot;
        pre[tot]=x;
        for (int i=head[x]; i; i=edge[i].next_) {
                if (edge[i].to_==fa) continue;
                DFS(edge[i].to_,x);
                dfn[++tot]=pos[x];
                // cout<<tot<<" "<<x<<" "<<fa<<"\n";
                // if (4==x) cout<<edge[i].to_<<"\n";
        }
        return;
}
int LCA(int x,int y) {
        x=pos[x]; y=pos[y];
        if (x>y) x^=y^=x^=y;
        // cout<<x<<" "<<y<<"\n";
        int kk=lg[y-x+1];
        return min(f[x][kk],f[y-(1<<kk)+1][kk]);
}
signed main()
{
        int s=0;
        scanf("%d %d %d",&n,&m,&s);
        for (int i=1; i<n; i++) {
                int x=0,y=0; scanf("%d %d",&x,&y);
                add_edge(x,y); add_edge(y,x);
        }
        tot=0;
        DFS(s,0); lg[0]=-1;
        // cout<<tot<<"\n";
        // for (int i=1; i<=tot; i++) cout<<dfn[i]<<" ";
        for (int i=1; i<=tot; i++) lg[i]=lg[i>>1]+1;
        for (int i=1; i<=tot; i++) f[i][0]=dfn[i];
        for (int i=1; i<=31; i++) {
                int kk=(1<<i); if (kk>tot) break;
                for (int j=1; j+kk-1<=tot; j++) {
                        f[j][i]=min(f[j][i-1],f[j+(1<<(i-1))][i-1]);
                }
        }
        for (int i=1; i<=m; i++) {
                int a=0,b=0;
                scanf("%d %d",&a,&b);
                int ab=LCA(a,b);
                // cout<<ab<<"\n";
                cout<<pre[ab]<<"\n";
        }
        return 0;
}

tarjan

tarjan 是一种离线求 LCA 的方法，但实际能做到线性的复杂度！！！

就冲线性这一点，已经足够优秀了，(我讲的全是现在主流的，有一些极致优化我当然不会)。

大概流程就 DFS ，然后走到当前节点，如果说当前节点是要统计答案的，并且另一个也遍历好了。

举个例子 $(x,y)$ 假定当前已经遍历到了 $x$ 判断 $y$ 是否遍历过，如果是的，那么当前就直接找祖先，这可以用并查集来维护。

正确性就是当前遍历到的显然是最近的公共祖先，因为不会往上回溯，和 ST 表其实差不多。

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
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int INF=5e5+5;
int n,m,head[INF],tot;
struct _node_edge {
        int to_,next_;
} edge[INF<<1];
vector<int> v[INF],id[INF];
int fa_set[INF],vis[INF],ans[INF];
void add_edge(int x,int y) {
        edge[++tot]=(_node_edge){y,head[x]};
        head[x]=tot; return;
}
int find_set(int x) {
        return x==fa_set[x] ? x : fa_set[x]=find_set(fa_set[x]);
}
void tarjan(int x,int fa) {
        for (int i=head[x]; i; i=edge[i].next_) {
                if (edge[i].to_==fa) continue;
                tarjan(edge[i].to_,x);
                fa_set[edge[i].to_]=x;
        }
        vis[x]=1;
        int len=v[x].size();
        for (int i=0; i<len; i++) {
                if (vis[v[x][i]]==0) continue;
                ans[id[x][i]]=find_set(v[x][i]);
        }
        return;
}
signed main()
{
        int s=0;
        scanf("%d %d %d",&n,&m,&s);
        for (int i=1; i<n; i++) {
                int x=0,y=0; scanf("%d %d",&x,&y);
                add_edge(x,y); add_edge(y,x);
        }
        for (int i=1; i<=m; i++) {
                int x=0,y=0; scanf("%d %d",&x,&y);
                v[x].push_back(y);
                v[y].push_back(x);
                id[x].push_back(i);
                id[y].push_back(i);
        }
        for (int i=1; i<=n; i++)
                fa_set[i]=i;
        tarjan(s,0);
        for (int i=1; i<=m; i++)
                cout<<ans[i]<<"\n";
        return 0;
}

至此 LCA 的各种优化已经全部列出 (如果有遗漏的肯定是超过了 OI 的范畴，就基本不会用的)。

如果有问题还请指出！

-------- 本文结束 感谢阅读 --------