jiry_2's Blog

显然我们要求出每个询问两个点的最近公共祖先。然后我们可以求出其最短路径上的点数。显然，如果要不能构成三角形，那么上面的点权一定是按照大于斐波那契数列排列的，这样在55项左右就超过MAXLONGINT。所以大于等于55一定构成三角形。余下的反正是有50+的点直接SORT一下然后暴力即可。PASCAL的代码又一次又臭又长，居然垫底了。。QAQ

program p3251;
	type
		bian=record
			next,point:int64;
		end;
		arr=array[0..500] of int64;
	var
		f:array[1..111111,0..17] of int64;
		w,d,p:array[1..111111] of int64;
		b:array[1..111111] of bian;
		way:arr;
		len,i,j,q,n,k1,k2,k3:longint;
		ch:char;
		pd:boolean;
	procedure add(k1,k2:int64);
		begin
			inc(len); 
			b[len].point:=k2;
			b[len].next:=p[k1];
			p[k1]:=len;
		end;
	procedure find(k1,k2:int64);
		var
			i,j:longint;
		begin
			d[k1]:=k2;
			i:=p[k1];
			while i<>0 do begin
				find(b[i].point,k2+1);
				i:=b[i].next;
			end;
		end;
	function go_up(k1,k2:int64):int64;
		var
			i,j,k:longint;
		begin
			if k2=0 then exit(k1);
			for k:=0 to 17 do
				if 1 shl k>k2 then break;
			dec(k);
			for i:=0 to k do 
				if k2 and (1 shl i)>0 then k1:=f[k1,i];
			exit(k1);
		end;
	procedure sort(var x:arr;first,en:longint);
		var
			i,j:longint;
		begin
			i:=first; j:=en; x[0]:=x[first];
			while i<j do begin
				while (i<j) and (w[x[j]]>=w[x[0]]) do dec(j);
				if i<j then x[i]:=x[j];
				while (i<j) and (w[x[i]]<w[x[0]]) do inc(i);
				if i<j then x[j]:=x[i];
			end;
			x[i]:=x[0];
			if i>first+1 then sort(x,first,i-1);
			if i<en-1 then sort(x,i+1,en);
		end;	
	function answer(k1,k2:int64):char;
		var
			k,i,j,k3,k4,k5,l:longint;
		begin
			if d[k1]>d[k2] then begin
				i:=k1; k1:=k2; k2:=i;
			end;
			k3:=go_up(k2,d[k2]-d[k1]);
			for k:=0 to 17 do
				if 1 shl k>=d[k3] then break;
			dec(k);
			k4:=k1;
			if k3<>k4 then begin
				for i:=k downto 0 do
					if f[k3,i]<>f[k4,i] then begin
						k3:=f[k3,i];
						k4:=f[k4,i];
					end;
				k3:=f[k3,0];
			end;
			l:=d[k1]-d[k3]+d[k2]-d[k3]+1;
			if (l<3) then exit('N');
			if (l>=55) then exit('Y');
			l:=0;
			i:=k1; 
			while i<>k3 do begin
				inc(l); way[l]:=i; i:=f[i,0];
			end;
			i:=k2; inc(l); way[l]:=i;
			while i<>k3 do begin
				i:=f[i,0]; inc(l); way[l]:=i;
			end;
			sort(way,1,l);
			for i:=3 to l do
				if w[way[i-2]]+w[way[i-1]]>w[way[i]] then exit('Y');
			exit('N');
		end;
	begin
		readln(n,q);
		len:=0;
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		fillchar(f,sizeof(f),0);
		for i:=1 to n do
			read(w[i]);
		for i:=1 to n-1 do begin
			readln(k1,k2);
			f[k2,0]:=k1;
			add(k1,k2);
		end;
		find(1,1);
		for i:=1 to 17 do begin
			pd:=false;
			for j:=1 to n do
				if 1 shl i<d[j] then begin
					pd:=true;
					f[j,i]:=f[f[j,i-1],i-1];
				end;
			if pd=false then break;
		end;
		for i:=1 to q do begin
			readln(k1,k2,k3);
			if k1=0 then
				writeln(answer(k2,k3))
			else 
				w[k2]:=k3;
		end;
	end.