Problem:


Score : 100 points

Problem Statement

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

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

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

Constraints

All values in input are integers.

1 \leq N \leq 10^5

1 \leq x_i, y_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1 2
2 3

Sample Output 1

5

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

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

9

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

Sample Input 3

1

Sample Output 3

2

Sample Input 4

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

Sample Output 4

157



Sample input:
3
1 2
2 3


Sample output:
5

Submission status: Accepted

Solution code:
from collections import 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 = (ans1 * 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: Accepted

Solution code:
from collections import deque
import sys

N = int(input())
mod = 10 ** 9 + 7

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

xy = []
dic = {}

for i in range(N-1):

    x,y = map(int,input().split())
    x -= 1
    y -= 1
    
    xy.append([x,y])

    if x not in dic:
        dic[x] = []
    if y not in dic:
        dic[y] = []

    dic[x].append(y)
    dic[y].append(x)


q = deque([0])

dep = [[float("inf"),i] for i in range(N)]
dep[0][0] = 0


while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:
        if dep[i][0] > dep[now][0] + 1:
            dep[i][0] = dep[now][0] + 1
            q.append(i)

end = [False] * N
dep.sort()
dep.reverse()

B = [1] * N
W = [1] * N

for i in range(N):

    now = dep[i][1]

    for i in dic[now]:
        if end[i]:
            B[now] *= W[i]
            W[now] *= (B[i] + W[i])
            B[now] %= mod
            W[now] %= mod

    end[now] = True

print ((B[0] + W[0]) % mod )

Submission status: Accepted

Solution code:
N, = map(int, input().split())
M = 10**9+7
d = [set() for _ in range(N+1)]
from collections import deque
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].add(b)
    d[b].add(a)


stack = deque([1])
leafs = set()
p = [0 for _ in range(N+1)]
vs = set([1])
vv = list()
while stack:
    v = stack.popleft()
    vv.append(v)
    for u in d[v]:
        if u in vs:
            continue
        p[u] = v
        vs.add(u)
        stack.append(u)

dp1 = [-1 for _ in range(N+1)]
dp2 = [-1 for _ in range(N+1)]
for v in vv[::-1]:
    if len(d[v]) == 1 and v != 1:
        dp1[v] = 1
        dp2[v] = 1
        continue
    xx=yy=1
    for u in d[v]:
        if p[v] == u:
            continue
        xx = (xx * dp2[u])%M
        yy = (yy * (dp1[u] + dp2[u]))%M
    dp1[v] = xx
    dp2[v] = yy
print((dp1[1]+dp2[1])%M)

Submission status: Accepted

Solution code:
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)

visited = [False]*n
q = deque([0])
lst = []  # 0を根として、深い頂点から見たい。
while q:
    v = q.popleft()
    visited[v] = True
    lst.append(v)
    for w in g[v]:
        g[w].remove(v)
        if not visited[w]:
            q.append(w)
lst = lst[::-1]

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

for v in lst:
    for w in g[v]:
        white[v] *= white[w]+black[w]
        white[v] %= mod
        black[v] *= white[w]
        black[v] %= mod

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

Submission status: Accepted

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

n=int(input())
e=[[] for i in range(n)]
dp=[[0,0] for i in range(n)]
for i in range(n-1):
    a,b=[int(j)-1 for j in input().split()]
    e[a].append(b)
    e[b].append(a)

par=[-1]*(n)
l=[]
from collections import deque
q=deque([0])
while q:
    p=q.pop()
    l.append(p)
    for i in e[p]:
        if i==par[p]:
            continue
        par[i]=p
        q.append(i)

dpw=[1]*(n+1)
dpb=[1]*(n+1)

for i in l[::-1]:
    w=dpw[i]
    b=dpb[i]
    p=par[i]
    dpw[p]*=(b+w)
    dpw[p]%=mod
    dpb[p]*=w
    dpb[p]%=mod

print((dpw[0]+dpb[0])%mod)

Submission status: Accepted

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)

depth = [-1]*n
prv = [-1]*n
depth[0] = 0
prv[0] = 0
stack = [[-1,0]]
while stack:
    pre,now = stack.pop()
    for nex in G[now]:
        if nex==pre:continue
        depth[nex] = depth[now] + 1
        prv[nex] = now
        stack.append([now,nex])


d_to_i = [[] for _ in range(n)]
for i in range(n):
    d_to_i[depth[i]].append(i)


dp = [[1,1] for _ in range(n)]
mod = 10**9 + 7
for d in range(n-1,-1,-1):
    for now in d_to_i[d]:
        for nex in G[now]:
            if depth[nex] < depth[now]:continue
            dp[now][0] *= (dp[nex][0] + dp[nex][1])%mod
            dp[now][1] *= dp[nex][0]%mod

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

