Problem:


Score : 100 points

Problem Statement

There is a tree with N vertices, numbered 1, 2, \ldots, N.
For each i (1 \leq i \leq N - 1), the i-th edge connects Vertex x_i and y_i.

Taro has decided to paint each vertex in white or black.
Here, it is not allowed to paint two adjacent vertices both in black.

Find the number of ways in which the vertices can be painted, modulo 10^9 + 7.

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq x_i, y_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
x_2 y_2
:
x_{N - 1} y_{N - 1}

Output

Print the number of ways in which the vertices can be painted, modulo 10^9 + 7.

Sample Input 1

3
1 2
2 3

Sample Output 1

5

There are five ways to paint the vertices, as follows:

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

9

There are nine ways to paint the vertices, as follows:

Sample Input 3

1

Sample Output 3

2

Sample Input 4

10
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7

Sample Output 4

157



Sample input:
3
1 2
2 3


Sample output:
5

Submission status: Accepted

Solution code:
from collections import deque
n = int(input())
mod = 10**9+7
g = [[] for i in range(n)]
g2 = [[] for i in range(n)]
for i in range(n-1):
  x,y = list(map(int,input().split()))
  g[x-1].append(y-1)
  g[y-1].append(x-1)
dp = [[0]* 2 for i in range(n)]
hukasa = [float("inf")]*n
hukasa[0] = 0
def dfs(x,y):
  for i in g[x]:
    if hukasa[i] > y+1:
      hukasa[i] = y+1
      que.append([i,y+1])
      g2[x].append(i)
que = deque([])
que.append([0,0])
while que:
  x,y = que.popleft()
  dfs(x,y)
for i in range(n):
  hukasa[i] = [hukasa[i],i]
hukasa.sort(key = lambda x:-x[0])
for i,j in hukasa:
  if len(g2[j]) == 0:
    dp[j][0] = dp[j][1] = 1
    continue
  tmp = 1
  tmp2 = 1
  for k in g2[j]:
    tmp *= dp[k][0]
    tmp2 *= (dp[k][0]+dp[k][1])
    tmp %= mod
    tmp2 %= mod
  dp[j][1] = tmp
  dp[j][0] = tmp2
print((dp[0][0]+dp[0][1])%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    table[v-1].append(w-1)
mod=10**9+7
f=[-1]*N
g=[-1]*N
def ser(par,son):
    if f[son]!=-1 and g[son]!=-1:
        return f[son],g[son]
    s=1
    t=1
    for grason in table[son]:
        if grason==par:
            continue
        x,y=ser(son,grason)
        s*=x
        s%=mod
        t*=(x+y)
        t%=mod
    f[son],g[son]=t,s
    return t,s
z=1
w=1
for i in table[0]:
    ser(0,i)
    z*=f[i]
    z%=mod
    w*=(f[i]+g[i])
    w%=mod
print((z+w)%mod)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 10 ** 9 + 7
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
 



sys.setrecursionlimit(10 ** 5 + 10)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = [[] for i in range(n + 1)]

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].append(b)
    g[b].append(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

Submission status: Runtime Error

Solution code:

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
#from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
# input = sys.stdin.readline



M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in st()]
 



# sys.setrecursionlimit(10 ** 5 + 10)

g = 0
d = {}
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    if (i, par, black) in d:return d[(i, par, black)]
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    d[(i, par, black)] = ans
    return ans



n = val()
g = defaultdict(set)

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

Submission status: Runtime Error

Solution code:

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
import sys
# input = sys.stdin.readline



M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in st()]
 



# sys.setrecursionlimit(10 ** 5 + 10)

g = 0
d = {}
def dp(i, par = -1, black = 0):
    global g
    ans = 1
    if (i, par, black) in d:return d[(i, par, black)]
    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    d[(i, par, black)] = ans
    return ans



n = val()
g = defaultdict(set)

l = []
for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


root = 1    
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

Submission status: Runtime Error

Solution code:

from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key,lru_cache
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
# import sys
# input = sys.stdin.readline
 
M = mod = 10**9 + 7 
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip().split()]
def st():return str(input().rstrip())[2:-1]
def val():return int(input().rstrip())
def li2():return [str(i)[2:-1] for i in input().rstrip().split()]
def li3():return [int(i) for i in st()]
 



sys.setrecursionlimit(10 ** 5 + 10)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1

    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = defaultdict(set)

for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)


root = 1
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



sys.setrecursionlimit(10 ** 5 + 10)

g = 0
@lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1

    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = defaultdict(set)

for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)

