# 算法模板——LCA（最近公共祖先）

```  1 type
2     point=^node;
3     node=record
4                g:longint;
5                next:point;
6     end;
7 const
8      maxn=100500;
9      maxm=trunc(ln(maxn)/ln(2))+1;
10 var
11    i,j,k,l,m,n:longint;
12    a:array[0..maxn] of point;
13    c:array[0..maxm,0..maxn] of longint;
14    d:array[0..maxn] of longint;
15 function max(x,y:longint):longint;inline;
16           begin
17                if x>y then max:=x else max:=y;
18           end;
19 function min(x,y:longint):longint;inline;
20          begin
21               if x<y then min:=x else min:=y;
22          end;
23 procedure swap(var x,y:longint);inline;
24           var z:longint;
25           begin
26                z:=x;x:=y;y:=z;
27           end;
29           var p:point;
30           begin
31                new(p);p^.g:=y;
32                p^.next:=a[x];a[x]:=p;
33           end;
34 procedure dfs(x:longint);inline;
35           var p:point;
36           begin
37                p:=a[x];
38                while p<>nil do
39                      begin
40                           if c[0,p^.g]=0 then
41                              begin
42                                   c[0,p^.g]:=x;
43                                   d[p^.g]:=d[x]+1;
44                                   dfs(p^.g);
45                              end;
46                           p:=p^.next;
47                      end;
48           end;
49 function getfat(x,y:longint):longint;inline;
50          var i,j,k:longint;
51          begin
52               i:=0;
53               while y>0 do
54                     begin
55                          if odd(y) then x:=c[i,x];
56                          inc(i);y:=y div 2;
57                     end;
58               exit(x);
59          end;
60 function getcom(x,y:longint):longint;inline;
61          var i:longint;
62          begin
63               if d[x]<d[y] then swap(x,y);
64               x:=getfat(x,d[x]-d[y]);
65               if x=y then exit(x);
66               for i:=maxm downto 0 do
67                   begin
68                        if c[i,x]<>c[i,y] then
69                           begin
70                                x:=c[i,x];
71                                y:=c[i,y];
72                           end;
73                   end;
74               exit(c[0,x]);
75          end;
76
77 begin
79      for i:=1 to n do a[i]:=nil;
80      for i:=1 to n-1 do
81          begin
84          end;
85      fillchar(d,sizeof(d),0);
86      fillchar(c,sizeof(c),0);
87      c[0,1]:=-1;
88      dfs(1);
89      for i:=1 to maxm do
90          for j:=1 to n do
91              c[i,j]:=c[i-1,c[i-1,j]];
92      for i:=1 to m do
93          begin
95               l:=getcom(j,k);
96               writeln(d[j]+d[k]-d[l]-d[l]);
97          end;
99 end.
100                                    ```

0 条评论

• ### 3732: Network

3732: Network Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 395  Solved: 179 ...

• ### 2953: [Poi2002]商务旅行

2953: [Poi2002]商务旅行 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 8  Solved: 8...

• ### 算法模板——线段树7（骰子翻转问题）

实现功能：首先输入一个长度为N的序列，由1-4组成（1表示向前滚一下，2表示向后滚一下，3表示向左滚一下，4表示向右滚一下，骰子原始状态：上1前2左4右5后3下...

• ### 3732: Network

3732: Network Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 395  Solved: 179 ...

• ### 2953: [Poi2002]商务旅行

2953: [Poi2002]商务旅行 Time Limit: 3 Sec  Memory Limit: 128 MB Submit: 8  Solved: 8...

• ### 算法模板——线段树7（骰子翻转问题）

实现功能：首先输入一个长度为N的序列，由1-4组成（1表示向前滚一下，2表示向后滚一下，3表示向左滚一下，4表示向右滚一下，骰子原始状态：上1前2左4右5后3下...

• ### 3359: [Usaco2004 Jan]矩形

3359: [Usaco2004 Jan]矩形 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 8  Solv...

• ### Android Studio你不知道的快捷键(二)

在Android Studio你不知道的快捷键(一)里面，主要讲述了一些窗口操作的快捷键还有补全参数提示等，这一篇会分享一些代码代码编辑的快捷键。(默认Keym...

• ### linux学习第五十五篇： MySQL主从介绍，准备工作，配置主，配置从，测试主从同步

MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主从后，在A上写数据，另外一台B也会跟着写数据，两者数据实时...