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 collections import deque, defaultdict

mod = 10**9+7

n = int(input())
d = defaultdict(list)
for i in range(n-1):
    x,y = map(lambda x:int(x)-1, input().split())
    d[x].append(y)
    d[y].append(x)

if n == 1:
    print(2)
    exit()

dp = [[0]*2 for i in range(n)]

q = deque()
for i in range(n):
    if len(d[i]) == 1:
        q.append(i)

visited = set()

while True:
    i = q.popleft()
    if i in visited:
        continue

    white = 1
    other = 1
    cnt = 0
    next_i = -1
    for j in d[i]:
        if j in visited:
            white = (white*dp[j][0]) % mod
            other = (other*sum(dp[j])) % mod
        else:
            cnt += 1
            next_i = j
    if cnt > 1:
        q.append(i)
        continue
    dp[i][0] = other
    dp[i][1] = white
    visited.add(i)
    if cnt == 0:
        print(sum(dp[i])%mod)
        exit()
    q.append(next_i)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

n = int(input())

ab = [[] for _ in range(n)]

for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)

def treeDP(p):
    if len(ab[p]) == 0:
        return [2,1]
    else:
        f = 1
        g = 1
        for x in ab[p]:
            ab[x].remove(p)
            temp = treeDP(x)
            f *= temp[1]
            g *= temp[0]
        f += g
        return [f % MOD, g % MOD]

print(treeDP(0)[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
mod=10**9+7
n=int(input())
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)
C=[[] for _ in range(n)]

def fill_C(v,par):
    for c in edges[v]:
        if c==par:
            continue
        C[v].append(c)
        fill_C(c,v)
fill_C(0,-1)

DP=[[-1,-1] for _ in range(n)]

def white(v):
    if DP[v][0]!=-1:
        return DP[v][0]
    res=1
    for c in C[v]:
        res*=white(c)+black(c)
        res%=mod
    DP[v][0]=res
    return res
def black(v):
    if DP[v][1]!=-1:
        return DP[v][1]
    res=1
    for c in C[v]:
        res*=white(c)
        res%=mod
    DP[v][1]=res
    return res

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
mod=10**9+7
n=int(input())
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)
root=-1
l=-1
for i in range(n):
    if len(edges[i])>l:
        root=i
        l=len(edges[i])
C=[[] for _ in range(n)]

def fill_C(v,par):
    for c in edges[v]:
        if c==par:
            continue
        C[v].append(c)
        fill_C(c,v)
fill_C(root,-1)

DP=[[-1,-1] for _ in range(n)]

def white(v):
    if DP[v][0]!=-1:
        return DP[v][0]
    res=1
    for c in C[v]:
        res*=white(c)+black(c)
        res%=mod
    DP[v][0]=res
    return res
def black(v):
    if DP[v][1]!=-1:
        return DP[v][1]
    res=1
    for c in C[v]:
        res*=white(c)
        res%=mod
    DP[v][1]=res
    return res

print((black(root)+white(root))%mod)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

# T = defaultdict(list)
T = [set() for _ in range(N+1)]
for i in range(N-1):
    x,y = map(int, input().split())
    # T[x] += [y]
    # T[y] += [x]
    T[x].add(y)
    T[y].add(x)

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7

T = defaultdict(list)
for i in range(N-1):
    x,y = map(int, input().split())
    T[x] += [y]
    T[y] += [x]

def dfs(n,oya):
    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())

from collections import defaultdict

MOD = 10**9 + 7
T = defaultdict(list)
for i in range(N-1):
    x,y = map(int, input().split())
    T[x] += [y]
    T[y] += [x]

DP = [[0] * (N+1) for _ in range(2)]

def dfs(n,oya):

    b,w = 1,1
    for child_n in T[n]:
        if child_n == oya:
            continue
        child_b, child_w = dfs(child_n, n)
        b *= child_w % MOD
        w *= (child_b+child_w)%MOD
    return b%MOD, w%MOD