root = 1
for j in g:
    if len(g[j]) == 1:
        root = j
        break

ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop,heapify
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

from itertools import accumulate
from functools import lru_cache

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)
 
def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]



g = 0
# @lru_cache(None)
def dp(i, par = -1, black = 0):
    global g
    ans = 1

    nokids = 1
    if black:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ans * dp(j, i, 0) % mod
    else:
        for j in g[i]:
            if j != par:
                nokids = 0
                ans = ( ans * (dp(j, i, 0) + dp(j, i, 1)) ) % mod

    if nokids:ans = 1
    return ans



n = val()
g = defaultdict(set)

for _ in range(n - 1):
    a, b = li()
    g[a].add(b)
    g[b].add(a)

root = 1
for j in g:
    if len(g[j]) == 1:
        root = j
        break

ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

Submission status: Runtime Error

Solution code:
dp = {}
mod = 10**9+7
def getAns(graph, root, col, par):

    if len(graph[root]) == 0 or (len(graph[root]) == 1 and graph[root][0] == par):
        return 1

    if (root, col) in dp:
        return dp[(root, col)]
    ans = 1 
    for i in graph[root]:
        if i != par:
            if col == 1:
                ans *= (getAns(graph, i, 0, root))%mod
            else:
                ans *= (getAns(graph, i, 1, root) + getAns(graph, i, 0, root))%mod

            ans = ans%mod
    dp[(root, col)] = ans%mod
    return ans

n = int(input())
graph = {i: [] for i in range(1, n+1)}
start = None
for i in range(n-1):
    v, u = map(int, input().strip().split())
    start = v
    graph[v].append(u)
    graph[u].append(v)

print((getAns(graph, start, 0, -1) + getAns(graph, start, 1, -1))%mod)

Submission status: Runtime Error

Solution code:
dp = {}
mod = 10**9+7
def getAns(graph, root, col, par):

    if len(graph[root]) == 0 or (len(graph[root]) == 1 and graph[root][0] == par):
        return 1

    if (root, col) in dp:
        return dp[(root, col)]
    ans = 1 
    for i in graph[root]:
        if i != par:
            if col == 1:
                ans *= (getAns(graph, i, 0, root))%mod
            else:
                ans *= (getAns(graph, i, 1, root) + getAns(graph, i, 0, root))%mod

            ans = ans%mod
    dp[(root, col)] = ans%mod
    return ans

n = int(input())
graph = {i: [] for i in range(1, n+1)}
for i in range(n-1):
    v, u = map(int, input().strip().split())
    graph[v].append(u)
    graph[u].append(v)

print(getAns(graph, 1, 0, -1) + getAns(graph, 1, 1, -1))

Submission status: Runtime Error

Solution code:
dp = {}
def getAns(graph, root, col, par):

    if (len(graph[root]) == 1 and graph[root][0] == par) or len(graph[root]) == 0:
        return 1

    if (root, col) in dp:
        return dp[(root, col)]
    ans = 1 
    for i in graph[root]:
        if i != par:
            if col == 1:
                ans *= getAns(graph, i, 0, root)
            else:
                ans *= getAns(graph, i, 1, root) + getAns(graph, i, 0, root)
    
    dp[(root, col)] = ans
    return ans

n = int(input())
graph = {i: [] for i in range(1, n+1)}
for i in range(n-1):
    v, u = map(int, input().strip().split())
    graph[v].append(u)
    graph[u].append(v)

print(getAns(graph, 1, 0, -1) + getAns(graph, 1, 1, -1))

Submission status: Runtime Error

Solution code:
from collections import deque
n=int(input())
g=[[] for i in range(n)]
for i in range(n-1):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a].append(b)
    g[b].append(a)
q=deque([0])
v=[0]*n
v[0]=1
gp=[[] for i in range(n)]
while q:
    p=q.popleft()
    for i in g[p]:
        if v[i]==0:
            v[i]=1
            gp[p].append(i)
            q.append(i)
MOD=10**9+7
flag=[0]*n
dp=[[0,0] for i in range(n)]
def f(i):
    if flag[i]:
        return 0
    flag[i]=1
    dp[i][0]=1
    dp[i][1]=1
    for j in gp[i]:
        f(j)
        dp[i][0]=dp[i][0]*(dp[j][0]+dp[j][1])%MOD
        dp[i][1]=dp[i][1]*dp[j][0]
    return 0
f(0)
print((dp[0][0]+dp[0][1])%MOD)

Submission status: Runtime Error

Solution code:

