提出 #26574539

---

ソースコード 拡げる

def yes!; puts'Yes'; exit end

N,X = gets.split.map(&:to_i)
E = Array.new(N){[]}
$<.each{|ln|
	a,b,c = ln.split.map(&:to_i)
	a -= 1; b -= 1
	E[a]<<[b,c]
	E[b]<<[a,c]
}

D = [nil]*N
O = [0]*N
Deg = E.map(&:size)
Q = N.times.select{ Deg[_1]==1 }
while a = Q.pop
	((p,),),bs = E[a].partition{|b,| ! D[b] }
	bs.sort_by!{|b,| D[b].size }
	bx,cx = bs.pop
	dx,ox = bx ? [D[bx],O[bx]+cx] : [{0=>0},0]
	until bs.empty?
		b,c = bs.pop
		d,o = D[b],O[b]+c
		yes! if x = X-o-ox and d.any?{|d,| dx[x-d] }
		d.each{|d,|
			d += o-ox
			dx[d] = d
		}
	end
	dx[-ox] = -ox
	D[a] = dx
	O[a] = ox
	yes! if D[a][X-O[a]]
	Q << p if p && 1==Deg[p] -= 1
end

puts'No'

提出情報

ジャッジ結果