Submission status: Accepted

Solution code:
from collections import deque
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

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: Accepted

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

def dfs(v,p):
  vb,vw = 1,1
  for x in g[v]:
    if x == p:
      continue
    xb,xw = dfs(x,v)
    vb = vb*xw%mod
    vw = vw*(xb+xw)%mod
  return vb, vw

ab,aw = dfs(0,-1)
print((ab+aw)%mod)

Submission status: Accepted

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

def dfs(v,p):
  vb,vw = 1,1
  for x in g[v]:
    if x == p:
      continue
    xb,xw = dfs(x,v)
    vb = vb*xw%mod
    vw = vw*(xb+xw)%mod
  return vb, vw

ab,aw = dfs(n//2,-1)
print((ab+aw)%mod)

Submission status: Accepted

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

mod = 10**9+7
N = int(input())
adj = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)

seq = []
st = [1]
seen = [0] * (N+1)
seen[1] = 1
child = [[] for _ in range(N+1)]
while st:
    v = st.pop()
    seq.append(v)
    for u in adj[v]:
        if seen[u] == 0:
            seen[u] = 1
            st.append(u)
            child[v].append(u)

seq.reverse()
dp0 = [1] * (N+1)
dp1 = [1] * (N+1)
for v in seq:
    for u in child[v]:
        dp0[v] = (dp0[v] * ((dp0[u] + dp1[u])%mod)) % mod
        dp1[v] = (dp1[v] * dp0[u]) % mod

print((dp0[1] + dp1[1]) % mod)

Submission status: Accepted

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


dp=[{'w':None, 'b':None} for i in range(n)]



def cal(parent, node, col):

    nei = adj_mat[node]
    if len(nei)==1:
        if col=='w':
            return 2
        else:
            return 1 
    
    else:
        if dp[node][col]:
            return dp[node][col]
        
        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
            dp[node][col] = (sb+sw)%m
            return dp[node][col]

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


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: Accepted

Solution code:
# cook your dish here
import sys
 
sys.setrecursionlimit(100005)
MOD = 1000000007
 
 
def dfs(v, a):
    w, b = 1, 1
    # print(w,b,v);
    for u in links[v]:
        if u == a:
            continue
        cw, cb = dfs(u, v)
        w *= cw + cb
        b *= cw
        w %= MOD
        b %= MOD
        # print(w,b,u,cw,cb);
    return w, b
 
 
n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].add(y)
    links[y].add(x)
 
print(sum(dfs(0, None)) % MOD)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u=0,pu=-1):
        w,b=1,1
        for v in to[u]:
            if v==pu:continue
            dfs(v,u)
            vw,vb=dp[v]
            w*=(vw+vb)
            b*=vw
        dp[u]=[w%md,b%md]

    md=10**9+7
    to=defaultdict(list)
    n=int(input())
    for _ in range(n-1):
        x,y=map(int1,input().split())
        to[x].append(y)
        to[y].append(x)
    dp=[[0]*2 for _ in range(n)]
    dfs()
    print(sum(dp[0])%md)

main()

Submission status: Accepted

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

    order = []
    parent = [-1] * n

    stack = [0]
    checked = [0] * n
    checked[0] = 1

    while stack:
        v = stack.pop()
        order.append(v)

        for u in g[v]:
            if checked[u]:
                continue
            checked[u] = 1
            stack.append(u)
            parent[u] = v

    order.reverse()

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

    checked = [0] * n

    for v in order:
        checked[v] = 1
        p = parent[v]

        if p == -1:
            continue

        dp_w[p] *= (dp_w[v] + dp_b[v])
        dp_w[p] %= mod

        dp_b[p] *= dp_w[v]
        dp_b[p] %= mod

    v = order[-1]
    return (dp_w[v] + dp_b[v]) % mod


if __name__ == '__main__':
    import sys

    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: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def main():
    N = int(input())
    d = {}
    v = set()
    if N == 1:
        return 2
    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: Accepted

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

    stack = [0]
    order = []
    parent = [-1] * n
    checked = [False] * n
    checked[0] = True

    while stack:
        v = stack.pop()
        order.append(v)
        for u in g[v]:
            if checked[u]:
                continue
            checked[u] = True
            parent[u] = v
            stack.append(u)

    order.reverse()

    checked = [False] * n

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

    for v in order:
        checked[v] = True
        par = parent[v]
        if par == -1:
            continue
        dp_w[par] = (dp_w[par] * (dp_w[v] + dp_b[v])) % mod
        dp_b[par] = (dp_b[par] * dp_w[v]) % mod

    v = order[-1]
    return (dp_w[v] + dp_b[v]) % mod


