Submission #32487113

---

Source Code Expand

class ST
	def initialize a
		@l = (1<<(a.size-1).bit_length)-1
		@a = [nil]*@l
		@a.concat a
		@a.concat [a[-1]]*(@l+1-a.size)
		(@l-1).downto(0){|i|
			@a[i] = @a[i+i+1,2].min
		}
	end

	def [] l,r
		return if r<l
		l,r = @l+l,@l+r
		lm,rm = @a[l],@a[r]
		lm,rm,l,r = [@a[l],lm].min,[@a[r],rm].min,l/2,r/2-1 until r<l
		return [lm,rm].min
	end

	def []= i,v
		i += @l
		@a[i] = v
		@a[i] = @a[i+i+1,2].min while 0<=i = (i-1)/2
		return v
	end
end

(N,_,Q),*ABC,X = $<.map{|ln| ln.split.map(&:to_i) }
E = Array.new(N+1){[]}
ABC.each{|a,b,c|
	E[a]<<[b,c]
	E[b]<<[a,c]
}
X<<10**9
I = (0..Q).sort_by{|i| X[i] }
J = I.map{}
I.each_with_index{|i,j| J[i] = j }
Y = I.map{|i| X[i] }

M = ST.new I
V = [nil]*(N+1)
V[1] = v = 1
W = X.map{[]}
F = lambda{|bcs|
	bcs.each{|b,c|
		W[M[Y.bsearch_index{|x| c<=x },Q]]<<b if ! V[b]
	}
}
F[E[1]]
puts Q.times.map{|i|
	M[J[i]] = Q
	next v += W[i].select{|b|
		V[b] = b if ! V[b]
	}.each{|a| F[E[a]] }.size
}

Submission Info

Judge Result