首页 > 其他 > 详细

LCA(倍增)

时间:2015-03-23 15:18:31      阅读:261      评论:0      收藏:0      [点我收藏+]
type arr=record v,nt:longint; end;
const maxn=10008; lx=20;
var lt:array[0..maxn] of longint;    
    eg:array[0..maxn*2] of arr;
    d:array[0..maxn] of longint;
    g:array[0..maxn,0..lx] of longint;
    n,i,x,y,a,b,sum:longint;
procedure swap(var a,b:longint);
var c:longint;
begin
    c:=a; a:=b; b:=c;
end;
procedure add(x,y:longint);
begin
    inc(sum); eg[sum].nt:=lt[x]; eg[sum].v:=y; lt[x]:=sum;
end;
procedure Tinit(x,fa:longint);
var i:longint;
begin
    g[x,0]:=fa; d[x]:=d[fa]+1;
    for i:=1 to lx do
        g[x,i]:=g[g[x,i-1],i-1];
    i:=lt[x];
    while i<>0 do
    begin
                if eg[i].v<>fa then Tinit(eg[i].v,x);
        i:=eg[i].nt;
    end;
end;
function Tlca(x,y:longint):longint;
var dep:longint;
begin
    if d[x]<d[y] then swap(x,y);
    dep:=d[x]-d[y];
    for i:=0 to lx-1 do
        if dep and (1<<i) >0 then
            x:=g[x,i];
    if x=y then exit(x);
    for i:=lx-1 downto 0 do
        if g[x,i]<>g[y,i] then
        begin
            x:=g[x,i];
            y:=g[y,i];
        end;
    exit(g[x][0]);
end;
function Tdist(x,y:longint):longint;
begin
    exit(d[x]+d[y]-d[Tlca(x,y)]*2);
end;
begin
    readln(n,a,b);
    sum:=0;
    while not eof do
    begin
        read(x);
        while not eoln do
        begin
            read(y);
            add(x,y);
            add(y,x);
        end;
        readln;
    end;
    Tinit(1,0);
    writeln(Tlca(a,b));
    writeln(Tdist(a,b));
end.

 

LCA(倍增)

原文:http://www.cnblogs.com/rpSebastian/p/4359747.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!