if __name__ == '__main__':
    import sys

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

# https://atcoder.jp/contests/dp/submissions/8270981
# 参考にした

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

# 再帰関数でdfsしたらTLEした

# 葉から根（0にした）に向かって、
# 親に掛け算する

# https://atcoder.jp/contests/dp/submissions/3950379
# メモ化再帰で解いていたので、これを参考にしたかった
# しかし、自分では要旨をつかめず、真似ても2000msを超えてしまったので、あきらめた

Submission status: Accepted

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

    stack = [0]
    order = []
    parent = [-1] * n
    checked = [False] * n
    checked[0] = True

    while stack:
        v = stack.pop()
        order.append(v)
        for u in g[v]:
            if checked[u]:
                continue
            checked[u] = True
            parent[u] = v
            stack.append(u)

    order.reverse()

    checked = [False] * n

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

    for v in order:
        checked[v] = True
        par = parent[v]
        if par == -1:
            continue
        dp_w[par] = (dp_w[par] * (dp_w[v] + dp_b[v])) % mod
        dp_b[par] = (dp_b[par] * dp_w[v]) % mod

    v = order[-1]
    return (dp_w[v] + dp_b[v]) % mod


if __name__ == '__main__':
    import sys

    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: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
XY = zip(m,m)

MOD = 10**9 + 7

graph = [[] for _ in range(N+1)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

dp_w = [1] * (N+1) # 根が白
dp_b = [1] * (N+1)

for x in order[::-1]:
    w = dp_w[x]; b = dp_b[x]
    p = parent[x]
    dp_w[p] *= (b+w); dp_w[p] %= MOD
    dp_b[p] *= w; dp_b[p] %= MOD

answer = (dp_w[1] + dp_b[1]) % MOD
print(answer)

Submission status: Accepted

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

def main():
  N = int(input())
  XY = [tuple(map(int,input().split())) for _ in range(N-1)]
  MOD =10**9+7
  
  E = [[] for _ in range(N)]
  for x,y in XY:
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
  
  def dfs(v,s):
    b = 1
    w = 1
    for u in E[v]:
      if u != s:
        b0,w0 = dfs(u,v)
        b *= w0
        w *= (b0+w0)
    #b %= MOD
    #w %= MOD
    return b,w

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        dp[v][0] *= (dp[u][0]+dp[u][1])
        dp[v][0] %= mod
        dp[v][1] *= dp[u][0]
        dp[v][1] %= mod

f(0)
ans = (dp[0][0] + dp[0][1]) % mod
print(ans)

Submission status: Accepted

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: Accepted

Solution code:

import sys
sys.setrecursionlimit(100005)
mod=1000000007
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2

def dfs(v,a):
    w=b=1
    for u in links[v]:
        if u==a:
            continue
        cw,cb=dfs(u,v)
        w*=cw+cb
        b*=cw
        w%=mod
        b%=mod
    return w,b


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

for line in sys.stdin.readlines():
    x,y=map(int, line.split())
    x-=1
    y-=1
    links[x].add(y)
    links[y].add(x)

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

N = int(input())
es = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(lambda x: int(x)-1, input().split())
    es[x].append(y)
    es[y].append(x)
depth = [None] * N
def dfs(v, p, d):
    depth[v] = d
    for u in es[v]:
        if u != p:
            dfs(u, v, d+1)
dfs(0, -1, 0)
dp = [[1] * 2 for i in range(N)]
@functools.lru_cache(maxsize=None)
def rec(v):
    d = depth[v]
    for u in es[v]:
        if d < depth[u]:
            w, b = rec(u)
            dp[v][0] *= w+b
            dp[v][1] *= w
    dp[v][0] %= mod
    dp[v][1] %= mod
    return dp[v][0], dp[v][1]
w, b = rec(0)
print((w+b)%mod)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])
#B
def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return

#C
def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return

#D
def D():
    n = I()
    a = LI()
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    dp = [[0]*(n+1) for i in range(n)]
    for le in range(1,n):
        for l in range(n-le):
            r = l+le+1
            res = float("inf")
            for i in range(l+1,r):
                m = dp[l][i]+dp[i][r]
                if m < res:
                    res = m
            res += a[r]-a[l]
            dp[l][r] = res
    print(dp[0][n])
    return

