算法模板——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