Submission #717927

---

Source Code Expand

M=10**9+7
n=gets.to_i
$edges=Array.new(n){Array.new}
(n-1).times{
	a,b=gets.split.map(&:to_i)
	a-=1
	b-=1
	$edges[a]<<b
	$edges[b]<<a
}

$dp={}
def dfs(node,color,parent)
	return $dp[[node,color]] if $dp[[node,color]]
	ret=1
	if color==:black
		$edges[node].each{|next_node|
			next if next_node==parent
			ret=(ret*dfs(next_node,:white,node))%M
		}
	else
		$edges[node].each{|next_node|
			next if next_node==parent
			ret=(ret*(dfs(next_node,:white,node)+dfs(next_node,:black,node)))%M
		}		
	end
	$dp[[node,color]]=ret
end

puts (dfs(0,:black,-1)+dfs(0,:white,-1))%M

Submission Info

Judge Result