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):
MOD = 10**9 + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    from heapq import heappush, heappop
    import sys
    readline = sys.stdin.buffer.readline
    N = int(readline())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in readline().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    dp = [[modint(1)]*2 for _ in range(N)]
    from collections import deque
    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(G, s):
        leaves = []
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            has_child = False
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    has_child = True
                    Q.append(v)
            G_color[u] = 'BLACK'
            if not(has_child):
                heappush(leaves, (-G_distance[u], u))
        return leaves

    leaves = bfs(edge, 0)
    seen = [False]*N
    while leaves:
        _, leaf = heappop(leaves)
        par = G_parent[leaf]
        if par == 'NIL':
            continue
        dp[par][0] *= dp[leaf][1]
        dp[par][1] *= (dp[leaf][0]+dp[leaf][1])
        if seen[par]:
            continue
        heappush(leaves, (-G_distance[par], par))
        seen[par] = True
    print((dp[0][0]+dp[0][1]))


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    from heapq import heappush, heappop
    import sys
    readline = sys.stdin.buffer.readline
    MOD = 10**9 + 7
    N = int(readline())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in readline().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    dp = [[1]*2 for _ in range(N)]
    from collections import deque
    G_color = ['WHITE' for _ in range(N)]
    G_distance = [float('inf') for _ in range(N)]
    G_parent = ['NIL' for _ in range(N)]

    def bfs(G, s):
        leaves = []
        G_color[s] = 'GRAY'
        G_distance[s] = 0
        Q = deque()
        Q.append(s)
        while Q:
            u = Q.popleft()
            has_child = False
            for v in G[u]:
                if G_color[v] == 'WHITE':
                    G_color[v] = 'GRAY'
                    G_distance[v] = G_distance[u] + 1
                    G_parent[v] = u
                    has_child = True
                    Q.append(v)
            G_color[u] = 'BLACK'
            if not(has_child):
                heappush(leaves, (-G_distance[u], u))
        return leaves

    leaves = bfs(edge, 0)
    seen = [False]*N
    while leaves:
        _, leaf = heappop(leaves)
        par = G_parent[leaf]
        if par == 'NIL':
            continue
        dp[par][0] *= dp[leaf][1]
        dp[par][1] *= (dp[leaf][0]+dp[leaf][1])
        dp[par][0] %= MOD
        dp[par][1] %= MOD
        if seen[par]:
            continue
        heappush(leaves, (-G_distance[par], par))
        seen[par] = True
    print((dp[0][0]+dp[0][1]) % MOD)


if __name__ == '__main__':
    main()

Solution (Python):


import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
for i in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)


dp1 = [1] * N

dp2 = [1] * N
def rec(u, prev):
    for v in nodes[u]:
        if v != prev:
            rec(v, u)
            
            dp1[u] *= dp1[v] + dp2[v]
            dp1[u] %= MOD
            
            dp2[u] *= dp1[v]
            dp2[u] %= MOD

rec(0, -1)
ans = (dp1[0]+dp2[0]) % MOD
print(ans)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    mod = 10**9 + 7

    N = int(input())

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


    
    parent = [-1]*(N)
    
    order = []
    d = deque([0])
    
    while d:
        x = d.pop()
        order.append(x)
        for y in adj[x]:
            if y==parent[x]:
                continue
            parent[y] = x
            d.append(y)

    
    dp_b = [1]*(N+1)
    dp_w = [1]*(N+1)

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

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

if __name__ == '__main__':
    main()

Solution (Python):











def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    
    from itertools import combinations, permutations, accumulate
    
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    

    
    mod = 10**9 + 7

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

    
    root = -1
    l = -1
    for i in range(N):
        t = len(adj[i])
        if t > l:
            l = t
            root = i

    
    c = [[] for _ in range(N)]
    
    def ch(x, y):
        for e in adj[x]:
            if e == y:
                continue
            c[x].append(e)
            ch(e, x)
    ch(root, -1)

    
    
    dp = [[-1, -1] for _ in range(N)]

    
    
    def black(x):
        if dp[x][0] != -1:
            return dp[x][0]
        res = 1
        for e in c[x]:
            res = white(e) * res %mod
        dp[x][0] = res
        return dp[x][0]

    
    def white(x):
        if dp[x][1] != -1:
            return dp[x][1]
        res = 1
        for e in c[x]:
            res = ((black(e)+white(e))%mod) * res %mod
        dp[x][1] = res
        return dp[x][1]

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

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
mod=10**9+7
N=int(input())
G=[[] for _ in range(N+1)]
for _ in range(N-1):
    x,y=map(int, input().split())
    G[x].append(y)
    G[y].append(x)
