[Ahoi2008]Meet 紧急集合
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
分析：很简单的一道题，对于每次询问要分情况讨论，先求出两两之间的lca，如果为同一点，显然该点为集合点，如果有一个x不同于另外两个，则三者在一条链上，x为中间的一个，故x为集合点，如果三者互不相同，集合点可以是三者到共同lca路径上任何一点，或者干脆将三者共同lca作为集合点就行了。
代码：
program Meet;
type
point=^node;
node=record
x:longint; next:point;
end;
var
a:array[..]of point;
f:array[..,..]of longint;
deep,s:array[..]of longint;
n,i,m,x,y,t,z,v1,v2,v3,ans:longint;
procedure add(x,y:longint);
var p:point;
begin
new(p); p^.x:=y; p^.next:=a[x]; a[x]:=p;
end;
procedure dfs(x,k:longint);
var p:point;
begin
new(p); p:=a[x]; f[,x]:=k; deep[x]:=deep[k]+;
while p<>nil do
begin
if p^.x<>k then dfs(p^.x,x);p:=p^.next;
end;
end;
procedure work;
var i,j:longint;
begin
for i:= to trunc(ln(n)/ln())- do
for j:= to n do
f[i+,j]:=f[i,f[i,j]];
end;
function lca(x,y:longint):longint;
var i,t:longint;
begin
if deep[x]<deep[y] then begin t:=x; x:=y; y:=t; end;
for i:= to trunc(ln(n)/ln()) do
if ((deep[x]-deep[y])>>i) and = then x:=f[i,x];
if x=y then exit(x);
for i:=trunc(ln(n)/ln()) downto do
if f[i,x]<>f[i,y] then
begin x:=f[i,x]; y:=f[i,y]; end;
exit(f[,x]);
end;
begin
assign(input,'Meet.in');
reset(input);
assign(output,'Meet.out');
rewrite(output);
readln(n,m);
for i:= to n- do
begin
readln(x,y); add(x,y); add(y,x);
end;
deep[]:=;
dfs(,); work;
for i:= to m do
begin
readln(x,y,z);
v1:=lca(x,y); v2:=lca(x,z); v3:=lca(z,y);
if (v1=v2)and(v2=v3) then t:=v1
else if v1=v2 then t:=v3
else if v2=v3 then t:=v1
else t:=v2;
v1:=lca(x,t); v2:=lca(y,t); v3:=lca(z,t);
ans:=deep[x]+deep[y]+deep[z]+deep[t]*-*(deep[v1]+deep[v2]+deep[v3]);
writeln(t,' ',ans);
end;
close(input); close(output);
end.