Submission #3015249

---

Source Code Expand

import sys
sys.setrecursionlimit(10**7)
def dfs(granpa,parent):
    for i in L[parent]:
        if i==granpa:
            continue
        dfs(parent,i)
    for i in L[parent]:
        if i==granpa:
            continue
        g[parent]*=f[i]
        g[parent]%=mod
    for i in L[parent]:
        if i==granpa:
            continue
        f[parent]*=g[i]
        f[parent]%=mod
    f[parent]+=g[parent]
    f[parent]%=mod
        
N=int(input())
L=[set() for i in range(N)]
f=[1]*N
g=[1]*N
mod=10**9+7
for i in range(N-1):
    a,b=map(int,input().split())
    L[a-1].add(b-1)
    L[b-1].add(a-1)
dfs(0,0)
print(f[0])

Submission Info

Judge Result