jiry_2's Blog

很容易就可以想到时间复杂度为nlog²n的算法。即用类似于求最近公共祖先的预处理。令f[i][j]为i的第2^j祖先。w[i][j]为i到f[i][j]路径不包括i的权值和。则可以得到递推式:f[i][j]=f[f[i,j-1]][j-1]，w[i][j]=w[f[i,j-1]][j-1]+w[i][j-1]。然后对于节点i，二分路径向上走多少层，如果可以二分得到其路径权值和s恰好相等则方案数加一，不要忘了只有节点i的情况。速度比较慢，存在复杂度为nlogn的算法，但是要用set或者treap，这对于pascal党太痛苦了，所以上述方法简单实用！

program p2783;
	type
		bian=record
			next,point:longint;
		end;
	var
		f,w:array[1..100000,0..25] of longint;
		d,x,p:array[0..100000] of longint;
		b:array[1..100000] of bian;
		l,r,mid,s,tot,len,n,i,j,k1,k2:longint;
		bo:boolean;
	procedure add(k1,k2:longint);
		begin
			inc(len);
			b[len].next:=p[k1];
			b[len].point:=k2;
			p[k1]:=len;
		end;
	procedure dfs(k1,k2:longint);
		var
			i,j:longint;
		begin
			f[k1,0]:=k2; d[k1]:=d[k2]+1;
			w[k1,0]:=x[k2];
			i:=p[k1];
			while i<>0 do begin
				j:=b[i].point;
				dfs(j,k1);
				i:=b[i].next;
			end;
		end;
	function go_up(k1,k2:longint):longint;
		var
			i,j,k:longint;
		begin
			for k:=1 to 30 do
				if 1 shl k>k2 then break;
			dec(k); j:=0;
			for i:=k downto 0 do
				if k2 and (1 shl i)>0 then begin
					j:=j+w[k1,i];
					k1:=f[k1,i];
				end;
			exit(j);
		end;
	begin
		readln(n,s);
		fillchar(p,sizeof(p),0);
		fillchar(b,sizeof(b),0);
		for i:=1 to n do
			read(x[i]);
		x[0]:=0;
		len:=0;
		for j:=1 to n-1 do begin
			readln(k1,k2);
			add(k1,k2);
		end;
		fillchar(d,sizeof(d),0);
		fillchar(f,sizeof(f),0);
		dfs(1,0);
		bo:=true; j:=0;
		while bo=true do begin
			inc(j);
			bo:=false;
			for i:=1 to n do begin
				if 1 shl j>=d[i] then continue;
				f[i,j]:=f[f[i,j-1],j-1];
				bo:=true;
				w[i,j]:=w[f[i,j-1],j-1]+w[i,j-1];
			end;
		end;
		tot:=0;
		for i:=1 to n do begin
			if x[i]=s then begin
				inc(tot);
				continue;
			end;
			l:=1; r:=d[i]; 
			while l<r do begin
				mid:=(l+r) div 2;
				k1:=go_up(i,mid)+x[i];
				if k1>s then r:=mid
					else if k1<s then l:=mid+1
						else begin
							inc(tot);
							break;
						end;
			end;
		end;
		writeln(tot);
	end.