Submission #34647156

---

Source Code Expand

N = gets.to_i
E = Array.new(N+1){[]}
(N-1).times{
	a,b = gets.split.map(&:to_i)
	E[a]<<b
	E[b]<<a
}
K = Array.new(N+1){[]}
U = gets.to_i.times.map{
	u,k = gets.split.map(&:to_i)
	K[u]<<-k
	next u
}
F = lambda{|ds,ans,a,p=a,anc=[]|
	ds[a] = anc.size
	ans[a] = anc.values_at(*K[a])
	anc<<a
	E[a].each{|b|
		F[ds,ans,b,a,anc] if b!=p
	}
	anc.pop
	next ds,ans
}

ds, = F[[nil]*(N+1),[nil]*(N+1),1]
ds,A1 = F[ds,[nil]*(N+1),(1..N).max_by{|r| ds[r] }]
ds,A2 = F[ds,[nil]*(N+1),(1..N).max_by{|r| ds[r] }]

puts U.map{|u|
	a1 = A1[u].shift
	a2 = A2[u].shift
	next a1||a2||-1
}

Submission Info

Judge Result