def countSetBits(n):
    count = 0
    while (n):
        n &= (n - 1)
        count += 1

    return count



N=10**9 + 7
n=int(input())
g=[[] for _ in range(n+5)]
for _ in range(n-1):
    a,b=map(int,input().strip().split(" "))
    g[a-1].append(b-1)
    g[b-1].append(a-1)
dpr=[-1 for _ in range(n+5)]
dpb=[-1 for _ in range(n+5)]

def dfs(v,p):
    if dpr[v]!=-1:
        return
    if len(g[v])==1 and g[v][0]==p:
        dpr[v]=1
        dpb[v]=1
        return
    valr=1
    valb=1
    for c in g[v]:
        if c==p:
            continue
        dfs(c,v)
        valr=(valr*((dpr[c]+dpb[c])%N))%N
        valb=(valb*(dpr[c]))%N
    dpr[v]=valr
    dpb[v]=valb
    return
dfs(0,-1)
print((dpr[0]+dpb[0])%N)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mod = 1e9+7
class Graph:
	def __init__(self,n):
		self.n=n+1
		self.graph=defaultdict(list)
		self.dp=[[0]*2 for i in range(self.n)]

	def addEdge(self,u,v):
		self.graph[u].append(v)
		self.graph[v].append(u)
	
	def dfs(self,node,par):
		self.dp[node][0]=1
		self.dp[node][1]=1

		for i in self.graph[node]:
			if(i==par):
				continue;
			self.dfs(i,node)
			self.dp[node][0]=(self.dp[node][0]*(self.dp[i][0]+self.dp[i][1])%mod)%mod
			self.dp[node][1]=self.dp[node][1]*self.dp[i][0]%mod


n=int(input())
g=Graph(n)
for i in range(n-1):
	u,v=map(int,input().split())
	g.addEdge(u,v);
g.dfs(1,-1)

print(int(g.dp[1][0]+g.dp[1][1] % mod))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mod = 1e9+7
class Graph:
	def __init__(self,n):
		self.n=n+1
		self.graph=defaultdict(list)
		self.dp=[[0]*2 for i in range(self.n)]

	def addEdge(self,u,v):
		self.graph[u].append(v)
		self.graph[v].append(u)
	
	def dfs(self,node,par):
		self.dp[node][0]=1
		self.dp[node][1]=1

		for i in self.graph[node]:
			if(i==par):
				continue;
			self.dfs(i,node)
			self.dp[node][0]=self.dp[node][0]*(self.dp[i][0]+self.dp[i][1])%mod
			self.dp[node][1]=self.dp[node][1]*self.dp[i][0]%mod


n=int(input())
g=Graph(n)
for i in range(n-1):
	u,v=map(int,input().split())
	g.addEdge(u,v);
g.dfs(1,-1)
# for i in range(1,n+1):
# 	print(g.dp[i])
print(int(g.dp[1][0]+g.dp[1][1] % mod))

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mod = 1e9+7
class Graph:
	def __init__(self,n):
		self.n=n+1
		self.graph=defaultdict(list)
		self.dp=[[0]*2 for i in range(self.n)]

	def addEdge(self,u,v):
		self.graph[u].append(v)
		self.graph[v].append(u)
	
	def dfs(self,node,par):
		self.dp[node][0]=1
		self.dp[node][1]=1

		for i in self.graph[node]:
			if(i==par):
				continue;
			self.dfs(i,node)
			self.dp[node][0]=self.dp[node][0]*(self.dp[i][0]+self.dp[i][1])%mod
			self.dp[node][1]=self.dp[node][1]*self.dp[i][0]%mod


n=int(input())
g=Graph(n)
for i in range(n-1):
	u,v=map(int,input().split())
	g.addEdge(u,v);
g.dfs(1,-1)
for i in range(1,n+1):
	print(g.dp[i])
print(int(g.dp[1][0]+g.dp[1][1] % mod))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

MOD = 10**9 + 7
N = int(input())
paths = {i:[] for i in range(N+1)}
for _ in range(N-1):
    x, y = map(int, input().split())
    paths[x].append(y)
    paths[y].append(x)

dpt = [[[-1] * 2 for i in range(N+1)] for j in range(N+1)]

def count_cc(prev, node, color):
    if dpt[prev][node][color] != -1:
        return dpt[prev][node][color]
    if paths[node] == [prev]:
        dpt[prev][node][color] = 1
        return 1
    result = 1
    if color == 0:
        for nxt in paths[node]:
            if nxt == prev:
                continue
            result *= (count_cc(node, nxt, 0) + count_cc(node, nxt, 1))
            result %= MOD
    else:
        for nxt in paths[node]:
            if nxt == prev:
                continue
            result *= count_cc(node, nxt, 0)
            result %= MOD

    dpt[prev][node][color] = result
    return result

