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:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)
#    print(Order)
    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="#":
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="#":
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j]*P[i]
            dp[i+1][j] += dp[i][j]*(1-P[i])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

def examJ():
    N = I()
    A = LI()
    dp = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
    S = Counter(A)
    print(S)
    dp[S[1]][S[2]][S[3]] = 0
    que = deque()
    que.append((S[1],S[2],S[3]))
    used = defaultdict(set)
    while(que):
        n1,n2,n3 = que.popleft()
        if used[(n1,n2,n3)]:
            continue
        used[(n1,n2,n3)] = True
        now = n1+n2+n3
        if n1>0:
            dp[n1-1][n2][n3] += dp[n1][n2][n3] + N/now * n1/now
            que.append((n1-1, n2, n3))
        if n2>0:
            dp[n1+1][n2-1][n3] += dp[n1][n2][n3] + N/now * n2/now
            que.append((n1+1,n2-1,n3))
        if n3>0:
            dp[n1][n2+1][n3-1] += dp[n1][n2][n3] + N/now * n3/now
            que.append((n1,n2+1,n3-1))
#    print(dp)
    ans = dp[0][0][0]
    print(ans)
    return

def examK():
    N, K = LI()
    A = LI()
    dp = [-1]*(K+1)
    for i in range(1,K+1):
        flag = False
        for a in A:
            if a>i:
                break
            if dp[i-a]==-1:
                flag = True
                break
        if flag:
            dp[i] = 1
#    print(dp)
    ans = dp[K]
    if ans==1:
        print("First")
    else:
        print("Second")
    return

def examM():
    N, K = LI()
    A = LI()
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        cum = [0]*(K+1)
        cum[0] = dp[i][0]
        for c in range(K):
            cum[c+1] = cum[c] + dp[i][c+1]
        for j in range(K+1):
            if j<=A[i]:
                dp[i+1][j] = cum[j]
            else:
                dp[i+1][j] = cum[j] - cum[j-A[i]-1]
            dp[i+1][j] %=mod
#    print(dp)
    ans = dp[N][K]%mod
    print(ans)
    return

def examP():
    def dfs_dp(n,s,fords,visited):
        W = 1; B = 1
        visited[s] = True
        for v in fords[s]:
            if visited[v]:
                continue
            cur = dfs_dp(n, v, fords,visited)
            W *= sum(cur)
            B *= cur[0]
#        print(s,W,B)
        W %= mod
        B %= mod
        return (W,B)
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x,y = LI()
        x -=1; y -=1
        V[x].append(y)
        V[y].append(x)
    visited = [False]*N
    ans = dfs_dp(N,0,V,visited)
    print(sum(ans)%mod)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LFI(): return list(map(float,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examP()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9+7
n = int(input())
g = [[] for _ in range(n)]

for _ in range(n-1):
    x, y = map(int, input().split())
    g[x-1].append(y-1)
    g[y-1].append(x-1)

white = [0 for _ in range(n)]
black = [0 for _ in range(n)]


def dfs(v):
    tmp_w = 1
    tmp_b = 1
    if len(g[v]) == 0:
        white[v] = 1
        black[v] = 1
        return None
    for w in g[v]:
        g[w].remove(v)
        dfs(w)
        tmp_w *= white[w]+black[w]
        tmp_b *= white[w]
        tmp_w %= mod
        tmp_b %= mod
    white[v] = tmp_w
    black[v] = tmp_b
    return None


dfs(0)

print((white[0]+black[0]) % mod)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, f, t, w=1):
        self.E[f].append((t, w))
        self.E[t].append((f, w))


def solve(N: int, x: "List[int]", y: "List[int]"):

    g = Graph(N)
    for xx, yy in zip(x, y):
        g.add_edge(xx-1, yy-1)

    white = [-1]*N
    black = [-1]*N

    def rec(node, pre):
        if white[node] > 0:
            return white[node], black[node]

        # nodeを黒と塗る場合
        bbb = 1
        www = 1
        for t, _ in g.E[node]:
            if t != pre:
                w, b = rec(t, node)
                bbb *= w
                bbb %= MOD
                www *= (w+b) % MOD
                www %= MOD
        black[node] = bbb % MOD
        white[node] = www % MOD
        return white[node], black[node]

    w, b = rec(0, -1)
    print((w+b) % MOD)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    x = [int()] * (N - 1)  # type: "List[int]"
    y = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2 * 10**5)
