Submission #761133

---

Source Code Expand

# (1) 頂点どうしの関係性を配列に入力する。隣接点のデータを作成する

n = gets.to_i

@neighbor = []
# 関数f, gの中から参照するので、@をつけてインスタンス変数にして、サブクラスから参照可能にする
$mod  = (10**9 + 7)
n.times do
	@neighbor << []
end

(n-1).times do
	line = gets.split
	i = line[0].to_i
	j = line[1].to_i

	@neighbor[i-1] << j-1
	@neighbor[j-1] << i-1
end

def f(x, p)
	# f(x, p) = 頂点xを根とした部分木に対する独立集合の個数
	# g(x,p) = 上記のうち、頂点xを含まないものの個数
	# pはxの親とする
	# 関数の返り値は[g(x,p), f(x,p)]である
	f_product = 1
	g_product = 1

	for i in @neighbor[x]
		if i == p
			next
		else
			temp = f(i,x)
			f_product *= temp[0]
			g_product *= temp[1]
		end
	end
	
	return [g_product % $mod , (g_product + f_product) % $mod]
end

p f(0,-1)[1]

Submission Info

Judge Result