提出 #32486333

---

ソースコード 拡げる

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.each_with_index.to_h

M = ST.new I
V = {1=>1}
W = X.map{{}}
F = lambda{|bcs|
	bcs.each{|b,c|
		W[M[I.bsearch_index{|i| c<=X[i] },Q]][b] = b if ! V[b]
	}
}
F[E[1]]
puts Q.times.map{|i|
	M[J[i]] = Q
	W[i].keys.select{|b|
		V[b] = b if ! V[b]
	}.each{|a| F[E[a]] }
	next V.size
}

提出情報

ジャッジ結果