Đề bài:
Thuật toán:
- LCA
Code:
- Pascal : https://ideone.com/6yKHJk
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 |
Speak Your Mind