如果只有两个点,我们可以保证最有集合地点一定为其最近公共祖先。而这儿三个点的话可以证明最有集合地点一定为三点中两点的最近公共祖先。这样我们只需要把可能的三个方案都求出来然后取最优就可以了。为了保证不TLE,需要用倍增算法来确保NLOGN时间复杂度的在线查询。
program p1787;
type
bian=record
point,next:longint;
end;
var
b:array[1..1000005] of bian;
p,d:array[0..500005] of longint;
f:array[1..500005,1..30] of longint;
len,n,m,i,j,k1,k2,k3,w1,w2,w3:longint;
extra:array[1..3,1..2] of longint;
bo:boolean;
procedure ade(k1,k2:longint);
begin
inc(len);
b[len].point:=k2;
b[len].next:=p[k1];
p[k1]:=len;
end;
procedure add(k1,k2:longint);
begin
ade(k1,k2);
ade(k2,k1);
end;
procedure dfs(k1,k2:longint);
var
i,j:longint;
begin
d[k1]:=d[k2]+1;
f[k1,0]:=k2;
i:=p[k1];
while i<>0 do begin
j:=b[i].point;
if j<>k2 then dfs(j,k1);
i:=b[i].next;
end;
end;
function go_up(k1,k2:longint):longint;
var
i,j,k:longint;
begin
for k:=0 to 30 do
if 1 shl k>k2 then break;
dec(k); if k<0 then exit(k1);
j:=k1;
for i:=0 to k do
if k2 and (1 shl i)>0 then
j:=f[j,i];
exit(j);
end;
function fcf(k1,k2:longint):longint;
var
i,j,k:longint;
begin
if d[k1]>d[k2] then begin
i:=k1; k1:=k2; k2:=i;
end;
k2:=go_up(k2,d[k2]-d[k1]);
if k1=k2 then exit(k1);
for k:=1 to 30 do
if 1 shl k>=d[k1] then break;
dec(k);
for i:=k downto 0 do
if f[k1,i]<>f[k2,i] then begin
k1:=f[k1,i]; k2:=f[k2,i];
end;
exit(f[k1,0]);
end;
function pay(k1,k2,k3:longint):longint;
begin
exit(d[k1]-d[k3]+d[k2]-d[k3]);
end;
begin
fillchar(p,sizeof(p),0);
fillchar(b,sizeof(b),0);
readln(n,m);
len:=0;
for i:=1 to n-1 do begin
readln(k1,k2);
add(k1,k2);
end;
fillchar(d,sizeof(d),0);
fillchar(f,sizeof(f),0);
d[0]:=0;
dfs(1,0);
j:=1; bo:=true;
while bo=true do begin
bo:=false;
for i:=1 to n do begin
if d[i]<=1 shl j then continue;
f[i,j]:=f[f[i,j-1],j-1];
bo:=true;
end;
inc(j);
end;{
for i:=0 to 3 do begin
for j:=1 to n do
write(f[j,i],' ');
writeln;
end;}
for i:=1 to m do begin
readln(k1,k2,k3);
extra[1,1]:=fcf(k1,k2);
extra[1,2]:=fcf(extra[1,1],k3);
extra[2,1]:=fcf(k1,k3);
extra[2,2]:=fcf(extra[2,1],k2);
extra[3,1]:=fcf(k2,k3);
extra[3,2]:=fcf(extra[3,1],k1);
w1:=pay(k1,k2,extra[1,1])+pay(extra[1,1],k3,extra[1,2]);
w2:=pay(k1,k3,extra[2,1])+pay(extra[2,1],k2,extra[2,2]);
w3:=pay(k2,k3,extra[3,1])+pay(extra[3,1],k1,extra[3,2]);
if w1<w2 then begin
k1:=extra[1,1]; k2:=w1;
end else begin
k1:=extra[2,1]; k2:=w2;
end;
if k2>w3 then begin
k1:=extra[3,1]; k2:=w3;
end;
{for j:=1 to 3 do
writeln(extra[j,1],' ',extra[j,2]);
writeln(w1,' ',w2,' ',w3);}
writeln(k1,' ',k2);
end;
end.