b=[1]*(N+1)
w=[1]*(N+1)
def dfs(pre,n):
  for i in G[n]:
    if i==pre:
      continue
    dfs(n,i)
    b[n]*=w[i]
    b[n]%=mod
    w[n]*=b[i]+w[i]
    w[n]%=mod

dfs(0,1)
print((b[1]+w[1])%mod)

Solution (Python):

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


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)

Solution (Python):

from collections import defaultdict
import sys

sys.setrecursionlimit(10**6)


N = int(input())
g = [set() for _ in range(N+1)]

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)

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

n = int(input())

neighbor = [[] for _ in range(n + 1)]

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

mod = 10**9 + 7
dp = [[0] * 2 for _ in range(n + 1)]


def dfs(i, bw, p):
    if dp[i][bw] != 0:
        return dp[i][bw]

    dp[i][bw] = 1
    for j in neighbor[i]:
        if j == p:
            continue

        if bw == 0:  
            dp[i][0] = (dp[i][0] * dfs(j, 1, i)) % mod
        else:  
            dp[i][1] = (dp[i][1] * (dfs(j, 0, i) + dfs(j, 1, i))) % mod

    return dp[i][bw]


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

Solution (Python):
from collections import deque
n=int(input())
mod=10**9+7
G=[[] for i in range(n)]
for i in range(n-1):
  x,y=map(int,input().split())
  x=x-1
  y=y-1
  G[x].append(y)
  G[y].append(x)
A=[0]*n
A[0]=1
B=deque([0])
C=[0]
GG=[[] for i in range(n)]
while len(B)>0:
  v=B[0]
  B.popleft()
  for i in range(len(G[v])):
    if A[G[v][i]]==0:
      A[G[v][i]]=1
      B.append(G[v][i])
      C.append(G[v][i])
      GG[v].append(G[v][i])
C=C[::-1]
dp=[[0]*2 for i in range(n)]
for i in range(n):
  if len(GG[C[i]])==0:
    dp[C[i]]=[1,1]
  else:
    a=1
    b=1
    for j in range(len(GG[C[i]])):
      a=(a*(dp[GG[C[i]][j]][0]+dp[GG[C[i]][j]][1]))%mod
      b=(b*dp[GG[C[i]][j]][0])%mod
    dp[C[i]][0]=a
    dp[C[i]][1]=b
print((dp[0][0]+dp[0][1])%mod)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i 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)
Ans=[]
inf=10**6


Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)
 

from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

C1,C2=[0]*n,[0]*n
for i in reversed(range(n)):
  v=TS[i]
  if len(edge[v])==1 and Par[v]!=-1:
    C1[v]=1
    C2[v]=1
  else:
    c1,c2=1,1
    for g in edge[v]:
      if g==Par[v]:
        continue
      else:
        c1=((C1[g]+C2[g])*c1)%mod
        c2=(C1[g]*c2)%mod
    C1[v]=c1
    C2[v]=c2
print((C1[0]+C2[0])%mod)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i 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)
Ans=[]
inf=10**6


Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)
 

from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

C1,C2=[0]*n,[0]*n
for i in reversed(range(n)):
  v=TS[i]
  if len(edge[v])==1 and Par[v]!=-1:
    C1[v]=1
    C2[v]=1
  else:
    c1,c2=1,1
    for g in edge[v]:
      if g==Par[v]:
        continue
      else:
        c1*=C1[g]+C2[g]
        c2*=C1[g]
    C1[v]=c1%mod
    C2[v]=c2%mod
print((C1[0]+C2[0])%mod)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i 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)
Ans=[]
inf=10**6


Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)
 

from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

