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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def main():
  MOD = 10**9+7
  N = int(input())
  edge = [[] for _ in range(N+1)]
  dp = [[0]*2 for i in range(100005)]
  # dp[v][c]: 頂点vを色cの根とする部分木の塗り分け方の総数
  # 葉が決まると順々に求まっていく
  for i in range(N-1):
      x,y = map(int,input().split())
      edge[x].append(y)
      edge[y].append(x)

  # 0:white,1:black
  def dfs(v,last=-1):
      dp[v][0] = 1
      dp[v][1] = 1
      for nv in edge[v]:
          if nv == last:
              continue
          dfs(nv, v)
          dp[v][0] = dp[v][0] * ((dp[nv][0] + dp[nv][1]) % MOD) % MOD
          dp[v][1] = dp[v][1] * dp[nv][0] % MOD


  dfs(1)
  print((dp[1][0] + dp[1][1])%MOD)
if __name__ == ''__main__:
  main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
MOD = 10**9+7
N = int(input())
edge = [[] for _ in range(N+1)]
dp = [[0]*2 for i in range(100005)]
# dp[v][c]: 頂点vを色cの根とする部分木の塗り分け方の総数
# 葉が決まると順々に求まっていく
for i in range(N-1):
    x,y = map(int,input().split())
    edge[x].append(y)
    edge[y].append(x)

# 0:white,1:black
def dfs(v,last=-1):
    dp[v][0] = 1
    dp[v][1] = 1
    for nv in edge[v]:
        if nv == last:
            continue
        dfs(nv, v)
        dp[v][0] = dp[v][0] * ((dp[nv][0] + dp[nv][1]) % MOD) % MOD
        dp[v][1] = dp[v][1] * dp[nv][0] % MOD


dfs(1)
print(dp[1][0] + dp[1][1])MOD = 10**9+7
N = int(input())
edge = [[] for _ in range(N+1)]
dp = [[0]*2 for i in range(100005)]
# dp[v][c]: 頂点vを色cの根とする部分木の塗り分け方の総数
# 葉が決まると順々に求まっていく
for i in range(N-1):
    x,y = map(int,input().split())
    edge[x].append(y)
    edge[y].append(x)

# 0:white,1:black
def dfs(v,last=-1):
    dp[v][0] = 1
    dp[v][1] = 1
    for nv in edge[v]:
        if nv == last:
            continue
        dfs(nv, v)
        dp[v][0] = dp[v][0] * ((dp[nv][0] + dp[nv][1]) % MOD) % MOD
        dp[v][1] = dp[v][1] * dp[nv][0] % MOD


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

Submission status: Runtime Error

Solution code:
#dpp
MOD = 10**9+7
n = int(input())
dp = [[1 for _ in range(2)] for _ in range(n)]
edges = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	edges[x-1].append(y-1)
	edges[y-1].append(x-1)

def dfs(le, ro):
	for ed in edges[le]:
		if ed == ro:
			continue
		dfs(ed, le)
		dp[le][0] = (dp[le][0] * (dp[ed][0] + dp[ed][1])) % MOD
		dp[le][1] = (dp[le][1] * dp[ed][0]) % MOD
	return

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

Submission status: Runtime Error

Solution code:

from collections import defaultdict

N = int(input())
g = defaultdict(set)

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

M = 10**9 + 7


def dfs(u, p):
    w = 1
    b = 1
    for v in g[u]:
        if p == v:
            continue
        wn, bn = dfs(v, u)
        w *= wn + bn
        b *= wn
        w %= M
        b %= M
    return w, b
print(sum(dfs(1, -1))%M)

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 10**9 + 7

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

dp1 = [0]*N # 頂点iが白のときに、頂点iを根とする部分木の塗り方の組み合わせ
dp2 = [0]*N # 頂点iが黒のときに、頂点iを根とする部分木の塗り方の組み合わせ