mod = 10 ** 9 + 7


def rec(v, p, color, graph, memo):
    if memo[v][color] != -1:
        return memo[v][color]
    ret = 1
    for c in graph[v]:
        if c == p:
            continue
        if color == 0:
            ret *= rec(c, v, 0, graph, memo) + rec(c, v, 1, graph, memo)
        else:
            ret *= rec(c, v, 0, graph, memo)
        ret %= mod
    memo[v][color] = ret
    return ret


def main():
    N = int(input())
    graph = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        x, y = x-1, y-1
        graph[x].append(y)
        graph[y].append(x)
    memo = [[-1, -1] for _ in range(N)]
    print((rec(0, -1, 0, graph, memo) + rec(0, -1, 1, graph, memo)) % mod)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from functools import lru_cache
import sys
sys.setrecursionlimit(10**6)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

@lru_cache(maxsize=None)
def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from functools import lru_cache
import sys
sys.setrecursionlimit(10**5)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

@lru_cache(maxsize=None)
def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**5)

N = int(input())
E = [[] for _ in range(N)]
for _ in range(N-1):
    x,y = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
    
parents = [-1]*N
q = deque()
q.append(0)
while q:
    t = q.popleft()
    for i in E[t]:
        if i == parents[t]:
            continue
        q.append(i)
        parents[i] = t
        
mod = 10**9+7
dp = [[1]*2 for _ in range(N)]
flag = [0]*N

def f(v, j):
    if flag[v]:
        return dp[v][j]
    flag[v] = 1
    for i in E[v]:
        if i == parents[v]:
            continue
        dp[v][0] *= (f(i, 0) + f(i, 1))
        dp[v][1] *= f(i, 0)
        dp[v][0] %= mod
        dp[v][1] %= mod
    return dp[v][j]

print((f(0, 0)+f(0, 1))%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline


n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
MOD = 10**9 + 7

tree = [[] for i in range(n)]
for i in range(n-1):
    x, y = info[i]
    x -= 1
    y -= 1
    tree[x].append(y)
    tree[y].append(x)

def solve(pos):
    b = 1
    w = 1
    flag = False
    for next_pos in tree[pos]:
        if not visited[next_pos]:
            visited[next_pos] = True
            flag = True
            tmp_b, tmp_w = solve(next_pos)
            w *= (tmp_b + tmp_w)
            b *= tmp_w
            w %= MOD
            b %= MOD
    if not flag:
        black[pos] = 1
        white[pos] = 1
        return (black[pos], white[pos])
    else:
        black[pos] = b
        white[pos] = w
        return (black[pos], white[pos])

black = [0]*n
white = [0]*n
visited = [False]*n
visited[0] = True
print(sum(solve(0)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if elem == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        numbers = list(map(int, input().split(" ")))
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)

Submission status: Time Limit Exceeded

Solution code:
modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if elem == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    #input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        numbers = list(map(int, input().split(" ")))
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)

Submission status: Time Limit Exceeded

Solution code:
modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)


muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if x == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    input = sys.stdin.readline
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        # x, y = map(int, input().split())
        numbers = list(map(int, input().split(" ")))
        #print(numbers)
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)

Submission status: Time Limit Exceeded

Solution code:
modulo = 1000000007

import sys
sys.setrecursionlimit(100000009)

muchii = []


def recursie(x, y):
    alb = 1
    negru = 1
    for elem in muchii[x]:
        if x == y:
            continue
        result_1, result_2 = recursie(elem, x)
        alb = (alb * (result_1 + result_2)) % modulo
        negru = (negru * result_1) % modulo
    return alb, negru
    