C1,C2=[0]*n,[0]*n
for i in reversed(range(n)):
  v=TS[i]
  if len(edge[v])==1 and Par[v]!=-1:
    C1[v]=1
    C2[v]=1
  else:
    c1,c2=1,1
    for g in edge[v]:
      if g==Par[v]:
        continue
      else:
        c1*=C1[g]+C2[g]
        c2*=C1[g]
    C1[v]=c1%mod
    C2[v]=c2%mod
print((C1[0]+C2[0])%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**5 + 1)

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

M = 10**9 + 7
def mod(v):
    if v >= M:
        return v % M
    return v

def dfs(node=0, prev=-1):
    cnt = [1, 1]
    for c in graph[node]:
        if c == prev:
            continue
        w, b = dfs(c, node)
        cnt[0] = mod(cnt[0] * (w + b))
        cnt[1] = mod(cnt[1] * w)
    
    return cnt

print(mod(sum(dfs())))

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

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

def dfs(prev, u):
    for v in G[u]:
        if v == prev:
            continue
        dfs(u, v)
        black[u] *= white[v]
        black[u] %= mod
        white[u] *= black[v] + white[v]
        white[u] %= mod

dfs(0, 1)
print((black[1] + white[1]) % mod)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return list(map(list, input().split()))
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = 1e10

"""
URL: https://atcoder.jp/contests/dp/tasks/dp_p

P - Independent Set / 
実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 
100 点

問題文
N 頂点の木があります。 
頂点には 1,2,…,N と番号が振られています。
各 i (1≤i≤N−1) について、i 番目の辺は頂点 xi と yi を結んでいます。

太郎君は、各頂点を白または黒で塗ることにしました。 ただし、隣り合う頂点どうしをともに黒で塗ってはいけません。

頂点の色の組合せは何通りでしょうか？ 
10**9+7 で割った余りを求めてください。

制約
入力はすべて整数である。
1≤N≤10**5
1≤xi,yi≤N
与えられるグラフは木である。

"""


def solve():
    n = II()
    edg = [[] for _ in range(n)]
    for _ in range(n - 1):
        x, y = LI_()
        edg[x].append(y)
        edg[y].append(x)
    black = [1] * n
    white = [1] * n
    rank = [-1] * n
    rank[0] = [0, None]
    q = deque()
    q.append([0, -1])
    while q:
        node, pre = q.pop()
        for nex in edg[node]:
            if nex == pre:
                continue
            rank[nex] = [rank[node][0] + 1, node]
            q.appendleft((nex, node))

    ans = []
    for i in range(n):
        ans.append((-rank[i][0], rank[i][1], i))
    ans.sort()
    for _, i, j in ans[:-1]:
        black[i] *= white[j]
        white[i] *= white[j] + black[j]
        black[i] %= mod
        white[i] %= mod
    print((white[0] + black[0]) % mod)
    return



if __name__ == '__main__':
    solve()

Solution (Python):
MOD = 10**9 + 7
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)

preorder = [-1] * N 
dp = [[1] * 2 for _ in range(N)]
stack = [(0, -1, 0)] 
pre_num = 0 
while stack:
    v, p, st = stack.pop()
    if st == 0 and preorder[v] < 0: 
        preorder[v] = pre_num
        pre_num += 1
        n_children = 0
        for u in E[v]:
            if preorder[u] >= 0:
                continue
            if n_children == 0:
                stack += [(v, p, 2), (u, v, 0)]
                n_children += 1
            else:
                stack += [(v, p, 1), (u, v, 0)]
                n_children += 1
        if n_children == 0 and p != -1: 
            dp[p][0] *= dp[v][0] + dp[v][1]
            dp[p][0] %= MOD
            dp[p][1] *= dp[v][0]
            dp[p][1] %= MOD
    elif st == 0 and preorder[v] >= 0: 
        continue
    elif st == 1: 
        continue
    else: 
        if p != -1:
            dp[p][0] *= dp[v][0] + dp[v][1]
            dp[p][0] %= MOD
            dp[p][1] *= dp[v][0]
            dp[p][1] %= MOD
