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:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)

def dfs(v, pv, c):
    if memo[v][c]!=-1:
        return memo[v][c]
        
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if c==0:
            res *= dfs(nv, v, 0)+dfs(nv, v, 1)
        else:
            res *= dfs(nv, v, 0)
        
        res %= MOD
    
    return res

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)

memo = [[-1]*2 for _ in range(N)]
MOD = 10**9+7

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

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[i] := 頂点iを白にしてその先の全体を塗り分ける通り数
dp1 = [1] * N
# dp2[i] := 頂点iを黒にしてその先の全体を塗り分ける通り数
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)

Submission status: Time Limit Exceeded

Solution code:
#木DP, 木上の数え上げ

#前処理
#隣接リストを作る
#隣接頂点が最も多い頂点を根にして木を作る

#




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

    #inf = 10**17
    mod = 10**9 + 7

    #頂点:0~N-1
    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[i]:iの子
    c = [[] for _ in range(N)]
    #x:i, y:iの親
    def ch(x, y):
        for e in adj[x]:
            if e == y:
                continue
            c[x].append(e)
            ch(e, x)
    ch(root, -1)

    #dp[i][b, w]:iを根とする木の場合の数
    #bはiが黒, wはiが白のとき
    dp = [[-1, -1] for _ in range(N)]

    #xが葉の場合は1が返される
    #dp[x][0=b]を返す
    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]

    #dp[x][0=w]を返す
    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()

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
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)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod=10**9+7
N=int(input())
A=[list(map(int, input().split())) for _ in range(N-1)]
G=[ [] for _ in range(N+1)]
for a,b in A:
  G[a].append(b)
  G[b].append(a)
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)

Submission status: Time Limit Exceeded

Solution code:

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)

Submission status: Time Limit Exceeded

Solution code:

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)

Submission status: Time Limit Exceeded

Solution code:
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:  # black
            dp[i][0] = (dp[i][0] * dfs(j, 1, i)) % mod
        else:  # white
            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)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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
与えられるグラフは木である。

"""

#solve
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]
    def f(node, pre):
        for nex in edg[node]:
            if nex == pre:
                continue
            rank[nex] = [rank[node][0] + 1, node]
            f(nex, node)
        return

    f(0, -1)
    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


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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
与えられるグラフは木である。

"""

