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

Solution (Python):
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():
    
    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():
    
    
    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)

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

    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

    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

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

if __name__ == '__main__':
    examP()

"""

"""

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**9)
MOD = 10**9 + 7

n = int(input())

neighbor = {}
for i in range(1,n+1):
    neighbor[i] = []

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

def calc(next, base):
    edges = neighbor[next]

    white, black = 1, 1
    for edge in edges:
        if(edge != base):
            white_e, black_e = calc(edge, next)
            white = white *  (white_e + black_e) % MOD
            black = black * white_e % MOD
    return white, black

white, black = calc(1,0)
print((white + black) % MOD )

Solution (Python):
from collections import defaultdict
import random

import sys
sys.setrecursionlimit(100000000)



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)

Solution (Python):
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 )

Solution (Python):
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)

Solution (Python):
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 = []  
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  


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]

        
        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))  
    x = [int()] * (N - 1)  
    y = [int()] * (N - 1)  
    for i in range(N - 1):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
    solve(N, x, y)


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):

import sys
 
sys.setrecursionlimit(100005)
MOD = 1000000007
 
 
def dfs(v, a):
    w, b = 1, 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 _ 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)

Solution (Python):

import sys
 
sys.setrecursionlimit(100005)
MOD = 1000000007
 
 
def dfs(v, a):
    w, b = 1, 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 _ 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)

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
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()

Solution (Python):
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))

Solution (Python):
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())

Solution (Python):
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))

Solution (Python):
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))

Solution (Python):
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)]

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

Solution (Python):
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)

Solution (Python):
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)