if __name__ == "__main__":
    
    n = int(input())
    for i in range(n):
        muchii.append([])
        
    for i in range(n-1):
        numbers = list(map(int, input().split()))
        
        x = numbers[0]
        y = numbers[1]
        
        muchii[x-1].append(y-1)
        muchii[y-1].append(x-1)
        
    result_1, result_2 = recursie(0, None)
    
    result = (result_1 + result_2) % modulo
    
    print(result)

Submission status: Time Limit Exceeded

Solution code:

from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
m=10**9+7

def len_max(mat):
    for i in range(len(mat)):
        if len(mat[i])>1:
            return i

n = int(input())
adj_mat =[[] for i in range(n)]



for i in range(n-1):
    a, b = [int(x) for x in input().strip().split()]
    adj_mat[a-1].append(b-1)
    adj_mat[b-1].append(a-1)

root = len_max(adj_mat) or 0


def cal(parent, node, col):

    nei = adj_mat[node]
    if len(nei)==1:
        if col=='w':
            return 2
        else:
            return 1 
    
    else:
        
        if col=='w':
            sb=1
            sw=1
            for k in nei:
                if k==parent:
                    continue
                sw*=cal(node, k, 'w')%m
                sb*=cal(node, k, 'b')%m
            return (sb+sw)%m

        else:
            sw=1
            for k in nei:
                if k==parent:
                    continue
                sw*=cal(node, k, 'w')%m
            return sw


ans = cal(None,root,'w')
if n==0:
    print(0)
elif n==1:
    print(2)
elif n==2:
    print(3)
else:
    print(ans%m)

Submission status: Time Limit Exceeded

Solution code:

from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)
m=10**9+7

def len_max(mat):
    for i in range(len(mat)):
        if len(mat[i])>1:
            return i

n = int(input())
adj_mat =[[] for i in range(n)]



for i in range(n-1):
    a, b = [int(x) for x in input().strip().split()]
    adj_mat[a-1].append(b-1)
    adj_mat[b-1].append(a-1)

root = len_max(adj_mat) or 0


@lru_cache(None)
def cal(parent, node, col):

    nei = adj_mat[node]
    if len(nei)==1:
        if col=='w':
            return 2
        else:
            return 1 
    
    else:
        
        if col=='w':
            sb=1
            sw=1
            for k in nei:
                if k==parent:
                    continue
                sw*=cal(node, k, 'w')%m
                sb*=cal(node, k, 'b')%m
            return (sb+sw)%m

        else:
            sw=1
            for k in nei:
                if k==parent:
                    continue
                sw*=cal(node, k, 'w')%m
            return sw


ans = cal(None,root,'w')
if n==0:
    print(0)
elif n==1:
    print(2)
elif n==2:
    print(3)
else:
    print(ans%m)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
edges = [[] for i in range(N)]
MOD = int(pow(10, 9) + 7)

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

# dp[i][j] - no of ways of painting tree rooted at i, with parent coloured j
dp = [[-1, -1] for i in range(N)]
def recurse(vertex, parent, parentColour):
    if dp[vertex][parentColour] != -1:
        return dp[vertex][parentColour]

    bways = 1
    wways = 1
    
    for n in edges[vertex]:
        if n == parent: continue
        bways *= recurse(n, vertex, False)
        if not parentColour:
            wways *= recurse(n, vertex, True)

    ways = bways if parentColour else bways + wways
    ways %= MOD
    dp[vertex][parentColour] = ways
    return ways

recurse(0, None, False)

print(dp[0][False])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

N = int(input())
edges = [[] for i in range(N)]
MOD = int(pow(10, 9) + 7)

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