#solve
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
    def f(node, pre):
        for nex in edg[node]:
            if nex == pre:
                continue
            f(nex,node)
            black[node] *= white[nex]
            white[node] *= (white[nex] + black[nex])%mod
            black[node] %= mod
            white[node] %= mod
        return
    f(0, -1)
    print((white[0] + black[0]) % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
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
与えられるグラフは木である。

"""

#solve
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
    def f(node, pre):
        for nex in edg[node]:
            if nex == pre:
                continue
            f(nex,node)
            black[node] *= white[nex]
            white[node] *= white[nex] + black[nex]
            black[node] %= mod
            white[node] %= mod
        return
    f(0, -1)
    print((white[0] + black[0]) % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

    # B = [0] * (N + 1) #自分自身が黒色の時
    # W = [0] * (N + 1) #自分自身が白色の時
    # T = [0] * (N + 1) #B + W
    C = [False] * (N + 1) #訪れたことのチェック

    def calc(x): #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
        # B[x] = b
        # W[x] = w
        return w, (b + w) % MOD

    tmp, ans = calc(N)
    print (ans)
    # print ((B[1] + W[1]) % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

    # B = [0] * (N + 1) #自分自身が黒色の時
    # W = [0] * (N + 1) #自分自身が白色の時
    # T = [0] * (N + 1) #B + W
    C = [False] * (N + 1) #訪れたことのチェック

    def calc(x): #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
        # B[x] = b
        # W[x] = w
        return w, (b + w) % MOD

    tmp, ans = calc(1)
    print (ans)
    # print ((B[1] + W[1]) % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

# B = [0] * (N + 1) #自分自身が黒色の時
# W = [0] * (N + 1) #自分自身が白色の時
# T = [0] * (N + 1) #B + W
C = [False] * (N + 1) #訪れたことのチェック

def calc(x): #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
    # B[x] = b
    # W[x] = w
    return w, (b + w) % MOD

tmp, ans = calc(1)
print (ans)
# print ((B[1] + W[1]) % MOD)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)
#    print(Order)
    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="#":
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="#":
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j]*P[i]
            dp[i+1][j] += dp[i][j]*(1-P[i])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

def examJ():
    N = I()
    A = LI()
    dp = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
    S = Counter(A)
    print(S)
    dp[S[1]][S[2]][S[3]] = 0
    que = deque()
    que.append((S[1],S[2],S[3]))
    used = defaultdict(set)
    while(que):
        n1,n2,n3 = que.popleft()
        if used[(n1,n2,n3)]:
            continue
        used[(n1,n2,n3)] = True
        now = n1+n2+n3
        if n1>0:
            dp[n1-1][n2][n3] += dp[n1][n2][n3] + N/now * n1/now
            que.append((n1-1, n2, n3))
        if n2>0:
            dp[n1+1][n2-1][n3] += dp[n1][n2][n3] + N/now * n2/now
            que.append((n1+1,n2-1,n3))
        if n3>0:
            dp[n1][n2+1][n3-1] += dp[n1][n2][n3] + N/now * n3/now
            que.append((n1,n2+1,n3-1))
#    print(dp)
    ans = dp[0][0][0]
    print(ans)
    return

def examK():
    N, K = LI()
    A = LI()
    dp = [-1]*(K+1)
    for i in range(1,K+1):
        flag = False
        for a in A:
            if a>i:
                break
            if dp[i-a]==-1:
                flag = True
                break
        if flag:
            dp[i] = 1
#    print(dp)
    ans = dp[K]
    if ans==1:
        print("First")
    else:
        print("Second")
    return

def examM():
    N, K = LI()
    A = LI()
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        cum = [0]*(K+1)
        cum[0] = dp[i][0]
        for c in range(K):
            cum[c+1] = cum[c] + dp[i][c+1]
        for j in range(K+1):
            if j<=A[i]:
                dp[i+1][j] = cum[j]
            else:
                dp[i+1][j] = cum[j] - cum[j-A[i]-1]
            dp[i+1][j] %=mod
#    print(dp)
    ans = dp[N][K]%mod
    print(ans)
    return

def examP():
    def dfs_dp(n,s,fords,visited):
        W = 1; B = 1
        visited[s] = True
        for v in fords[s]:
            if visited[v]:
                continue
            cur = dfs_dp(n, v, fords,visited)
            W *= sum(cur)
            B *= cur[0]
            W %= mod
            B %= mod
#        print(s,W,B)
        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()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def examA():
    N = I()
    H = LI()
    dp = [inf]*(N)
    dp[0] = 0
    for i in range(N-1):
        dp[i+1] = min(dp[i+1],dp[i]+abs(H[i+1]-H[i]))
        if i<N-2:
            dp[i + 2] = min(dp[i + 2], dp[i]+abs(H[i + 2] - H[i]))
    ans = dp[-1]
    print(ans)
    return

def examB():
    N, K = LI()
    H = LI()
    dp = [inf]*N
    dp[0] = 0
    for i in range(N):
        for k in range(1,K+1):
            if i+k>=N:
                break
            if dp[i+k]>dp[i]+abs(H[i+k]-H[i]):
                dp[i+k] = dp[i]+abs(H[i+k]-H[i])
    ans = dp[-1]
    print(ans)
    return

def examC():
    N = I()
    A = [0]*N; B = [0]*N; C = [0]*N
    for i in range(N):
        A[i],B[i],C[i] = LI()
    dp = [[0]*3 for _ in range(N+1)]
    for i in range(N):
        dp[i+1][0] = max(dp[i][1],dp[i][2]) + A[i]
        dp[i + 1][1] = max(dp[i][0], dp[i][2]) + B[i]
        dp[i + 1][2] = max(dp[i][1], dp[i][0]) + C[i]
    ans = max(dp[N])
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    # LCS
    S = SI(); N = len(S)
    T = SI(); M = len(T)
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j], dp[i][j+1])

    i = N; j = M
    ans = []
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            ans.append(S[i-1])
            i -= 1
            j -= 1
    print("".join(ans[::-1]))
    return

def examG():
    # http://zehnpaard.hatenablog.com/entry/2018/06/26/201512
    # トポロジカルソート
    def topological_sort(n,outs,ins):
        q = deque(v1 for v1 in range(n) if ins[v1] == 0)
        res = []
        while q:
            v1 = q.popleft()
            res.append(v1)
            for v2 in outs[v1]:
                ins[v2] -= 1
                if ins[v2] == 0:
                    q.append(v2)
        return res
    N, M = LI()
    V = [[]for _ in range(N)]
    start = [0]*N
    for _ in range(M):
        x,y = LI()
        x -= 1; y -= 1
        V[x].append(y)
        start[y] += 1
    Order = topological_sort(N, V, start)
#    print(Order)
    dp = [0]*N
    for i in Order:
        for v in V[i]:
            dp[v] = max(dp[v],dp[i]+1)
    ans = max(dp)
    print(ans)
    return

def examH():
    H, W = LI()
    A = [SI() for _ in range(H)]
    dp = [[0]*W for _ in range(H)]
    dp[0][0] = 1
    for i in range(H):
        for j in range(W):
            if A[i][j]=="#":
                continue
            dp[i][j] %=mod
            if i+1<H and dp[i+1][j]!="#":
                dp[i+1][j] +=dp[i][j]
            if j+1<W and dp[i][j+1]!="#":
                dp[i][j+1] +=dp[i][j]
    ans = dp[-1][-1]
    print(ans)
    return

def examI():
    N = I()
    P = LFI()
    dp = [[0]*(N+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        for j in range(i+1):
            dp[i+1][j+1] += dp[i][j]*P[i]
            dp[i+1][j] += dp[i][j]*(1-P[i])
    ans = 0
    for v in dp[N][(1+N//2):]:
        ans += v
    print(ans)
    return

def examJ():
    N = I()
    A = LI()
    dp = [[[0]*(N+1) for _ in range(N+1)]for _ in range(N+1)]
    S = Counter(A)
    print(S)
    dp[S[1]][S[2]][S[3]] = 0
    que = deque()
    que.append((S[1],S[2],S[3]))
    used = defaultdict(set)
    while(que):
        n1,n2,n3 = que.popleft()
        if used[(n1,n2,n3)]:
            continue
        used[(n1,n2,n3)] = True
        now = n1+n2+n3
        if n1>0:
            dp[n1-1][n2][n3] += dp[n1][n2][n3] + N/now * n1/now
            que.append((n1-1, n2, n3))
        if n2>0:
            dp[n1+1][n2-1][n3] += dp[n1][n2][n3] + N/now * n2/now
            que.append((n1+1,n2-1,n3))
        if n3>0:
            dp[n1][n2+1][n3-1] += dp[n1][n2][n3] + N/now * n3/now
            que.append((n1,n2+1,n3-1))
#    print(dp)
    ans = dp[0][0][0]
    print(ans)
    return

def examK():
    N, K = LI()
    A = LI()
    dp = [-1]*(K+1)
    for i in range(1,K+1):
        flag = False
        for a in A:
            if a>i:
                break
            if dp[i-a]==-1:
                flag = True
                break
        if flag:
            dp[i] = 1
#    print(dp)
    ans = dp[K]
    if ans==1:
        print("First")
    else:
        print("Second")
    return

def examM():
    N, K = LI()
    A = LI()
    dp = [[0]*(K+1) for _ in range(N+1)]
    dp[0][0] = 1
    for i in range(N):
        cum = [0]*(K+1)
        cum[0] = dp[i][0]
        for c in range(K):
            cum[c+1] = cum[c] + dp[i][c+1]
        for j in range(K+1):
            if j<=A[i]:
                dp[i+1][j] = cum[j]
            else:
                dp[i+1][j] = cum[j] - cum[j-A[i]-1]
            dp[i+1][j] %=mod
#    print(dp)
    ans = dp[N][K]%mod
    print(ans)
    return

def examP():
    def dfs_dp(n,s,fords,visited):
        W = 1; B = 1
        visited[s] = True
        for v in fords[s]:
            if visited[v]:
                continue
            cur = dfs_dp(n, v, fords,visited)
            W *= sum(cur)
            B *= cur[0]
#        print(s,W,B)
        W %= mod
        B %= mod
        return (W,B)
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        x,y = LI()
        x -=1; y -=1
        V[x].append(y)
        V[y].append(x)
    visited = [False]*N
    ans = dfs_dp(N,0,V,visited)
    print(sum(ans)%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()

"""

"""