fork download
copy 
  1. const
  2.         tfi='';
  3.         tfo='';
  4.  
  5. var
  6.         fi,fo:Text;
  7.         ke,nx:array[-70000..70000] of longint;
  8.         num,thoat,hd:array[0..70000] of longint;
  9.         f:array[0..70000,0..20] of longint;
  10.         n,q,jmax,dem,dem1:longint;
  11.         t:array[0..3000000] of longint;
  12.  
  13. procedure nhap;
  14.         var i,j,u,v:longint;
  15.         begin
  16.                 read(fi,n,q);
  17.                 for i:=1 to n-1 do
  18.                         begin
  19.                                 read(fi,u,v);
  20.                                 ke[i]:=v;
  21.                                 nx[i]:=hd[u];
  22.                                 hd[u]:=i;
  23.                                 ke[-i]:=u;
  24.                                 nx[-i]:=hd[v];
  25.                                 hd[v]:=-i;
  26.                         end;
  27.                 for j:=1 to 20 do if 1 shl j<=n then jmax:=j+1;
  28.         end;
  29.  
  30. procedure DFS(u:longint);
  31.         var j,v:longint;
  32.         begin
  33.                 inc(dem);
  34.                 num[u]:=dem;
  35.                 for j:=1 to jmax do f[u,j]:=f[f[u,j-1],j-1];
  36.                 j:=hd[u];
  37.                 while j<>0 do
  38.                         begin
  39.                                 v:=ke[j];
  40.                                 if f[v,0]=0 then
  41.                                         begin
  42.                                                 f[v,0]:=u;
  43.                                                 DFS(v);
  44.                                         end;
  45.                                 j:=nx[j];
  46.                         end;
  47.                 inc(dem1);
  48.                 thoat[u]:=dem1;
  49.         end;
  50.  
  51. function cha(x,y:longint):boolean;
  52.         begin
  53.             cha:=(num[x]<=num[y]) and (thoat[y]<=thoat[x]);
  54.         end;
  55.  
  56. function lca(x,y:longint):longint;
  57.         var j:longint;
  58.         begin
  59.                 if cha(x,y) then exit(x);
  60.                 if cha(y,x) then exit(y);
  61.                 for j:=jmax downto 0 do
  62.                         if not cha(f[x,j],y) then x:=f[x,j];
  63.                 exit(f[x,0]);
  64.         end;
  65.  
  66. procedure init(i,l,r:longint);
  67.         var mid:longint;
  68.         begin
  69.             if l=r then
  70.                 begin
  71.                         t[i]:=l;
  72.                         exit;
  73.                 end;
  74.             mid:=(l+r) div 2;
  75.             init(i*2,l,mid);
  76.             init(i*2+1,mid+1,r);
  77.             t[i]:=lca(t[i*2],t[i*2+1]);
  78.         end;
  79.  
  80. function get(i,l,r,u,v:longint):longint;
  81.         var mid:longint;
  82.         begin
  83.                 if (l>v) or (r<u) then exit(u);
  84.                 if (u<=l) and (r<=v) then exit(t[i]);
  85.                 mid:=(l+r) div 2;
  86.                 get:=lca(get(i*2,l,mid,u,v),get(i*2+1,mid+1,r,u,v));
  87.         end;
  88.  
  89. procedure xuli;
  90.         var i,u,v,pa,j:longint;
  91.         begin
  92.                 f[1,0]:=1;
  93.                 DFS(1);
  94.                 init(1,1,n);
  95.                 for i:=1 to q do
  96.                         begin
  97.                                 read(fi,u,v);
  98.                                 writeln(fo,get(1,1,n,u,v));
  99.                         end;
  100.  
  101.         end;
  102.  
  103. begin
  104.         assign(fi,tfi);
  105.         assign(fo,tfo);
  106.         reset(fi);
  107.         rewrite(fo);
  108.         nhap;
  109.         xuli;
  110.         close(fo);
  111. end.
Time limit exceeded #stdin #stdout 5s 2891776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/gVVsof
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!