# dp[i][j] - no of ways of painting tree rooted at i, with parent coloured j
dp = [[-1, -1] for i in range(N)]
def recurse(vertex, parent, parentColour):
    if dp[vertex][parentColour] != -1:
        return dp[vertex][parentColour]

    bways = 1
    wways = 1
    
    for n in edges[vertex]:
        if n == parent: continue
        bways *= recurse(n, vertex, False)
        wways *= recurse(n, vertex, True)

    ways = bways if parentColour else bways + wways
    ways %= MOD
    dp[vertex][parentColour] = ways
    return ways

recurse(0, None, False)

print(dp[0][False])

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)
    from collections import deque
    mod = 10**9+7
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    que = deque([0])
    children = [[] for _ in range(N)]
    while que:
        v = que.pop()
        for nv in G[v]:
            if children[nv]:
                continue
            children[v].append(nv)
            que.append(nv)   
    memo = [[-1]*2 for _ in range(N)]
    def dp(i, c):
        if memo[i][c] >=0:
            return memo[i][c]
        if c == 1:
            res = 1
            for j in children[i]:
                res*=dp(j, 0)
                res%=mod
            memo[i][c] = res
        else:
            res = 1
            for j in children[i]:
                res*=(dp(j, 0)+dp(j, 1))
                res%=mod
            memo[i][c]= res
        return memo[i][c]
    print((dp(0, 0)+dp(0, 1))%mod)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = map(int, input().split())
        E[x - 1].append(y - 1)
        E[y - 1].append(x - 1)

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb = (tb * w) % MOD
            tw = (tw * (w + b)) % MOD
        return tb, tw
    return sum(dp(0)) % MOD


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = map(int, input().split())
        E[x - 1].append(y - 1)
        E[y - 1].append(x - 1)

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb *= w
            tw *= w + b
        return tb % MOD, tw % MOD
    return sum(dp(0)) % MOD


print(main())

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for i in range(N - 1):
        x, y = map(int, input().split())
        E[x - 1].append(y - 1)
        E[y - 1].append(x - 1)

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb *= w
            tw *= w + b
        return tb, tw
    return sum(dp(0)) % (10 ** 9 + 7)


print(main())

Submission status: Time Limit Exceeded

Solution code:
def solve(n, g):
    mod = 10 ** 9 + 7

    def dfs(v):
        checked[v] = True

        w = 1
        b = 1
        for u in g[v]:
            if checked[u]:
                continue
            uw, ub = dfs(u)
            w = w * (uw + ub) % mod
            b = b * uw % mod
        return w, b

    checked = [False] * n
    checked[0] = True
    return sum(dfs(0)) % mod


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする
# 2次元配列でdpするより、1次元*2本の方が若干速い

Submission status: Time Limit Exceeded

Solution code:
def solve(n, g):
    mod = 10 ** 9 + 7

    dp_w = [1] * n
    dp_b = [1] * n

    # dp_x[j] := 頂点jをxとする場合のjを親とする部分木の塗り方の状態数
    # dp_w[j] = reduce(mul, (dp_w[k] + dp_b[k] for k in g[j]))
    # dp_b[j] = reduce(mul, (dp_w[k] for k in g[j]))

    def dfs(v):
        checked[v] = True
        for u in g[v]:
            if checked[u]:
                continue
            dfs(u)
            dp_w[v] = dp_w[v] * (dp_w[u] + dp_b[u]) % mod
            dp_b[v] = dp_b[v] * dp_w[u] % mod

    checked = [False] * n
    checked[0] = True
    dfs(0)

    return (dp_w[0] + dp_b[0]) % mod


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする

Submission status: Time Limit Exceeded

Solution code:
def solve(n, g):
    mod = 10 ** 9 + 7

    dp = tuple([1] * 2 for _ in range(n))

    # dp[j][0/1] := 頂点jを0/1とする場合のjを親とする部分木の塗り方の状態数
    # dp[j][0] = reduce(mul, (dp[k][0] + dp[k][1] for k in g[j]))
    # dp[j][1] = reduce(mul, (dp[k][0] for k in g[j]))

    def dfs(v):
        checked[v] = True
        for u in g[v]:
            if checked[u]:
                continue
            dfs(u)
            dp[v][0] = dp[v][0] * (dp[u][0] + dp[u][1]) % mod
            dp[v][1] = dp[v][1] * dp[u][0] % mod

    checked = [False] * n
    checked[0] = True
    dfs(0)

    return sum(dp[0]) % mod


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする

