源码:

倍增LCA by pascal

我们知道,一个一个往上跳的LCA是会TLE,这时就有了更快的LCA算法。

“倍增LCA”

倍增LCA分为以下几个步骤:

1
2
1.让2个节点跳到同一个深度,然后完事。
2.一起往上跳,直到找到公共祖先,然后完事。

听起来好简单哦。

倍增

先请大家思考一下,是不是任何一个正整数都能被一些2的n次方加起来?

答案是:可以的。

1
2
3
4
5
16=16
15=8+2+4+1
10=8+2
5=4+1
...

那么,倍增的意思就是:
每次以2的n次方跳跃!!

那么,显而易见,时间复杂度是 log 喽。

我们用一个数组 get[i,j] 来存储 i号节点如果跳了2的j次方,到达的点的编号。

盗一张图来说:
1
2
3
4
get[17,0]=14
get[14,1]=7
get[10,2]=1
get[ 7,3]=?? 0

我们可以发现其实get[i,0]就是平常的father[i]。

1
2
3
get[i,1]可以表示为get[i的father,0],也就是get[get[i,0],1]
get[i,2]可以表示为get[get[i,1],1]
...

那么我们可以发现一个类似的DP式子:
get[i,j]:=get[get[i,j-1],j-1];

操作

操作有2个:

1
2
3
4
5
6
7
1.LCA主题部分:
	(1.跳到同一个深度。
    (2.一起往上跳。
    
2.DFS部分:
	(1.用来记录每一个节点的深度 dep[i] (dep[i]=dep[i的父亲]+1)
    (2.记录get[i,j]

具体的看代码演示:

DFS部分:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
procedure Dfs(cnt,fa:longint); //现在的节点cnt,父亲fa
var
        i:longint;
begin
        dep[cnt]:=dep[fa]+1;  //更新深度
        get[cnt,0]:=fa;  //get的fa,前面已讲
        i:=0;
        repeat
                inc(i); //方++
                get[cnt,i]:=get[get[cnt,i-1],i-1]; //神奇de公式
        until lg[i]>dep[cnt];  //忘了介绍lg[i]=2的i次方,要预处理,大概i到21左右
        i:=head[cnt]; //链式前向星
        while i<>0 do
        begin
                if gt[i]<>fa then
                        Dfs(gt[i],cnt); //其他连边
                i:=next[i];
        end;
end;

然后:

LCA部分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function Find(x_,y_:longint):longint; //两个节点 x_,y_
var
        i,x,y,t:longint;
begin
        x:=x_; y:=y_;
        if dep[x_]<dep[y_] then //交换深度,使y在高处
        begin
                x:=y_;
                y:=x_;
        end;
        for i:=21 downto 0 do //一定是downto!!!(看前面事例)
                if (dep[y]<=dep[x]-lg[i]) then //让x跳到y处
                        x:=get[x,i];
        if x=y then
                exit(x); //如果x已经是y了,那么y就是祖先了
        for i:=21 downto 0 do //一定是downto!!
                if get[x,i]<>get[y,i] then 
                //说明一点,如果我跳过了怎么办?那么我们就跳到祖先的下面(反正任何数都可以被2的n次方相加,对不对),然后直接返回此节点的父亲就得了
                begin
                        x:=get[x,i]; //大家一起跳
                        y:=get[y,i];
                end;
        exit(get[x,0]);
end;

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
var
        get:array[-1..500010,0..21] of longint;
        num,gt,head,next:array[-1..5000010] of longint;
        lg:array[0..21] of longint;
        dep:array[-1..500010] of longint;
        i,n,m,l,r,root:longint;

procedure Main;
var
        i:longint;
begin
        read(n,m,root);
        dec(n);
        for i:=1 to n do
        begin
                read(l,r);
                gt[2*i]:=r;
                next[2*i]:=head[l];
                head[l]:=2*i;
                gt[2*i-1]:=l;
                next[2*i-1]:=head[r];
                head[r]:=2*i-1;
        end;
        lg[0]:=1;
        for i:=1 to 21 do
                lg[i]:=lg[i-1]*2;
end;

function Find(x_,y_:longint):longint;
var
        i,x,y,t:longint;
begin
        x:=x_; y:=y_;
        if dep[x_]<dep[y_] then
        begin
                x:=y_;
                y:=x_;
        end;
        for i:=21 downto 0 do
                if (dep[y]<=dep[x]-lg[i]) then
                        x:=get[x,i];
        if x=y then
                exit(x);
        for i:=21 downto 0 do
                if get[x,i]<>get[y,i] then
                begin
                        x:=get[x,i];
                        y:=get[y,i];
                end;
        exit(get[x,0]);
end;

procedure Dfs(cnt,fa:longint);
var
        i:longint;
begin
        dep[cnt]:=dep[fa]+1;
        get[cnt,0]:=fa;
        i:=0;
        repeat
                inc(i);
                get[cnt,i]:=get[get[cnt,i-1],i-1];
        until lg[i]>dep[cnt];
        i:=head[cnt];
        while i<>0 do
        begin
                if gt[i]<>fa then
                        Dfs(gt[i],cnt);
                i:=next[i];
        end;
end;

procedure Answer;
begin
        read(l,r);
        writeln(Find(l,r));
end;

begin
        Main;
        Dfs(root,-1);
        for i:=1 to m do
                Answer;
end.