8
27
2013
1

【BZOJ1787】【Ahoi2008】Meet 紧急集合【倍增(最近公共祖先)】

如果只有两个点,我们可以保证最有集合地点一定为其最近公共祖先。而这儿三个点的话可以证明最有集合地点一定为三点中两点的最近公共祖先。这样我们只需要把可能的三个方案都求出来然后取最优就可以了。为了保证不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.
Category: 倍增 | Tags: | Read Count: 1669
Avatar_small
Junior Dakil Result 说:
2022年9月02日 03:07

Bangladesh Sylhet Division Secondary and Higher Secondary Education Board also successfully completed the Junior School Certificate and Junior Dakhil Certificate of Grade 8th standard annual terminal examination tests on November 2022 at all selected examination centers of the division, according to the reports lacks students have appeared from all districts under the Division and they all are waiting to check JSC Result 2022 Sylhet Board. Department of Secondary Education, JJunior Dakil Result Sylhet Board Sylhet Division also conducted an evaluation process to the valuation of subject wise marks through answer sheet correction and the process of evaluation will be complete in before 2nd week of December 2022 and the education board will update answer scripts with student wise mark sheets in subject wise with total GPA grade points to Secondary and Higher Secondary Education Board Bangladesh.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com