print( sum(dfs(1,None)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())

from collections import defaultdict

MOD = 10**9 + 7
T = defaultdict(list)
R = defaultdict(list)
visited = [-1]*(N+1)
for i in range(N-1):
    x,y = map(int, input().split())
    # x,y = min(x,y), max(x,y)
    T[x] += [y]
    T[y] += [x]

# DP = defaultdict(lambda : 0 )
DP = [[0] * (N+1) for _ in range(2)]

root = 1
visited[root] = 1
node = root
from collections import deque
q = deque()
q.append(node)

# while q:
#     node = q.popleft()
#     # print("node: ,", node)
#     if all(visited[child]!=-1 for child in T[node]):
#         continue
#     for chnode in T[node]:
#         if visited[chnode] == -1:
#             R[node] += [chnode]
#             visited[chnode] = 1
#             q.append(chnode)


def dfs(c,n,oya):
    # if len(T[n]) == 0:
    #     DP[0][n] = 1
    #     DP[1][n] = 1
    #     return 1

    if c == 0:
        black = 1
        for child_n in T[n]:
            if child_n == oya:
                continue
            black *= dfs(1, child_n, n) % MOD
        DP[0][n] = black % MOD
        return black % MOD
    else:
        white = 1
        for child_n in T[n]:
            if child_n == oya:
                continue
            white *= dfs(0, child_n, n) + dfs(1, child_n,n) % MOD
        DP[1][n] = white % MOD
        return white % MOD

print( (dfs(0, 1, None) + dfs(1,1, None)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
import sys
sys.setrecursionlimit(10000000)
N = int(input())
# T = [ [int(j) for j in input().split()] for _ in range(N-1)]

from collections import defaultdict

MOD = 10**9 + 7
T = defaultdict(list)
R = defaultdict(list)
visited = [-1]*(N+1)
for i in range(N-1):
    x,y = map(int, input().split())
    # x,y = min(x,y), max(x,y)
    T[x] += [y]
    T[y] += [x]

# DP = defaultdict(lambda : 0 )
DP = [[0] * (N+1) for _ in range(2)]
# visited = [False] * (N+1)

root = 1
visited[root] = 1
node = root
from collections import deque
q = deque()
q.append(node)

while q:
    node = q.popleft()
    # print("node: ,", node)
    if all(visited[child]!=-1 for child in T[node]):
        continue
    for chnode in T[node]:
        if visited[chnode] == -1:
            R[node] += [chnode]
            visited[chnode] = 1
            q.append(chnode)
    
# 0 for black
# 1 for white
# print(R)

def dfs(c,n):
    if len(R[n]) == 0:
        DP[0][n] = 1
        DP[1][n] = 1
        return 1

    if c == 0:
        black = 1
        for child_n in R[n]:
            black *= dfs(1, child_n) % MOD
        DP[0][n] = black % MOD
        return black % MOD
    else:
        white = 1
        for child_n in R[n]:
            white *= dfs(0, child_n) + dfs(1, child_n) % MOD
        DP[1][n] = white % MOD
        return white % MOD

print( (dfs(0, 1) + dfs(1,1)) % MOD)

Submission status: Time Limit Exceeded

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

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)


QUE=[1]

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b=b*y%mod
            w=w*(x+y)%mod

        return b,w

print(sum(ANS(1))%mod)

Submission status: Time Limit Exceeded

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

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)

from collections import deque
QUE=deque([1])

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b=b*y%mod
            w=w*(x+y)%mod

        return b,w

print(sum(ANS(1))%mod)

Submission status: Time Limit Exceeded

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

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)

from collections import deque
start=N//2+1
QUE=deque([start])

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b=b*y
            w=w*(x+y)

        return b%mod,w%mod

print(sum(ANS(start))%mod)

Submission status: Time Limit Exceeded

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

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)

from collections import deque
QUE=deque([1])

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b=b*y
            w=w*(x+y)

        return b%mod,w%mod

print(sum(ANS(1))%mod)

Submission status: Time Limit Exceeded

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

N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]

EDGELIST=[[] for i in range(N+1)]

for x,y in XY:
    EDGELIST[x].append(y)
    EDGELIST[y].append(x)

check=[0]*(N+1)

from collections import deque
QUE=deque([1])

EDGE1=[[] for i in range(N+1)]

while QUE:
    x=QUE.pop()
    if check[x]==1:
        continue

    for to in EDGELIST[x]:
        if check[to]==1:
            continue
        else:         
            QUE.append(to)
            EDGE1[x].append(to)

    check[x]=1
        

def ANS(n):
    if EDGE1[n]==[]:
        return 1,1
    else:
        b=1
        w=1
        for to in EDGE1[n]:
            x,y=ANS(to)
            b*=y
            w*=(x+y)

        return b,w

print(sum(ANS(1))%(10**9+7))

Submission status: Time Limit Exceeded

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

N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(2)
    exit()

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
dp = [[1,1] for i in range(N)]

def rec(i,parent):
    for to in es[i]:
        if to==parent: continue
        rec(to,i)
        dp[i][0] *= (dp[to][0] + dp[to][1])
        dp[i][1] *= dp[to][0]
        dp[i][0] %= MOD
        dp[i][1] %= MOD

rec(0,-1)
print(sum(dp[0])%MOD)

Submission status: Time Limit Exceeded

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

N = int(input())
src = [tuple(map(int,input().split())) for i in range(N-1)]

if N==1:
    print(2)
    exit()

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
dp = [[1,1] for i in range(N)]

def rec(i,parent):
    for to in es[i]:
        if to==parent: continue
        rec(to,i)
        dp[i][0] *= (dp[to][0] + dp[to][1])
        dp[i][1] *= dp[to][0]
        dp[i][0] %= MOD
        dp[i][1] %= MOD

rec(0,-1)
print(sum(dp[0])%MOD)

Submission status: Memory Limit Exceeded

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


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

    n = int(inp())
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        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] % MOD
            dp[vi][1] %= MOD

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


