Submission #53927502

---

Source Code Expand

module UF
	def find a
		self[a]<0 ? a : self[a] = find(self[a])
	end

	def unite a,b
		a = find a
		b = find b
		return if a==b
		a,b = b,a if self[b]<self[a]
		self[a] += self[b]
		self[b] = a
		return true
	end
end

N,Q = gets.split.map(&:to_i)
G = Array.new(11){ [-1]*(N+1) }.each{|g| g.extend UF }
sc = (N-1).times.sum{
	a,b,c = gets.split.map(&:to_i)
	G[c..10].each{|g|
		g.unite a,b
	}
	next c
}
puts Q.times.map{
	u,v,w = gets.split.map(&:to_i)
	if G[w].unite u,v
		sc += w
		sc -= (w+1..10).find{|c| ! G[c].unite u,v }
	end
	next sc
}

Submission Info

Judge Result