Submission status: Time Limit Exceeded

Solution code:
def solve(n, g):
    mod = 10 ** 9 + 7

    dp = [[1] * 2 for _ in range(n)]

    # dp[j][0/1] := 頂点jを0/1とする場合のjを親とする部分木の塗り方の状態数
    # dp[j][0] = reduce(mul, (dp[k][0] + dp[k][1] for k in g[j]))
    # dp[j][1] = reduce(mul, (dp[k][0] for k in g[j]))

    def dfs(v, parent=-1):
        for u in g[v]:
            if u == parent:
                continue
            dfs(u, v)
            dp[v][0] = dp[v][0] * (dp[u][0] + dp[u][1]) % mod
            dp[v][1] = dp[v][1] * dp[u][0] % mod

    dfs(0)

    return sum(dp[0]) % mod


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
graph = {i:[] for i in range(n+1)}
for j in range(n-1):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

memo_ls = [[None for j in range(2)] for i in range(n+1)]
# i番目の人がj色の時の通り数 0 : 白
cur = 0
def dfs(cur, col, last):
    if memo_ls[cur][col] is not None:
        return memo_ls[cur][col]
    next_col_num = 1 if col == 1 else 2
    _sum = 1
    cnt = 0
    for _next in graph[cur]:
        if _next == last:
            continue
        cnt += 1
        res = 0
        for next_col in range(next_col_num):
            res += dfs(_next, next_col, cur)
        _sum *= max(1, res)
    if cnt == 0:
        memo_ls[cur][col] = 1
        return 1
    res = _sum % (10 ** 9 + 7)
    memo_ls[cur][col] = res
    return res
res = dfs(0,0,-1) + dfs(0,1,-1)
print(res % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
n = int(input())
graph = {i:[] for i in range(n+1)}
for j in range(n-1):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

memo_ls = [[None for j in range(2)] for i in range(n+1)]
# i番目の人がj色の時の通り数 0 : 白
cur = 0
def dfs(cur, col, last):
    if memo_ls[cur][col] is not None:
        return memo_ls[cur][col]
    next_col_num = 1 if col == 1 else 2
    _sum = 1
    cnt = 0
    for _next in graph[cur]:
        res = 0
        for next_col in range(next_col_num):
            if _next == last:
                continue
            cnt += 1
            res += dfs(_next, next_col, cur)
        _sum *= max(1, res)
    if cnt == 0:
        memo_ls[cur][col] = 1
        return 1
    res = _sum % (10 ** 9 + 7)
    memo_ls[cur][col] = res
    return res
res = dfs(0,0,-1) + dfs(0,1,-1)
print(res % (10**9+7))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
n = int(input())
graph = {i:[] for i in range(n+1)}
for j in range(n-1):
    x, y = [int(i) for i in sys.stdin.readline().split()]
    x -= 1
    y -= 1
    graph[x].append(y)
    graph[y].append(x)

memo_ls = [[None for j in range(2)] for i in range(n+1)]
# i番目の人がj色の時の通り数 0 : 白
cur = 0
def dfs(cur, col, last):
    if memo_ls[cur][col] is not None:
        return memo_ls[cur][col]
    next_col_num = 1 if col == 1 else 2
    _sum = 1
    cnt = 0
    for _next in graph[cur]:
        res = 0
        for next_col in range(next_col_num):
            if _next == last:
                continue
            cnt += 1
            res += dfs(_next, next_col, cur)
        _sum *= max(1, res)
    if cnt == 0:
        memo_ls[cur][col] = 1
        return 1
    res = _sum % (10 ** 9 + 7)
    memo_ls[cur][col] = res
    return res
res = dfs(0,0,-1) + dfs(0,1,-1)
print(res % (10**9+7))