#E
def E():

    n = I()
    a = LIR(n)
    m = 1<<n
    dp = [0]*m
    dp[0] = 1
    a = [[j for j in range(n) if a[i][j]] for i in range(n)]
    bit_count = [-1]
    for i in range(n):
        for j in range(len(bit_count)):
            bit_count.append(bit_count[j]+1)
    for k in range(1,m):
        i = bit_count[k]
        for j in a[i]:
            bj = 1<<j
            if bj > k:
                break
            if not k&bj:
                continue
            nk = k^bj
            dp[k] += dp[nk]
    print(dp[m-1]%mod)
#F
def F():

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    f = [1]*n
    g = [1]*n
    bfs = [1]*n
    bfs[0] = 0
    q = deque([0])
    par = [None]*n
    d = [[0,i] for i in range(n)]
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                par[y] = x
                d[y][0] = d[x][0]+1
                q.append(y)
    d.sort(key = lambda x:-x[0])
    for _,x in d[:-1]:
        px = par[x]
        fx,gx = f[x],g[x]
        f[px] *= fx+gx
        if f[px] >= mod:
            f[px] %= mod
        g[px] *= fx
        if g[px] >= mod:
            g[px] %= mod
    print((f[0]+g[0])%mod)
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())
#n,q = [int(i) for i in readline().split()]
 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
MOD = 10**9+7
def dfs(v,p): #p: parent of v
    b = w = 1
    for c in g[v]:
        if c == p: continue
        bb, ww = dfs(c,v)
        b *= ww
        b %= MOD        
        w *= bb+ww
        w %= MOD
    return b,w

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def dfs(i):
    w=b=1
    for j in e[i]:
        if j in d:continue
        d.add(j)
        x,y=dfs(j)
        w*=x+y
        b*=x
    return w%M,b%M
M=10**9+7
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for x,y in zip(*[iter(t)]*2):
    e[x-1]+=y-1,
    e[y-1]+=x-1,
d={0}
print(sum(dfs(0))%M)

Submission status: Accepted

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

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

def dfs(x=1,parent=None):
    b,w = 1,1 # 子がすべて白、子が何でもよい
    for y in graph[x]:
        if y == parent:
            continue
        b1,w1 = dfs(y,x)
        b *= w1
        w *= (b1+w1)
        b %= MOD
        w %= MOD
    return b,w

b,w = dfs()
answer = (b+w) % MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())
nodes = [[] for _ in range(n+1)]
done = [1 for _ in range(n+1)]
mod = int(1e9+7)
def dfs(next):
    w=1
    b=1
    for v in nodes[next]:
        if done[v]:
            done[v]=0
            white,black= dfs(v)
            w *= white+black
            b *= white
            w%=mod
            b%=mod
    return (w,b)
 
for i in range(n-1):
    a,b = map(int,input().split())
    nodes[a].append(b)
    nodes[b].append(a)
done[1]=0
 
ans = dfs(1)
print(sum(ans)%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())
nodes = [[] for _ in range(n+1)]
done = [1 for _ in range(n+1)]
mod = int(1e9+7)
def dfs(next,pre):
    w=1
    b=1
    for v in nodes[next]:
        if v!=pre:
            white,black= dfs(v,next)
            w *= (white+black)
            b *= white
            w%=mod
            b%=mod
    return (w,b)

for i in range(n-1):
    a,b = map(int,input().split())
    nodes[a].append(b)
    nodes[b].append(a)
done[1]=0

ans = dfs(1,-1)
print(sum(ans)%mod)

Submission status: Accepted

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

def main():
    input = sys.stdin.readline

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

    def rec(cur, prev=None):
        white = 1
        black = 1
        for to in edges[cur]:
            if to == prev:
                continue
            w,b = rec(to, cur)
            white *= (w+b)
            white %= mod
            black *= w
            black %= mod
        return white, black

    w, b = rec(0)
    print((w+b)%mod)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
xy = [list(map(int, input().split())) for i in range(N - 1)]

MOD = 10 ** 9 + 7

class Tree:
  C, RL = {}, {}
  R, N, D = None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root = 0):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
      s.D += 1
      F = Ft
  def nasu(s, x = 0):
    DP = [[1] * 2 for _ in range(s.N)]
    for d in range(s.D - 2, 0, -1):
      for i in s.RL[d]:
        L = []
        for j in s.C[i]:
          if s.R[j] > s.R[i]:
            L.append(j)
        b = 1
        w = 1
        for k in L:
          b = b * DP[k][0] % MOD
          w = w * (DP[k][0] + DP[k][1]) % MOD
        DP[i] = [w, b]
    return (DP[x][0] + DP[x][1]) % MOD

T = Tree(N)
if N == 1:
  print(2)
  exit()
for x, y in xy:
  x -= 1
  y -= 1
  T.setC(x, y)

T.makeRank()

print(T.nasu())