Submission #18036165

---

Source Code Expand

class Array
	def ^ other
		return self + other - (self&other)
	end
end

N,Q = gets.split.map(&:to_i)

ChildrenOfV = Array.new(N+1){ [] }
ParentOfV = [nil]*(N+1)
ColorOfV = Array.new(N+1){ [] }
EdgeOfV = [nil]*(N+1)
ColorOfEdge = [nil]*(N-1)

Edges = (N-1).times.map{
	a,b = gets.split.map(&:to_i)
	ChildrenOfV[a] << b
	ChildrenOfV[b] << a
	next a,b
}

Colors = Q.times.map{|z|
	u,v,c = gets.split.map(&:to_i)
	ColorOfV[u] << z
	ColorOfV[v] << z
	next c
}
Colors << 0

子を認知する親の行列 = [p=N]
子を認知する親の行列.concat ChildrenOfV[p].each{|c|
	ParentOfV[c] = ChildrenOfV[c].delete p
} while p = 子を認知する親の行列.shift

Edges.each_with_index{|(p,c),i|
	p,c = c,p unless ParentOfV[c] == p
	EdgeOfV[c] = i
}

上方の辺の色を決定する頂点の行列 = *1...N
while p = 上方の辺の色を決定する頂点の行列.shift
	next if ColorOfEdge[EdgeOfV[p]]
	next 上方の辺の色を決定する頂点の行列.push(p) if ChildrenOfV[p].any?{|c| ColorOfEdge[EdgeOfV[c]].nil? }
	begin
		ColorOfV[p] = ChildrenOfV[p].map{|u| ColorOfV[u] }.inject(ColorOfV[p],:^)
		ColorOfEdge[EdgeOfV[p]] = Colors[ColorOfV[p].max||-1]
		p = ParentOfV[p]
	end while p < N && ChildrenOfV[p].all?{|c| ColorOfEdge[EdgeOfV[c]] }
end

puts ColorOfEdge

Submission Info

Judge Result