Eternity

Until The End

树上最近公共祖先(LCA)

发表于 更新于 分类于 ，
本文字数： 5.3k 阅读时长 ≈ 5 分钟

“你与我最初的缔结”

定义

LCA（Least Common Ancestors）：即最近公共祖先，是指在有根树中，找出某两个结点 $u$ 和 $v$ 最近的公共祖先。

对于下图（取自洛谷）：

LCA

$lca(13,5)=3$

$lca(6,4)=4$

$lca(18,2)=2$

$lca(15,18)=5$

…

朴素思路

从一个点开始，向上标记至根节点；然后将另一点向上搜索到第一个标记的点，该点则是两点的 $lca$ 。这样的复杂度是 $O(nq)$ ，$q$ 表示询问次数。非常滴慢。

一般方法

倍增

树链剖分

裸裸的树剖，甚至不需要数据结构维护。

对于一组询问 $(x,y)$ 首先将两个点跳到同一条重链上，然后输出深度小的点即可。

AC Code 
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define db double
typedef long long ll;
using namespace std;
const int MAXN=5e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
template<class T>
inline bool checkMax(T &x,T &y)
{
    return x<y?x=y,1:0;
}
template<class T>
inline bool checkMin(T &x,T &y)
{
    return x>y?x=y,1:0;
}
int N,M,Root;
struct Graph
{
    int next,to;
    Graph(int n=0,int t=0):next(n),to(t){}
}Edge[MAXN<<1];
int Head[MAXN],Total;
inline void addEdge(int u,int v)
{
    Edge[++Total]=Graph(Head[u],v);Head[u]=Total;
    Edge[++Total]=Graph(Head[v],u);Head[v]=Total;
}
int Size[MAXN],Dep[MAXN],Top[MAXN],Fa[MAXN],Son[MAXN];
void dfsTree(int x,int last,int dep)
{
    Fa[x]=last,Size[x]=1,Dep[x]=dep;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        dfsTree(v,x,dep+1);
        Size[x]+=Size[v];
        if(!Son[x]||Size[Son[x]]<Size[v]) Son[x]=v;
    }
}
void dfsDfn(int x,int topf)
{
    Top[x]=topf;
    if(!Son[x]) return ;
    dfsDfn(Son[x],topf);
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        v=Edge[e].to;
        if(v==Fa[x]||v==Son[x]) continue;
        dfsDfn(v,v);
    }
}
inline int lca(int x,int y)
{
    while(Top[x]!=Top[y])
    {
        if(Dep[Top[x]]<Dep[Top[y]]) swap(x,y);
        x=Fa[Top[x]];
    }
    if(Dep[x]>Dep[y]) swap(x,y);
    return x;
}
int main()
{
    // freopen("tree-chain.in","r",stdin);
    // freopen("tree-chain.out","w",stdout);
    read(N,M,Root);
    for(int i=2,u,v;i<=N;++i)
    {
        read(u,v);
        addEdge(u,v);
    }
    dfsTree(Root,0,1);
    dfsDfn(Root,Root);
    for(int i=1,x,y;i<=M;++i)
    {
        read(x,y);
        printf("%d\n",lca(x,y));
    }
    return 0;
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
*/

Tarjan

st表

做到 $O(n \log n)$ 的预处理，$O(1)$ 的查询，算比较快的了。将整个树遍历，每遍历一个点将其加至序列末尾。记为数组 $id(x)$ 。无论是到达还是回溯都需要记录。可以证明该序列不会超过 $2n-1$ 。从 $x$ 到 $y$ 需要从 $lca$ 的一个子树走到另一个子树。则在区间 $[id(x),id(y)]$ 之间一定存在 $lca(x,y)$ 。

而 $lca(x,y)$ 就是其中深度最小的点。用 $st$ 表维护。

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
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<ctime>
#include<iomanip>
#include<queue>
#include<stack>
#include<map>
#include<vector>
#define gh() getchar()
#define re register
#define underMax(x,y) ((x)>(y)?(x):(y))
#define underMin(x,y) ((x)<(y)?(x):(y))
typedef long long ll;
using namespace std;
const int MAXN=5e5+1;
template<class T>
inline void underRead(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
int N,M,Idx,Rt;
struct edge
{
    int next,to;
}Edge[MAXN<<1];
int Head[MAXN],Total;
int Log[MAXN<<1],St[MAXN<<1][64],Dep[MAXN],Id[MAXN];
inline void underAddEdge(int u,int v)
{
    Edge[++Total]=(edge){Head[u],v};Head[u]=Total;
    Edge[++Total]=(edge){Head[v],u};Head[v]=Total;
}
inline void underSwap(int &x,int &y)
{
    x^=y^=x^=y;
}
inline void underDfs(int x,int last)
{
    St[++Idx][0]=x;Id[x]=Idx;Dep[x]=Dep[last]+1;
    for(int e=Head[x],v;e;e=Edge[e].next)
    {
        if((v=Edge[e].to)==last) continue;
        underDfs(v,x);
        St[++Idx][0]=x;
    }
}
inline int underDepMin(int a,int b)
{
    return Dep[a]<Dep[b]?a:b;
}
inline void underInit()
{
    for(int i=2;i<=Idx;++i) Log[i]=Log[i>>1]+1;
    for(int k=1;(1<<k)<=Idx;++k)
        for(int i=1;i+(1<<k)-1<=Idx;++i)
            St[i][k]=underDepMin(St[i][k-1],St[i+(1<<(k-1))][k-1]);
}
inline int underLca(int x,int y)
{
    x=Id[x],y=Id[y];
    if(x>y) underSwap(x,y);
    int k=Log[y-x+1];
    return underDepMin(St[x][k],St[y-(1<<(k))+1][k]);
}
int main()
{
    // freopen("LCA.in","r",stdin);
    // freopen("LCA.out","w",stdout);
    underRead(N),underRead(M),underRead(Rt);
    for(int i=1,u,v;i<N;++i)
    {
        underRead(u),underRead(v);
        underAddEdge(u,v);
    }
    underDfs(Rt,-1);
    underInit();
    for(int x,y;M;--M)
    {
        underRead(x),underRead(y);
        printf("%d\n",underLca(x,y));
    }
    return 0;
}
/*
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
*/
相关文章