HBTLCA – SPOJ

Đề bài: http://vn.spoj.com/problems/HBTLCA/

Thuật toán:

• (đang cập nhập)

Code:

const
    tfi='';//hbtlca.inp';
    tfo='';//hbtlca.out';

var
    fi,fo:Text;
    n,jmax,dem1,goc,dem2:longint;
    ke,nx:array[-100000..100000] of longint;
    hd,num,thoat,d:array[0..100000] of longint;
    f:array[0..100000,0..20] of longint;

procedure nhap;
    var i,u,v:longint;
    begin
        read(fi,n);
        fillchar(hd,sizeof(hd),0);
        for i:=1 to n-1 do
            begin
                read(fi,u,v);
                ke[i]:=v;
                nx[i]:=hd[u];
                hd[u]:=i;
                ke[-i]:=u;
                nx[-i]:=hd[v];
                hd[v]:=-i;
            end;
        for i:=0 to 20 do if 1 shl i<=n then jmax:=i+1;
    end;

procedure DFS(u:longint);
    var i,j,v:longint;
    begin
        inc(dem1);
        num[u]:=dem1;
        for j:=1 to jmax do
            f[u,j]:=f[f[u,j-1],j-1];
        j:=hd[u];
        while j<>0 do
            begin
                v:=ke[j];
                if v<>f[u,0] then
                    begin
                        f[v,0]:=u;
                        d[v]:=d[u]+1;
                        DFS(v);
                    end;
                j:=nx[j];
            end;
        inc(dem2);
        thoat[u]:=dem2;
    end;

function cha(x,y:longint):boolean;
    begin
        cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
    end;

function lca(x,y:longint):longint;
    var j:longint;
    begin
        if cha(x,y) then exit(x);
        if cha(y,x) then exit(y);
        for j:=jmax downto 0 do
            if not cha(f[x,j],y) then x:=f[x,j];
        exit(f[x,0]);
    end;

procedure check(u,v:longint);
    var pa,pa1,pa2:longint;
    begin
        pa:=lca(u,v);
        pa1:=lca(goc,u);
        pa2:=lca(goc,v);
        if (d[pa]>=d[pa1]) and (d[pa]>=d[pa2]) then writeln(fo,pa)
        else
        if (d[pa1]>=d[pa2]) and (d[pa1]>=d[pa]) then writeln(fo,pa1)
        else writeln(fo,pa2);
    end;

procedure xuli;
    var i,j,q,u,v:longint;
        ch:char;
    begin
        while true do
        begin
        nhap;
        if n=0 then exit;
        dem1:=0;
        dem2:=0;
        f[1,0]:=1;
        DFS(1);
        readln(fi,q);
        goc:=1;
        for i:=1 to q do
            begin
                read(fi,ch);
                if ch='!' then
                    begin
                        readln(fi,goc);
                    end
                else
                if ch='?' then
                    begin
                        readln(fi,u,v);
                        check(u,v);
                    end;
            end;
        end;
    end;

begin
    assign(fi,tfi);
    assign(fo,tfo);
    reset(fi);
    rewrite(fo);
    xuli;
    close(fo);
end.