print((dp[0][0] + dp[0][1]) % MOD)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline

    sys.setrecursionlimit(10 ** 8)

    MOD = 10 ** 9 + 7

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

    
    
    
    C = [False] * (N + 1) 

    def calc(x): 
        C[x] = True

        b = 1
        w = 1

        for next_ in G[x]:
            if C[next_]:
                continue
            tmp_b, tmp_w = calc(next_)
            b = (b * tmp_b) % MOD
            w = (w * tmp_w) % MOD
        
        
        return w, (b + w) % MOD

    tmp, ans = calc(1)
    print (ans)
    

if __name__ == '__main__':
    main()

Solution (Python):
N=int(input())
xy=[list(map(int,input().split())) for i in range(N-1)]
mod=10**9+7

data=[[] for i in range(N+1)]
for x,y in xy:
    data[x].append(y)
    data[y].append(x)

parent=[-1]*(N+1)
child=[0]*(N+1)

parent[1]=1
que=[1]
while que:
    u=que.pop()
    for v in data[u]:
        if parent[v]==-1:
            parent[v]=u
            que.append(v)
            child[u]+=1

dp=[[1,1] for i in range(N+1)]
que=[]
for i in range(1,N+1):
    if child[i]==0:
        que.append(i)

while que:
    u=que.pop()
    for v in data[u]:
        if parent[u]==v:
            child[v]-=1
            if child[v]==0:
                que.append(v)
            continue
        dp[u][1]=dp[u][1]*dp[v][0]%mod
        dp[u][0]=dp[u][0]*(dp[v][0]+dp[v][1])%mod

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

Solution (Python):

import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
sys.setrecursionlimit(10**7)

def dfs(node,prenode,black):
  if black and B[node]!= -1: return B[node]
  elif not black and W[node]!= -1: return W[node]
  res = 1
  for vi in G[node]:
    if vi == prenode: continue
    tmp = 0
    tmp += dfs(vi,node,False)
    if not black:
      tmp += dfs(vi,node,True)
    res = res * tmp % mod
  if black:
    B[node] = res
  else:
    W[node] = res
  return res

n = int(input())
B = [-1]*n
W = [-1]*n
G=[[] for i in range(n)]
for i in range(n-1):
  x,y = map(int,input().split())
  x-=1;y-=1
  G[x].append(y)
  G[y].append(x)
dfs(0,-1,True)
dfs(0,-1,False)
print((B[0]+W[0])%mod)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
MOD = 10**9+7
N = int(input())
G = [[] for _ in range(N)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)


def tree(S):
    for g in G[S]:
        G[g].remove(S)
        tree(g)


tree(0)

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


def main(S, f):
    if dp[S][f] != -1:
        return dp[S][f]
    ret = 1
    if f == 1:
        for g in G[S]:
            ret *= main(g, 0)
            ret %= MOD
    else:
        for g in G[S]:
            ret *= main(g, 0)+main(g, 1)
            ret %= MOD
    dp[S][f] = ret
    return ret


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

Solution (Python):

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
 
N = int(input())
edge = [[] for _ in range(N + 1)]
mod = 10 ** 9 + 7
 
for _ in range(N - 1):
    a, b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

root = 1
 
black = [1] * (N + 1)
white = [1] * (N + 1)
under = [[] for _ in range(N+1)]
seen = [False] * (N + 1)


node = [root]
while node:
    s = node.pop()
    seen[s] = True
    for t in edge[s]:
        if seen[t]:
            continue
        node.append(t)
        under[s].append(t)

def BW(s):
    if not under[s]: 
        return
    for t in under[s]:
        BW(t)
        white[s] = (white[s] * (white[t] + black[t])) % mod
        black[s] = (black[s] * white[t]) % mod

BW(root)
ans = white[root]+black[root]
print(ans%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**5)

def main():
    n=int(input())
    nodes=[[]for _ in range(n)]
    mod=10**9+7

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

    def pick(n,excep=-1):
        white=1
        black=1
        for node in nodes[n]:
            if excep==node:
                continue
            p=pick(node,n)
            white=(white*(p[0]+p[1]))%mod
            black=(black*p[0])%mod
        return [white,black]
    p=pick(0)
    print(sum(p)%mod)
main()

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(10**9)

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 
dp2 = [0]*N 



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: 
      dp1[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]



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: 
      dp2[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)