fork download
copy 
  1.     uses    math;
  2.     const   fi='';
  3.             fo='';
  4.             maxk=20;
  5.             maxn=trunc(1e5)+3;
  6.             oo=2*trunc(1e9);
  7.  
  8.     type    arr1    =array[1..maxn] of longint;
  9.             arr2    =array[1..maxn,0..maxk] of longint;
  10.  
  11.     var     mi,ma,p         :arr2;
  12.             depth,dad       :arr1;
  13.             i,j,n,m,q       :longint;
  14.             link,head,ke,ts :array[-maxn..maxn] of longint;
  15.             resma,resmi     :longint;
  16.             cx      :array[1..maxn] of boolean;
  17.     procedure add(i,u,v,w:longint);
  18.     begin
  19.             link[i]:=head[u];
  20.             head[u]:=i;
  21.             ke[i]:=v;
  22.             ts[i]:=w;
  23.     end;
  24.  
  25.     procedure enter;
  26.     var     u,v,w   :longint;
  27.     begin
  28.             readln(n);
  29.             for i:=1 to n-1 do
  30.             begin
  31.                     read(u,v,w);
  32.                     add(i,u,v,w);
  33.                     add(-i,v,u,w);
  34.             end;
  35.     end;
  36.  
  37.     procedure dfs(u:longint);
  38.     var     i,v     :longint;
  39.     begin
  40.             cx[u]:=false;
  41.             i := head[u];
  42.             while i<>0 do
  43.                     begin
  44.                             v:=ke[i];
  45.                             if cx[v] then
  46.                                     begin
  47.                                             depth[v]:=depth[u]+1;
  48.                                             dad[v]:=u; ma[v,0] := ts[i]; mi[v,0] := ts[i];
  49.                                             dfs(v);
  50.                                     end;
  51.                             i:=link[i];
  52.                     end;
  53.     end;
  54.  
  55.     procedure init;
  56.     var     i,j     :longint;
  57.     begin
  58.             fillchar(cx,sizeof(cx),true);
  59.             dad[1] := 1; depth[1] :=1;
  60.             dfs(1);
  61.             for i:=1 to n do
  62.                     begin
  63.                             p[i,0] := dad[i];
  64.                     end;
  65.             for j:=1 to maxk do mi[1,0] := oo;
  66.             for j:=1 to maxk do ma[1,0] := -oo;
  67.             for j:=1 to maxk do
  68.                     for i:=1 to n do
  69.                             begin
  70.                                     p[i,j] := p[p[i,j-1],j-1];
  71.                                     ma[i,j] := max(ma[i,j-1],ma[p[i,j-1],j-1]);
  72.                                     mi[i,j] := min(mi[i,j-1],mi[p[i,j-1],j-1]);
  73.                             end;
  74.     end;
  75.     procedure lca(u,v:longint);
  76.     var     i,j     :longint;
  77.     begin
  78.             for i:=maxk downto 0 do
  79.                     if depth[p[u,i]]>=depth[v] then
  80.                             begin
  81.                                     resma := max(resma,ma[u,i]);
  82.                                     resmi := min(resmi,mi[u,i]);
  83.                                     u := p[u,i];
  84.                             end;
  85.             for i:=maxk downto 0 do
  86.                     if depth[p[v,i]]>=depth[u] then
  87.                             begin
  88.                                     resma := max(resma,ma[v,i]);
  89.                                     resmi := min(resmi,mi[v,i]);
  90.                                     v := p[v,i];
  91.                             end;
  92.             if u=v then exit;
  93.             for i:=maxk downto 0 do
  94.                     if p[u,i]<>p[v,i] then
  95.                             begin
  96.                                     resma := max(resma,ma[v,i]);
  97.                                     resmi := min(resmi,mi[v,i]);
  98.                                     resma := max(resma,ma[u,i]);
  99.                                     resmi := min(resmi,mi[u,i]);
  100.                                     v := p[v,i];
  101.                                     u := p[u,i];
  102.                             end;
  103.             resma := max(resma,ma[v,0]);
  104.             resmi := min(resmi,mi[v,0]);
  105.             resma := max(resma,ma[u,0]);
  106.             resmi := min(resmi,mi[u,0]);
  107.     end;
  108.     procedure process;
  109.     var     u,v,qq  :longint;
  110.     begin
  111.             read(q);
  112.             for qq:=1 to q do
  113.                     begin
  114.                             read(u,v);
  115.                             if u=v then begin writeln(0,' ',0); continue; end;
  116.                                     resmi := oo;
  117.                                     resma := -oo;
  118.                                     lca(u,v);
  119.                             writeln(resmi,' ',resma);
  120.                     end;
  121.     end;
  122.     procedure print;
  123.     begin
  124.  
  125.     end;
  126.  
  127.     begin
  128.             assign(input,fi);reset(input);
  129.             assign(output,fo);rewrite(output);
  130.                     enter;
  131.                     init;
  132.                     process;
  133.                     print;
  134.             close(input);close(output);
  135.     end.
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/6yKHJk
language:
Pascal (fpc 3.0.4)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!