if __name__ == "__main__":
    resolve()

Submission status: Memory Limit Exceeded

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


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

    n = int(inp())
    e = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = map(lambda x: int(x) - 1, inp().split())
        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__":
    resolve()

Submission status: Memory 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 or visited[chld]:
                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: Memory 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):
        dp[v][0] = 1
        dp[v][1] = 1
        for to in G[v]:
            if to == parent:
                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)]

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


if __name__ == "__main__":
    resolve()

Submission status: Memory 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):
        if dp[v][0] and dp[v][1]:
            return
        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(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 + 1)]

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


if __name__ == "__main__":
    resolve()

Submission status: Memory 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):
        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(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 + 1)]

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


if __name__ == "__main__":
    resolve()

Submission status: Memory Limit Exceeded

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

N = int(input())
MOD = 10**9+7
G = [set() for _ in range(N)]
for i in range(N-1):
    x, y = map(lambda x: int(x)-1, input().split())
    G[x].add(y)
    G[y].add(x)

def dfs(v, r):
    w, b = 1, 1
    for u in G[v]:
        if u == r: continue
        c_w, c_b = dfs(u, v)
        w *= c_w + c_b
        b *= c_w
    w %= MOD
    b %= MOD
    return w, b

print(sum(dfs(0, None))%MOD)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  white, black = [1]*N, [1]*N
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        white[v] *= white[u]+black[u]
        white[v] %= mod
        black[v] *= white[u]
        black[v] %= mod
    if marker==0:
      stack.pop()
  ans = (black[0]+white[0])%mod
  return ans

mod = 10**9+7
ans = dfs(0)
print(ans)

Submission status: Accepted

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

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

dp = [[1,1] for i in range(N)]
def rec(v,p=-1):
    for to in es[v]:
        if to==p: continue
        rec(to,v)
        dp[v][0] *= (dp[to][0] + dp[to][1])
        dp[v][1] *= dp[to][0]
        dp[v][0] %= MOD
        dp[v][1] %= MOD
rec(0)

print(sum(dp[0]) % MOD)

Submission status: Accepted

Solution code:

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

    return count


import sys
sys.setrecursionlimit(10**6)


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

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

Submission status: Accepted

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

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

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

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

    dpt[node][color] = result
    return result

print((count_cc(0, 1, 0) + count_cc(0, 1, 1)) % MOD)

Submission status: Accepted

Solution code:
# 類題（同じ問題): ABC 036 D
# https://atcoder.jp/contests/abc036/tasks/abc036_d
# 解法参考: https://qiita.com/Kiri8128/items/cbaa021dbcb07b5fdb92

from collections import deque

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

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

P = [-1] * N # P[i] はiの親。iが根なら-1
Q = deque([0]) # queue。根にするやつを最初に追加
R = [] # トポロジカルソート
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in G[i]:
        if a == P[i]: continue
        P[a] = i
        G[a].remove(i) #Gを子リストにする。
        deque.append(Q, a)

# トポロジカルソート逆順（葉）から順にみていく
for a in R[::-1]:
  # aが葉のとき
  if len(G[a])==0:
    dp[a][0] = 1
    dp[a][1] = 1
  # aが合流地点のとき: 部分木の情報をまとめる
  elif len(G[a])>1:
    # いったん値をリセットする
    dp[a][0] = 1
    dp[a][1] = 1
    for c in G[a]:
      dp[a][1] *= sum(dp[c]) # aの値が白の場合は、aの子cの色は何でもいい
      dp[a][0] *= dp[c][1] # 一方、aの値が黒の場合は、aの子cは全て白でなければいけない
    dp[a][0] %= mod
    dp[a][1] %= mod
  b = P[a]
  if b == -1:break
  dp[b][0] += dp[a][1] % mod
  dp[b][1] += dp[a][0]+dp[a][1] % mod

print(sum(dp[0])%mod)

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


def main():
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = (int(i) for i in input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)

    dp_w = [0]*N
    dp_b = [0]*N

    def dfs(s):
        seen = [False]*N
        par = [-1]*N
        stack = [s]
        seen[s] = True
        while stack:
            v = stack.pop()
            if v >= 0:
                stack.append(~v)
                for u in G[v]:
                    if seen[u]:
                        continue
                    stack.append(u)
                    seen[u] = True
                    par[u] = v
            else:
                # 帰りがけ順
                # ~v = -v-1
                v = ~v
                w = 1
                b = 1
                for u in G[v]:
                    if u == par[v]:
                        continue
                    w *= dp_w[u] + dp_b[u]
                    b *= dp_w[u]
                    w %= MOD
                    b %= MOD
                dp_w[v] += w
                dp_b[v] += b
                dp_w[v] %= MOD
                dp_b[v] %= MOD

    dfs(0)
    print((dp_w[0] + dp_b[0]) % MOD)


if __name__ == '__main__':
    main()