print(count_cc(0, 2, 0) + count_cc(0, 2, 1))

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
N = int(input())
paths = {i:[] for i in range(N+1)}
for _ in range(N-1):
    x, y = map(int, input().split())
    paths[x].append(y)
    paths[y].append(x)

dpt = [[[-1] * 2 for i in range(N+1)] for j in range(N+1)]

def count_cc(prev, node, color):
    if dpt[prev][node][color] != -1:
        return dpt[prev][node][color]
    if paths[node] == [prev]:
        dpt[prev][node][color] = 1
        return 1
    result = 1
    if color == 0:
        for nxt in paths[node]:
            if nxt == prev:
                continue
            result *= (count_cc(node, nxt, 0) + count_cc(node, nxt, 1))
            result %= MOD
    else:
        for nxt in paths[node]:
            if nxt == prev:
                continue
            result *= count_cc(node, nxt, 0)
            result %= MOD

    dpt[prev][node][color] = result
    return result

print(count_cc(0, 2, 0) + count_cc(0, 2, 1))

Submission status: Runtime Error

Solution code:
# 末端の頂点は白1通り、黒1通り
# それ以外の頂点は、各子どもの頂点を元に、白:子の全ての場合分けの積、黒:子が全て白の場合分けの積
# で更新していく

N = int(input())
G = [[] for i in range(N)]
MOD = 10 ** 9 + 7

for i in range(N - 1):
  x,y = map(int,input().split())
  G[x - 1].append(y - 1)
  G[y - 1].append(x - 1)
  
dp_black = [-1] * N
dp_white = [-1] * N

# 頂点vの(黒,白)の場合の数を求める
def search(v,parent):
  if dp_black[v] != -1:
    return (dp_black[v],dp_white[v])
  black = 1
  white = 1
  for child in G[v]:
    if child == parent:
      continue
    b,w = search(child, v)
    black *= w
    black %= MOD
    white *= (b + w)
    white %= MOD
  dp_black[v] = black
  dp_white[v] = white
  return (black, white)

print(sum(search(0, -1)) % MOD)

Submission status: Runtime Error

Solution code:
n = int(input())
g = [[] for _ in range(n)]
mod = 10**9+7
for _ in range(n-1):
    x,y = map(int,input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)

def dfs(x,par):
    w,b = 1,1
    for y in g[x]:
        if y == par:continue
        cw,cb = dfs(y,x)
        w*=cw+cb
        b*=cw
    w%=mod
    b%=mod
    return w,b
print(sum(dfs(0,None))%mod)

Submission status: Runtime Error

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 7)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

inp = sys.stdin.buffer.readline

def main():
    n = ni()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = map(int, inp().split())
        x -= 1
        y -= 1
        e[x].append(y)
        e[y].append(x)

    # dp[i][0]:i番目のノードが白のときの組み合わせの数
    # dp[i][1]:i番目のノードが黒のときの組み合わせの数
    dp = [[1, 1] for _ in range(n)]
    visited = [False for _ in range(n)]

    def dfs(vi, prnt):
        # if visited[vi]:
        #     return
        visited[vi] = True

        for chld in e[vi]:
            if chld == prnt or visited[chld]:
                continue
            dfs(chld, vi)

            # 親が白なら子は白でも黒でもいい
            dp[vi][0] *= (dp[chld][0] + dp[chld][1]) % MOD
            dp[vi][0] %= MOD
            # 親が黒田と子は白じゃないとダメ
            dp[vi][1] *= dp[chld][0]
            dp[vi][1] %= MOD

    dfs(0, -1)
    print((dp[0][0] + dp[0][1]) % MOD)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
mod=10**9+7
def dfs(v):
  if checked[v]==1:
    return
  checked[v]=1
  dp[v][0]=1
  dp[v][1]=1
  for u in g[v]:
    if checked[u]==0:
      dfs(u)
      dp[v][0]*=dp[u][0]+dp[u][1]
      dp[v][0]%=mod
      dp[v][1]*=dp[u][0]
      dp[v][1]%=mod      

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
dp=[[0,0] for _ in range(n+1)]
checked=[0]*(n+1)
dfs(1)
print((dp[1][0]+dp[1][1])%mod)

Submission status: Runtime Error

