1787: [Ahoi2008]Meet 紧急集合

Time Limit: 20 Sec  Memory Limit: 162 MB

Submit: 1482  Solved: 652

[][][]

Description

Input

Output

Sample Input

6 4

1 2

2 3

2 4

4 5

5 6

4 5 6

6 3 1

2 4 4

6 6 6

Sample Output

5 2

2 5

4 1

6 0

HINT

Source

 

题解：很明显，两个人的时候，最优方案即为两者的LCA；而三个点时，必然是某两个点的LCA，然后求出两两的LCA，然后判断即可= =，直接水过

1 /**************************************************************  2     Problem: 1787  3     User: HansBug  4     Language: Pascal  5     Result: Accepted  6     Time:5352 ms  7     Memory:113532 kb  8 ****************************************************************/  9   10 type 11     point=^node; 12     node=record 13                g:longint; 14                next:point; 15     end; 16 var 17    i,j,k,l,m,n,a1,a2,a3,a4,a5,a6:longint; 18    a:array[0..1000000] of point; 19    b:array[0..1000000] of longint; 20    c:array[0..22,0..1000000] of longint; 21    d:array[0..5,1..3] of longint; 22 function min(x,y:longint):longint; 23          begin 24               if x
      
       y then max:=x else max:=y; 29          end; 30 function max3(x,y,z:longint):longint; 31          begin 32               exit(max(max(x,y),z)); 33          end; 34 procedure swap(var x,y:longint); 35           var z:longint; 36           begin 37                z:=x;x:=y;y:=z; 38           end; 39 procedure add(x,y:longint); 40           var p:point; 41           begin 42                new(p);p^.g:=y;p^.next:=a[x];a[x]:=p; 43           end; 44 procedure dfs(y,x:longint); 45           var p:point; 46           begin 47                p:=a[x]; 48                while p<>nil do 49                      begin 50                           if p^.g<>y then 51                              begin 52                                   b[p^.g]:=b[x]+1; 53                                   c[0,p^.g]:=x; 54                                   dfs(x,p^.g); 55                              end; 56                           p:=p^.next; 57                      end; 58           end; 59 function getfat(x,y:longint):longint; 60          var i:longint; 61          begin 62               i:=0; 63               while y>0 do 64                     begin 65                          if odd(y) then x:=c[i,x]; 66                          inc(i);y:=y div 2; 67                     end; 68               exit(x); 69          end; 70 function getcom(x,y:longint):longint; 71          var i:longint; 72          begin 73               if b[x]
       
        c[i,y] then 78                      begin 79                           x:=c[i,x]; 80                           y:=c[i,y]; 81                      end; 82               exit(c[0,x]); 83          end; 84 function dis(x,y:longint):longint; 85          var z:longint; 86          begin 87               z:=getcom(x,y); 88               exit(b[x]-b[z]+b[y]-b[z]); 89          end; 90 procedure sort(l,r:longint); 91           var i,j,x,y:longint; 92           begin 93                i:=l;j:=r;x:=d[(l+r) div 2,1];y:=d[(l+r) div 2,2]; 94                repeat 95                      while (d[i,1]
        
         x) do dec(j); 97                      if i<=j then 98                         begin 99                              swap(d[i,1],d[j,1]);100                              swap(d[i,2],d[j,2]);101                              inc(i);dec(j);102                         end;103                until i>j;104                if i
         
          j then sort(l,j);106           end;107 begin108      readln(n,m);109      for i:=1 to n do a[i]:=nil;110      for i:=1 to n-1 do111          begin112               readln(j,k);113               add(j,k);add(k,j);114          end;115      l:=random(n)+1;b[l]:=1;116      dfs(0,l);117      for i:=1 to trunc(ln(n)/ln(2)+1) do118          for j:=1 to n do119              c[i,j]:=c[i-1,c[i-1,j]];120      for i:=1 to m do121          begin122               readln(j,k,l);123               a1:=getcom(j,k);124               a2:=getcom(k,l);125               a3:=getcom(j,l);126               a4:=dis(a1,l);127               d[1,1]:=(b[j]-b[a1])+(b[k]-b[a1])+a4;128               d[1,2]:=a1;129               a5:=dis(a2,j);130               d[2,1]:=a5+(b[k]-b[a2])+(b[l]-b[a2]);131               d[2,2]:=a2;132               a6:=dis(a3,k);133               d[3,1]:=(b[j]-b[a3])+a6+(b[l]-b[a3]);134               d[3,2]:=a3;135               sort(1,3);writeln(d[1,2],' ',d[1,1]);136          end;137 end.