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: Time Limit Exceeded

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 ** 6)

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: Time Limit Exceeded

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 ** 6)

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: Time Limit Exceeded

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 = [set() for i in range(n + 1)]

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: Time Limit Exceeded

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 = [set() for i in range(n + 1)]

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: Time Limit Exceeded

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: Time Limit Exceeded

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()
    l.append([a, b])
for i in range(n - 1):
    a, b = l[i]
    g[a].add(b)
    g[b].add(a)


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

print(ans % mod)

Submission status: Time Limit Exceeded

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)

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: Time Limit Exceeded

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: Time Limit Exceeded

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 = 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: Time Limit Exceeded

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 = 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
root = 1
ans = dp(root, -1, 0) + dp(root, -1, 1)

print(ans % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)
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]
        dp[i][0]%=MOD
        dp[i][1]%=MOD
    return 0
f(0)
print((dp[0][0]+dp[0][1])%MOD)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**9)
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: Time Limit Exceeded

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

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

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

stack = [-1,0]

while len(stack) > 1:
  v = stack[-1]
  parent = stack[-2]
  black = 1
  white = 1
  for child in G[v]:
    if child == parent:
      continue
    if dp_black[child] == -1:
      stack.append(child)
      break
    black *= dp_white[child]
    black %= MOD
    white *= (dp_black[child] + dp_white[child])
    white %= MOD
  else:
    dp_black[v] = black
    dp_white[v] = white
    stack.pop()
    
print((dp_black[0] + dp_white[0]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
al = [[] for i in range(N+1)]

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

b = [0 for i in range(N + 1)]
w = [0 for i in range(N + 1)]
seen = [0 for i in range(N + 1)]

@functools.lru_cache(None)
def bfs(u):
    seen[u] = 1

    b[u] = 1
    w[u] = 1

    for v in al[u]:
        if seen[v] == 0:
            seen[v] = 1
            bfs(v)
            b[u] = (b[u] * w[v]) % mod
            w[u] = (w[u] * ((b[v] + w[v]) % mod)) % mod
            flag = 1

bfs(1)

print((b[1] + w[1]) % mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
al = [[] for i in range(N+1)]

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

b = [0 for i in range(N + 1)]
w = [0 for i in range(N + 1)]
seen = [0 for i in range(N + 1)]

def mul_list(a):
    ans = 1
    for aa in a:
        ans = (ans * aa) % mod
    return ans

@functools.lru_cache(None)
def bfs(u):
    seen[u] = 1
    tmp1 = []
    tmp2 = []

    flag = 0
    for w in al[u]:
        if seen[w] == 0:
            seen[w] = 1
            bb, ww = bfs(w)
            tmp1.append(ww)
            tmp2.append(bb + ww)
            flag = 1

    if flag == 0:
        return 1, 1

    ans_b = mul_list(tmp1)
    ans_w = mul_list(tmp2)

    return ans_b, ans_w

p, q = bfs(1)

print((p + q) % mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

N = int(input())
al = [[] for i in range(N+1)]

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

b = [0 for i in range(N + 1)]
w = [0 for i in range(N + 1)]
seen = [0 for i in range(N + 1)]

@functools.lru_cache(None)
def bfs(u):
    seen[u] = 1
    tmp1 = []
    tmp2 = []

    flag = 0
    for w in al[u]:
        if seen[w] == 0:
            seen[w] = 1
            bb, ww = bfs(w)
            tmp1.append(ww)
            tmp2.append(bb + ww)
            flag = 1

    if flag == 0:
        return 1, 1

    ans_b = reduce(mul, tmp1) % mod
    ans_w = reduce(mul, tmp2) % mod

    return ans_b, ans_w

p, q = bfs(1)

print((p + q) % mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    x, y = LI()
    G[x - 1] += [y - 1]
    G[y - 1] += [x - 1]


par = [-1] * n
def f(u):
    b, w = 1, 1
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        cb, cw = f(v)
        b = b * cw % mod
        w = w * (cw + cb)
    return b, w

bb, ww = f(0)
print((bb + ww) % mod)

Submission status: Time Limit Exceeded

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===

def main():
    n = ni()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = ns()
        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: Time Limit Exceeded

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 ** 9)
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===

def main():
    n = ni()
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = ns()
        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:
                continue
            dfs(chld, vi)

            # 親が白なら子は白でも黒でもいい
            dp[vi][0] *= dp[chld][0] + dp[chld][1]
            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: Time Limit Exceeded

Solution code:

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


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

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

    N = int(inp())
    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)]
    vistied = [False] * N

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


if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)

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: Time Limit Exceeded

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

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]) % MOD)

Submission status: Time Limit Exceeded

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):
        nonlocal ret_white, ret_total
        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()