Solution code:
mod=10**9+7
def dfs(v):
  if checked[v]==1:
    return
  checked[v]=1
  dp[v][0]=1
  dp[v][1]=1
  for u in g[v]:
    if checked[u]==0:
      dfs(u)
      dp[v][0]*=dp[u][0]+dp[u][1]
      dp[v][0]%=mod
      dp[v][1]*=dp[u][0]
      dp[v][1]%=mod      

n=int(input())
g=[[] for _ in range(n+1)]
for _ in range(n-1):
  a,b=map(int,input().split())
  g[a].append(b)
  g[b].append(a)
dp=[[0,0] for _ in range(n+1)]
checked=[0]*(n+1)
dfs(1)
print(dp[1][0]+dp[1][1])

Submission status: Runtime Error

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
read = sys.stdin.buffer.read 
inp = sys.stdin.buffer.readline


def resolve():
    MOD = 10 ** 9 + 7

    # 0: white, 1: black
    def dfs(v, parent):
        dp[v][0] = 1
        dp[v][1] = 1
        for to in G[v]:
            if to == parent:
                continue
            dfs(to, v)
            # 親が白の時は子は白黒どっちでも良い
            # 親が黒の時は子は白のみ
            dp[v][0] = (dp[v][0] * (dp[to][0] + dp[to][1])) % MOD
            dp[v][1] = (dp[v][1] * dp[to][0]) % MOD

    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        G[x].append(y)
        G[y].append(x)
    dp = [[0] * 2 for _ in range(N + 1)]

    dfs(0, -1)
    ans = dp[0][0] + dp[0][1]
    print(ans % MOD)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:

def resolve():
    MOD = 10 ** 9 + 7

    # 0: white, 1: black
    def dfs(v, parent):
        dp[v][0] = 1
        dp[v][1] = 1
        for to in G[v]:
            if to == parent:
                continue
            dfs(to, v)
            # 親が白の時は子は白黒どっちでも良い
            # 親が黒の時は子は白のみ
            dp[v][0] = (dp[v][0] * (dp[to][0] + dp[to][1])) % MOD
            dp[v][1] = (dp[v][1] * dp[to][0]) % MOD

    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N - 1):
        x, y = map(lambda x: int(x) - 1, input().split())
        G[x].append(y)
        G[y].append(x)
    dp = [[0] * 2 for _ in range(N + 1)]

    dfs(0, -1)
    ans = dp[0][0] + dp[0][1]
    print(ans % MOD)


if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
def dfs(v, pv):
    dp[v][0] = dp[v][1] = 1
    for nv in edge[v]:
        if nv == pv: continue
        dfs(nv, v)
        dp[v][0] *= dp[nv][0] + dp[nv][1]
        dp[v][0] %= MOD
        dp[v][1] *= dp[nv][0]
        dp[v][1] %= MOD

N = int(input())
edge = [[] for _ in range(N)]

for i in range(N-1):
    x, y = map(lambda x:int(x)-1, input().split())
    edge[x].append(y)
    edge[y].append(x)

dp = [[0] * 2 for _ in range(10**5+10)]
dfs(0,-1)

print(dp[0][1] + dp[0][0])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

from collections import defaultdict
#from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, edges):
    ret_white = 0
    ret_total = 0

    def visit(parent, self):
        if parent != 0 and len(edges[self]) == 1:
            # self is leaf
            ret_white = 1
            ret_total = 2
            return

        black = 1
        white = 1
        for child in edges[self]:
            if child == parent:
                continue
            visit(self, child)
            black *= ret_white
            black %= MOD
            white *= ret_total
            white %= MOD
        ret_white = white
        ret_total = white + black
        return

    visit(0, 1)
    return ret_total % MOD


def main():
    # parse input
    N = int(input())
    edges = defaultdict(list)
    for i in range(N - 1):
        x, y = map(int, input().split())
        edges[x].append(y)
        edges[y].append(x)
    print(solve(N, edges))


# tests
T1 = """
3
1 2
2 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5
    """


T2 = """
4
1 2
1 3
1 4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    9
    """


T3 = """
1
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    2
    """


T4 = """
10
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    157
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Runtime Error

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
ns = [[] for _ in range(n)]
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)

M = 10**9+7
def sub(u, p):
    v1 = 1 # 白
    v2 = 1 # 黒
    for v in ns[u]:
        if v==p:
            continue
        w1, w2 = sub(v, u)
        v1 *= (w1+w2)
        v2 *= w1
        v1 %= M
        v2 %= M
    return v1, v2
sub(0, -1)
print((d1[0]+d2[0])%M)