jiry_2's Blog

如果只有两个点，我们可以保证最有集合地点一定为其最近公共祖先。而这儿三个点的话可以证明最有集合地点一定为三点中两点的最近公共祖先。这样我们只需要把可能的三个方案都求出来然后取最优就可以了。为了保证不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.