Submission #26833318

---

Source Code Expand

$debug = false
def no!; puts'No'; exit end

N = gets.to_i
E = Array.new(N){[]}
(N-1).times{
	a,b = gets.split.map{_1.to_i-1}
	E[a] << b
	E[b] << a
}
V = [nil]*N
K = gets.to_i.times.map{
	gets.split.map(&:to_i).then{|v,p|
		V[v-=1] = 0,p
		next v,p
	}
}

D = E.map(&:size)
Q = N.times.select{|v| D[v]<2 }
while a = Q.pop
	D[a] -= 1
	break unless p = E[a].find{|b,| 0<D[b] }
	Q << p if 1 == D[p] -= 1
	(d,v),(pd,pv) = V[a],V[p]
	next unless d
	if pd
		dd,dv = d+1+pd,(v-pv).abs
		no! if dd<dv || dd&1!=dv&1
		if dv <= (d+1-pd).abs
			V[p] = d+1,v if d < pd
		else
			d += 1
			if d<pd
				pv -= (pd-d)*(pv<=>v)
				pd = d
			else
				v -= (d-pd)*(v<=>pv)
				d = pd
			end
			V[p] = d-(v-pv).abs/2,(v+pv)/2
		end
#warn [a,V[a],p,V[p]].inspect if (dd,dv = V[a].zip(V[p]).then{[_1.sum+1,_2.inject(:-).abs]}) and dd<dv || 0<(dd-dv)&1
	else
		V[p] = d+1,v
	end
end
warn'!!!' if $debug && K.any?{|v,p| V[v] != [0,p] }

V[a] = V[a].sum
Q << a
while a = Q.pop
	v = V[a]
	E[a].each{|b|
		db,vb = V[b]
		next if db && ! vb
		if db
			V[b] = (vb-v).abs<db+1 ? v-(v<vb ? 1:-1) : v+(v<vb ? 1:-1)
#warn [[a,v],b,V[b],[db,vb]].inspect if V[b] != vb+db && V[b] != vb-db
		else
			V[b] = 0<v ? v-1 : v+1
		end
		Q << b
	}
end

if $debug
	warn'!' if N.times.any?{|a|
		E[a].any?{|b| (V[a]-V[b]).abs != 1 }
	}
	warn'!!' if K.any?{|v,p| V[v] != p }
end

puts'Yes',V

Submission Info

Judge Result