# nodeを白で塗るときに、nodeを根とする部分木の塗り方の組み合わせを求める
def solve1(node, parent): 
  global dp1
  global dp2
  if dp1[node]:
    return dp1[node]
  else:
    children = tree[node]
    if len(children)==0 or \
        len(children)==1 and children[0]==parent: # nodeがリーフのとき
      dp1[node] = 1 # nodeを白に塗る1通りだけ
      return dp1[node]
    
    else:
      dp1[node] = 1
      for child in children:
        if child == parent:
          continue

        dp1[node] *= solve1(child, node) + solve2(child, node)
        dp1[node] %= MOD

      return dp1[node]


# nodeを黒で塗るときに、nodeを根とする部分木の塗り方の組み合わせを求める
def solve2(node, parent):
  global dp1
  global dp2
  if dp2[node]:
    return dp2[node]
  else:
    children = tree[node]
    if len(children)==0 or \
    len(children)==1 and children[0]==parent: # nodeがリーフのとき
      dp2[node] = 1 # nodeを黒に塗る1通りだけ
      return dp2[node]
    
    else:
      dp2[node] = 1
      for child in children:
        if child == parent:
          continue

        dp2[node] *= solve1(child, node)
        dp2[node] %= MOD

      return dp2[node]


print((solve1(0, -1)+solve2(0, -1))%MOD)

Submission status: Runtime Error

Solution code:
N = int(input())
MOD = 10**9 + 7

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

dp1 = [0]*N # 頂点iが白のときに、頂点iを根とする部分木の塗り方の組み合わせ
dp2 = [0]*N # 頂点iが黒のときに、頂点iを根とする部分木の塗り方の組み合わせ


# nodeを白で塗るときに、nodeを根とする部分木の塗り方の組み合わせを求める
def solve1(node, parent): 
  global dp1
  global dp2
  if dp1[node]:
    return dp1[node]
  else:
    children = tree[node]
    if len(children)==0 or \
        len(children)==1 and children[0]==parent: # nodeがリーフのとき
      dp1[node] = 1 # nodeを白に塗る1通りだけ
      return dp1[node]
    
    else:
      dp1[node] = 1
      for child in children:
        if child == parent:
          continue

        dp1[node] *= solve1(child, node) + solve2(child, node)
        dp1[node] %= MOD

      return dp1[node]


# nodeを黒で塗るときに、nodeを根とする部分木の塗り方の組み合わせを求める
def solve2(node, parent):
  global dp1
  global dp2
  if dp2[node]:
    return dp2[node]
  else:
    children = tree[node]
    if len(children)==0 or \
    len(children)==1 and children[0]==parent: # nodeがリーフのとき
      dp2[node] = 1 # nodeを黒に塗る1通りだけ
      return dp2[node]
    
    else:
      dp2[node] = 1
      for child in children:
        if child == parent:
          continue

        dp2[node] *= solve1(child, node)
        dp2[node] %= MOD

      return dp2[node]


print(solve1(0, -1) + solve2(0, -1))

Submission status: Runtime Error

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))
    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: Runtime Error

Solution code:
from collections import defaultdict


def independent_set(adj):
    MOD = 10 ** 9 + 7

    def dfs(cur, parent):
        black, white = 1, 1
        for child in adj[cur]:
            if child != parent:
                child_b, child_w = dfs(child, cur)
                black = (black * child_w) % MOD
                white = (white * (child_b + child_w)) % MOD
        return black, white

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


def main():
    n = int(input())
    adj = defaultdict(list)
    for _ in range(n - 1):
        x, y = [int(x) - 1 for x in raw_input().split()]
        adj[x].append(y)
        adj[y].append(x)
    return independent_set(adj)


print(main())

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def independent_set(adj):
    MOD = 10 ** 9 + 7

    def dfs(cur, parent):
        black, white = 1, 1
        for child in adj[cur]:
            if child != parent:
                child_b, child_w = dfs(child, cur)
                black = (black * child_w) % MOD
                white = (white * (child_b + child_w)) % MOD
        return black, white

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


def main():
    n = int(input())
    adj = defaultdict(list)
    for _ in range(n - 1):
        x, y = [int(x) - 1 for x in input().split()]
        adj[x].append(y)
        adj[y].append(x)
    return independent_set(adj)


