1787: [Ahoi2008]Meet 紧急集合

Time Limit: 20 Sec Memory Limit: 162 MB
Submit: 1482 Solved: 652
[Submit][Status][Discuss]
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

Day1
题解：很明显，两个人的时候，最优方案即为两者的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 min:=x else min:=y;
 25          end;
 26 function max(x,y:longint):longint;
 27          begin
 28               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]<b[y] then swap(x,y);
 74               x:=getfat(x,b[x]-b[y]);
 75               if x=y then exit(x);
 76               for i:=trunc(ln(b[x])/ln(2)+1) downto 0 do
 77                   if c[i,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 inc(i);
 96                      while (d[j,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<r then sort(i,r);
105                if l>j then sort(l,j);
106           end;
107 begin
108      readln(n,m);
109      for i:=1 to n do a[i]:=nil;
110      for i:=1 to n-1 do
111          begin
112               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) do
118          for j:=1 to n do
119              c[i,j]:=c[i-1,c[i-1,j]];
120      for i:=1 to m do
121          begin
122               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.