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
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
2 5
4 1
6 0
HINT
Source
题解：很明显，两个人的时候，最优方案即为两者的LCA；而三个点时，必然是某两个点的LCA，然后求出两两的LCA，然后判断即可= =，直接水过
/**************************************************************
Problem:
User: HansBug
Language: Pascal
Result: Accepted
Time: ms
Memory: kb
****************************************************************/ type
point=^node;
node=record
g:longint;
next:point;
end;
var
i,j,k,l,m,n,a1,a2,a3,a4,a5,a6:longint;
a:array[..] of point;
b:array[..] of longint;
c:array[..,..] of longint;
d:array[..,..] of longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x else min:=y;
end;
function max(x,y:longint):longint;
begin
if x>y then max:=x else max:=y;
end;
function max3(x,y,z:longint):longint;
begin
exit(max(max(x,y),z));
end;
procedure swap(var x,y:longint);
var z:longint;
begin
z:=x;x:=y;y:=z;
end;
procedure add(x,y:longint);
var p:point;
begin
new(p);p^.g:=y;p^.next:=a[x];a[x]:=p;
end;
procedure dfs(y,x:longint);
var p:point;
begin
p:=a[x];
while p<>nil do
begin
if p^.g<>y then
begin
b[p^.g]:=b[x]+;
c[,p^.g]:=x;
dfs(x,p^.g);
end;
p:=p^.next;
end;
end;
function getfat(x,y:longint):longint;
var i:longint;
begin
i:=;
while y> do
begin
if odd(y) then x:=c[i,x];
inc(i);y:=y div ;
end;
exit(x);
end;
function getcom(x,y:longint):longint;
var i:longint;
begin
if b[x]<b[y] then swap(x,y);
x:=getfat(x,b[x]-b[y]);
if x=y then exit(x);
for i:=trunc(ln(b[x])/ln()+) downto do
if c[i,x]<>c[i,y] then
begin
x:=c[i,x];
y:=c[i,y];
end;
exit(c[,x]);
end;
function dis(x,y:longint):longint;
var z:longint;
begin
z:=getcom(x,y);
exit(b[x]-b[z]+b[y]-b[z]);
end;
procedure sort(l,r:longint);
var i,j,x,y:longint;
begin
i:=l;j:=r;x:=d[(l+r) div ,];y:=d[(l+r) div ,];
repeat
while (d[i,]<x) do inc(i);
while (d[j,]>x) do dec(j);
if i<=j then
begin
swap(d[i,],d[j,]);
swap(d[i,],d[j,]);
inc(i);dec(j);
end;
until i>j;
if i<r then sort(i,r);
if l>j then sort(l,j);
end;
begin
readln(n,m);
for i:= to n do a[i]:=nil;
for i:= to n- do
begin
readln(j,k);
add(j,k);add(k,j);
end;
l:=random(n)+;b[l]:=;
dfs(,l);
for i:= to trunc(ln(n)/ln()+) do
for j:= to n do
c[i,j]:=c[i-,c[i-,j]];
for i:= to m do
begin
readln(j,k,l);
a1:=getcom(j,k);
a2:=getcom(k,l);
a3:=getcom(j,l);
a4:=dis(a1,l);
d[,]:=(b[j]-b[a1])+(b[k]-b[a1])+a4;
d[,]:=a1;
a5:=dis(a2,j);
d[,]:=a5+(b[k]-b[a2])+(b[l]-b[a2]);
d[,]:=a2;
a6:=dis(a3,k);
d[,]:=(b[j]-b[a3])+a6+(b[l]-b[a3]);
d[,]:=a3;
sort(,);writeln(d[,],' ',d[,]);
end;
end.