print(main())

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import random

import sys
sys.setrecursionlimit(100000000)

# N, W = 100, 20000
# W_V = [[random.randint(1,1000000), random.randint(1,1000)] for i in range(N)]
N = int(raw_input())
ADG_VERTICES= defaultdict(list)
panting_cache = {}
for i in range(N-1):
    u, v = map(int, raw_input().split())
    ADG_VERTICES[u].append(v)
    ADG_VERTICES[v].append(u)

BLACK_COLOR = 1
WHITE_COLOR = 0
MOD_VAL = int(1e9 + 7)
def get_ways_to_paint_vertices(parent_color, parent_vertex, vertex):
    if ADG_VERTICES[vertex] == [parent_vertex]:
        if parent_color == BLACK_COLOR:
            return 1
        else:
            return 2

    if (parent_color,  parent_vertex, vertex) in panting_cache:
        return panting_cache[parent_color,  parent_vertex, vertex]
    ans1 = 1
    ans2 = 0
    for adg_vertex in ADG_VERTICES[vertex]:
        if adg_vertex != parent_vertex:
            ans1 = (ans * get_ways_to_paint_vertices(WHITE_COLOR, vertex, adg_vertex)) % MOD_VAL
    if parent_color != BLACK_COLOR:
        ans2 = 1
        for adg_vertex in ADG_VERTICES[vertex]:
            if adg_vertex != parent_vertex:
                ans2 = (ans2 * get_ways_to_paint_vertices(BLACK_COLOR, vertex, adg_vertex)) % MOD_VAL

    ans = ans1 + ans2
    if ans >= MOD_VAL:
        ans -= MOD_VAL
    panting_cache[parent_color, parent_vertex, vertex] = ans

    return ans


print get_ways_to_paint_vertices(None, 0, 1)

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
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]
    white[v] += tmp_w
    black[v] += tmp_b
    return None


dfs(0)

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

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
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
                www *= (w+b)
        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: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from collections import deque
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
                www *= (w+b)
        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: Runtime Error

Solution code:
from collections import deque
p = 10**9+7
memo = {}
def f(i,x):
    if len(T[i])==1:
        return 1
    if (i,x) in memo:
        return memo[(i,x)]
    memo[(i,x)] = 1
    if x==0:
        for j in T[i][1:]:
            memo[(i,x)] = (memo[(i,x)]*(f(j,0)+f(j,1)))%p
        return memo[(i,x)]
    else:
        for j in T[i][1:]:
            memo[(i,x)] = (memo[(i,x)]*f(j,0))%p
        return memo[(i,x)]
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
T = {i:[] for i in range(1,N+1)}
hist = [0 for _ in range(N+1)]
T[1] = [0]
for y in G[1]:
    T[1].append(y)
hist[1] = 1
cur = 1
que = deque([cur])
while que:
    cur = que.popleft()
    for x in T[cur][1:]:
        if hist[x]==0:
            T[x].append(cur)
            for y in G[x]:
                if y != cur:
                    T[x].append(y)
            que.append(x)
            hist[x]=1
print(f(1,0)+f(1,1))

Submission status: Runtime Error

Solution code:
p = 10**9+7
memo = {}
def f(i,x):
    if len(G[i])==1 and hist[G[i][0]]==1:
        return 1
    if (i,x) in memo:
        return memo[(i,x)]
    memo[(i,x)] = 0
    if x==0:
        for j in G[i]:
            if hist[j]==0:
                hist[i]=1
                memo[(i,x)] = (memo[(i,x)]+f(j,0)+f(j,1))%p
                hist[i]=0
        return memo[(i,x)]
    else:
        for j in G[i]:
            if hist[j]==0:
                hist[i]=1
                memo[(i,x)] = (memo[(i,x)]+f(j,0))%p
                hist[i]=0
        return memo[(i,x)]
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
hist = [0 for _ in range(N+1)]
print(f(1,0)+f(1,1))

Submission status: Runtime Error

