LUBENICA – spoj

03/12/2017 by Leave a Comment

Đề bài:

Thuật toán:

  • LCA

Code:

uses    math;
const   fi='';
        fo='';
        maxk=20;
        maxn=trunc(1e5)+3;
        oo=2*trunc(1e9);
 
type    arr1    =array[1..maxn] of longint;
        arr2    =array[1..maxn,0..maxk] of longint;
 
var     mi,ma,p         :arr2;
        depth,dad       :arr1;
        i,j,n,m,q       :longint;
        link,head,ke,ts :array[-maxn..maxn] of longint;
        resma,resmi     :longint;
        cx      :array[1..maxn] of boolean;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
 
procedure enter;
var     u,v,w   :longint;
begin
        readln(n);
        for i:=1 to n-1 do
        begin
                read(u,v,w);
                add(i,u,v,w);
                add(-i,v,u,w);
        end;
end;
 
procedure dfs(u:longint);
var     i,v     :longint;
begin
        cx[u]:=false;
        i := head[u];
        while i<>0 do
                begin
                        v:=ke[i];
                        if cx[v] then
                                begin
                                        depth[v]:=depth[u]+1;
                                        dad[v]:=u; ma[v,0] := ts[i]; mi[v,0] := ts[i];
                                        dfs(v);
                                end;
                        i:=link[i];
                end;
end;
 
procedure init;
var     i,j     :longint;
begin
        fillchar(cx,sizeof(cx),true);
        dad[1] := 1; depth[1] :=1;
        dfs(1);
        for i:=1 to n do
                begin
                        p[i,0] := dad[i];
                end;
        for j:=1 to maxk do mi[1,0] := oo;
        for j:=1 to maxk do ma[1,0] := -oo;
        for j:=1 to maxk do
                for i:=1 to n do
                        begin
                                p[i,j] := p[p[i,j-1],j-1];
                                ma[i,j] := max(ma[i,j-1],ma[p[i,j-1],j-1]);
                                mi[i,j] := min(mi[i,j-1],mi[p[i,j-1],j-1]);
                        end;
end;
procedure lca(u,v:longint);
var     i,j     :longint;
begin
        for i:=maxk downto 0 do
                if depth[p[u,i]]>=depth[v] then
                        begin
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                u := p[u,i];
                        end;
        for i:=maxk downto 0 do
                if depth[p[v,i]]>=depth[u] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                v := p[v,i];
                        end;
        if u=v then exit;
        for i:=maxk downto 0 do
                if p[u,i]<>p[v,i] then
                        begin
                                resma := max(resma,ma[v,i]);
                                resmi := min(resmi,mi[v,i]);
                                resma := max(resma,ma[u,i]);
                                resmi := min(resmi,mi[u,i]);
                                v := p[v,i];
                                u := p[u,i];
                        end;
        resma := max(resma,ma[v,0]);
        resmi := min(resmi,mi[v,0]);
        resma := max(resma,ma[u,0]);
        resmi := min(resmi,mi[u,0]);
end;
procedure process;
var     u,v,qq  :longint;
begin
        read(q);
        for qq:=1 to q do
                begin
                        read(u,v);
                        if u=v then begin writeln(0,' ',0); continue; end;
                                resmi := oo;
                                resma := -oo;
                                lca(u,v);
                        writeln(resmi,' ',resma);
                end;
end;
procedure print;
begin
 
end;
 
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
                enter;
                init;
                process;
                print;
        close(input);close(output);
end
Chủ đề: LCA Mức độ:
Khuyên dùng

 

Speak Your Mind

*