专栏首页HansBug's Lab算法模板——LCA(最近公共祖先)

算法模板——LCA(最近公共祖先)

实现的功能如下——在一个N个点的无环图中,共有N-1条边,M个访问中每次询问两个点的距离

原理——既然N个点,N-1条边,则说明这是一棵树,而且联通。所以以1为根节点DFS建树,然后通过求两点的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;
 28 procedure add(x,y:longint);inline;
 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
 78      readln(n,m);
 79      for i:=1 to n do a[i]:=nil;
 80      for i:=1 to n-1 do
 81          begin
 82               readln(j,k);
 83               add(j,k);add(k,j);
 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
 94               readln(j,k);
 95               l:=getcom(j,k);
 96               writeln(d[j]+d[k]-d[l]-d[l]);
 97          end;
 98      readln;
 99 end.
100                                    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 3732: Network

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

    HansBug
  • 2953: [Poi2002]商务旅行

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

    HansBug
  • 算法模板——线段树7(骰子翻转问题)

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

    HansBug
  • 3732: Network

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

    HansBug
  • 2953: [Poi2002]商务旅行

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

    HansBug
  • 算法模板——线段树7(骰子翻转问题)

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

    HansBug
  • 3359: [Usaco2004 Jan]矩形

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

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

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

    weishu
  • Android – DataBinding 自定义setter

    code_horse
  • linux学习第五十五篇: MySQL主从介绍,准备工作,配置主,配置从,测试主从同步

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

    用户1215343

扫码关注云+社区

领取腾讯云代金券