Solution code:
MOD = 10**9+7
n = int(input())
g = [[] for _ in range(n)]
dp = [[0] * 2 for _ in range(n)]
'''
dp[i][0]: number of ways that vertex i is white, 
dp[i][1]: number of ways that vertex i is black
'''
for i in range(n - 1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

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

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

Submission status: Runtime Error

Solution code:
// Author - Sumit 

#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9+7;

using ll = long long;

const int N=1e5+5;
vector<int> v[N];

pair<int,int> dfs(int a,int p){
	int w=1,b=1;
	for(int i:v[a]){
		if(i != p){
			pair<int,int> p = dfs(i,a);
			w *= p.first + p.second;
			b *= p.first;
			w %= mod;
			b %=mod;
		}
	}
	return make_pair(w,b);
} 

int main(){
	int n;
	scanf("%d",&n);
	for(int i=0;i<n-1;++i){
		int x,y;
		scanf("%d%d",&x,&y);
		v[x].push_back(y);
		v[y].push_back(x);
	}
	pair<int,int> p = dfs(1,-1);
	int ans = (p.first + p.second)%mod;
	printf("%d",ans);
    return 0;
}

Submission status: Runtime Error

Solution code:
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, j i
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: Runtime Error

Solution code:
def main():
    input = sys.stdin.readline
    import sys
    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: Runtime Error

Solution code:
def main():
    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 not children[i]:
            return 1
        if c == 1:
            memo[i][c] = sum(dp(j, 0) for j in children[i])%mod
        else:
            memo[i][c] = sum(dp(j, 0) for j in children[i])%mod+sum(dp(j, 1) for j in children[i])%mod
            memo[i][c]%=mod
        return memo[i][c]
    print(dp(0, 0)+dp(0, 1))
main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
def main():
    N = int(input())
    d = {}
    v = set()
    for _ in range(N-1):
        x, y = map(int, input().split())
        if x in d:
            d[x].append(y)
        else:
            d[x] = [y]
        if y in d:
            d[y].append(x)
        else:
            d[y] = [x]
    w, b = dfs(1, d, v)
    return w + b
def dfs(node, d, v):
    v.add(node)
    l = []
    for i in d[node]:
        if i in v:
            continue
        w, b = dfs(i, d, v)
        l.append((w,b))
    w = 1
    b = 1
    for tw, tb in l:
        w *= (tw + tb)
        b *= tw
    return w, b

print(main() % (10**9 + 7))

Submission status: Runtime Error

Solution code:
import sys
n = int(input())
graph = {i:[] for i in range(n)}
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: Runtime Error

Solution code:
import sys
from collections import deque
n = int(input())
graph = {i:[] for i in range(n)}
for i 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)]
# 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: Runtime Error

Solution code:
N = int(input())

root = {i for i in range(N)}

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

visited = [False] * N
def dfs(n):
    visited[n] = True
    w = 1
    b = 1
    for i in to[n]:
        if visited[i] == False:
            rw, rb = dfs(i)
            w *= rw + rb
            b *= rw
    return [w,b]

ans = dfs(0)
print(ans[0] + ans[1])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
s=[[]for i in range(n+1)]
m=10**9+7
for i in range(n-1):
    x,y=map(int,input().split())
    s[x].append(y)
    s[y].append(x)
t=[[0,0]for i in range(n+1)]
def f(a,b):
    t[a][0]=t[a][1]=1
    for i in s[a]:
        if i!=b:
            f(i,a)
            t[a][0]*=t[i][0]+t[i][1]
            t[a][1]*=*t[i][0]
f(1,0)
print(sum(t[1])%m)

Submission status: Runtime Error

Solution code:
n=int(input())
s=[[]for i in range(n+1)]
m=10**9+7
for i in range(n-1):
    x,y=map(int,input().split())
    s[x].append(y)
    s[y].append(x)
t=[[0,0]for i in range(n+1)]
def f(a,b):
    t[a][0]=t[a][1]=1
    for i in s[a]:
        if i!=b:
            f(i,a)
            t[a][0]=(t[a][0]*(t[i][0]+t[i][1]))%m
            t[a][1]=(t[a][1]*t[i][0])%m
f(1,0)
print(sum(t[1]))