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):
import sys
sys.setrecursionlimit(500000)

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

def f(x, prev):
    if memo_f[x]:
        return memo_f[x]
    memo_f[x] = 1
    for i in node[x]:
        if i == prev:
            continue
        memo_f[x] = (memo_f[x] * g(i, x)) % mod
    memo_f[x] = (memo_f[x] + g(x, prev)) % mod
    return memo_f[x]

def g(x, prev):
    if memo_g[x]:
        return memo_g[x]
    memo_g[x] = 1
    for i in node[x]:
        if i == prev:
            continue
        memo_g[x] = (memo_g[x] * f(i, x)) % mod
    return memo_g[x]

print(f(0, -1))

Solution (Python):
import sys


sys.setrecursionlimit(100000)
MOD = 10**9 + 7
n = int(input())
tree = [[] for i in range(n)]
for i in range(n-1):
    tmp1, tmp2 = map(int, input().split())
    tree[tmp1 - 1].append(tmp2 - 1) 
    tree[tmp2 - 1].append(tmp1 - 1)
visited = [False]*n

def dfs(i):
    visited[i] = True
    if all([visited[j] for j in tree[i]]):
        return 1, 1  
    else:
        ans1 = 1
        ans2 = 1
        for j in tree[i]:
            if not visited[j]:
                tmp1, tmp2 = dfs(j)
                ans1 *= tmp2
                ans2 *= (tmp1 + tmp2)
                ans1 %= MOD
                ans2 %= MOD
        return ans1, ans2  

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

Solution (Python):
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def bw(i, p):
    if dp[i] != [0, 0]:
        return dp[i]
    b = w = 1
    for ii in h[i]:
        if ii == p: continue
        bwi = bw(ii,i)
        w *= (bwi[0] + bwi[1])
        b *= bwi[1]
        w %= md
        b %= md
    dp[i] = [b, w]
    return [b, w]


md = 10 ** 9 + 7
n = int(input())
if n == 1:
    print(2)
    exit()
h = {}
for _ in range(n - 1):
    a, b = map(int, input().split())
    h.setdefault(a, [])
    h.setdefault(b, [])
    h[a] += [b]
    h[b] += [a]
dp = [[0, 0] for _ in range(n + 1)]
b, w = bw(1, 1)
print((b + w) % md)

Solution (Python):
from collections import deque

MOD = 10**9 + 7


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        adj[x-1].add(y-1)
        adj[y-1].add(x-1)
    memo = [[0] * 2 for _ in range(N)]
    q = deque([(0, -1)])
    while len(q):
        cur, prev = q.pop()
        adjs = set([x for x in adj[cur] if x != prev])
        if len(adjs) == 0:
            memo[cur][0] = 1
            memo[cur][1] = 1
            continue
        rec = []
        black = 1
        white = 1
        for a in adjs:
            if memo[a][0] != 0:
                black = (black * memo[a][0]) % MOD
                white = (white * (memo[a][0] + memo[a][1])) % MOD
            else:
                rec += [(a, cur)]
        if len(rec):
            q.append((cur, prev))
            for r in rec:
                q.append(r)
        else:
            memo[cur][0] = white
            memo[cur][1] = black
    print(sum(memo[0]) % MOD)


if __name__ == "__main__":
    main()

Solution (Python):


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

mod = int(1e9 + 7)

def f(r):
    if v[r]:
        return(False)
    v[r] = 1
    dpr = dp[r]
    dpr[0] = 1
    dpr[1] = 1
    for j in e[r]:
        if f(j):
            dpj = dp[j]
            dpr[0] = dpr[0] * (dpj[0] + dpj[1]) % mod
            dpr[1] = dpr[1] * dpj[0] % mod
    return(True)

n = int(input()) 
e = [set() for _ in range(n)]
for x, y in [map(int, input().split()) for _ in range(n - 1)]:
    e[x - 1].add(y - 1)
    e[y - 1].add(x - 1)
v = [0] * n
dp = [[0] * 2 for _ in range(n)]
f(0)
print((dp[0][0] + dp[0][1]) % mod)

Solution (Python):
import sys

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

n = int(input())

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

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

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

print(treeDP(0)[0])

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import deque
mod=10**9+7
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
root=-1
l=-1
for i in range(n):
    if len(edges[i])>l:
        root=i
        l=len(edges[i])
children=[[] for _ in range(n)]
V=[]
q=deque([root])
used=[False]*n
used[root]=True
while q:
    par=q.popleft()
    C=children[par]
    V.append(par)
    for v in edges[par]:
        if used[v]:
            continue
        C.append(v)
        used[v]=True
        q.append(v)
DP=[None for _ in range(n)]
for par in V[::-1]:
    white,black=1,1
    for c in children[par]:
        w,b=DP[c]
        white*=w+b
        white%=mod
        black*=w
        black%=mod
    DP[par]=(white,black)
print(sum(DP[root])%mod)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import deque
mod=10**9+7
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
children=[[] for _ in range(n)]
V=[]
q=deque([0])
used=[False]*n
used[0]=True
while q:
    par=q.popleft()
    C=children[par]
    V.append(par)
    for v in edges[par]:
        if used[v]:
            continue
        C.append(v)
        used[v]=True
        q.append(v)
DP=[None for _ in range(n)]
for par in V[::-1]:
    white,black=1,1
    for v in children[par]:
        w,b=DP[v]
        white*=w+b
        white%=mod
        black*=w
        black%=mod
    DP[par]=(white,black)
print(sum(DP[0])%mod)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import deque
mod=10**9+7
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
children=[[] for _ in range(n)]
V=[]
q=deque([0])
used=[False]*n
used[0]=True
while q:
    par=q.popleft()
    C=children[par]
    V.append(par)
    for v in edges[par]:
        if used[v]:
            continue
        C.append(v)
        used[v]=True
        q.append(v)
DP=[None for _ in range(n)]
for par in V[::-1]:
    white,black=1,1
    for v in children[par]:
        w,b=DP[v]
        white*=w+b
        white%=mod
        black*=w
        black%=mod
    DP[par]=(white,black)
print(sum(DP[0])%mod)

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
mod=10**9+7
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
C=[[] for _ in range(n)]

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

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

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

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

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**7)
mod=10**9+7
n=int(input())
edges=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(int,input().split())
    edges[x-1].append(y-1)
    edges[y-1].append(x-1)
root=-1
l=-1
for i in range(n):
    if len(edges[i])>l:
        root=i
        l=len(edges[i])
C=[[] for _ in range(n)]

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

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

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

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
mod = 10**9+7
p = -1
le = -1
for i in range(n):
    if len(edge[i]) > le:
        p = i

c = [[] for i in range(n)]
def ch(x,y):
    for e in edge[x]:
        if e == y:
            continue
        c[x].append(e)
        ch(e,x)
ch(p,-1)


dp = [[-1,-1] for i in range(n)]


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


def whi(x):
    if dp[x][1] != -1:
        return dp[x][1]
    res = 1
    for e in c[x]:
        res = ( (bla(e)+whi(e))%mod )*res%mod
    dp[x][1] = res
    return res
print((bla(p)+whi(p))%mod)

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

n = int(input())
graph = [[] for _ in range(n)]

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

mod = 10**9 + 7

memo = [0] * n


dp = [[0, 0] for _ in range(n+1)]


def dfs(v):
    if memo[v] != 0:
        return
    memo[v] = 1
    dp[v][0] = 1
    dp[v][1] = 1
    for nv in graph[v]:
        if memo[nv] != 0:
            continue
        dfs(nv)
        dp[v][0] *= (dp[nv][0] + dp[nv][1])
        dp[v][0] %= mod

        dp[v][1] *= dp[nv][0]
        dp[v][1] %= mod

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

Solution (Python):

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n = int(input())
X = [[int(i) for i in input().split()] for j in range(n-1)]
p = 10 ** 9 + 7

V = [[] for i in range(n+1)]
for x, y in X:
    V[x].append(y)
    V[y].append(x)

w = 0
b = 1
DP = [[0] *  2 for i in range(n+1)]

def dfs(i):
    if DP[i] != [0, 0]:
        return 0
    DP[i][w] = 1
    DP[i][b] = 1
    for v in V[i]:
        if dfs(v) == 0:
            continue
        DP[i][w] *= DP[v][w] + DP[v][b]
        DP[i][b] *= DP[v][w]
        DP[i][w] %= p
        DP[i][b] %= p

dfs(1)
print(sum(DP[1]) % p)

Solution (Python):

from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

n = int(input())
X = [[int(i) for i in input().split()] for j in range(n-1)]
p = 10 ** 9 + 7

V = [[] for i in range(n+1)]
for x, y in X:
    V[x].append(y)
    V[y].append(x)

root = 0
for i, v in enumerate(V):
    if len(v) == 1:
        root = i
        break

w = 0
b = 1
DP = [[0] *  2 for i in range(n+1)]

def dfs(i):
    if DP[i] != [0, 0]:
        return 0
    DP[i][w] = 1
    DP[i][b] = 1
    for v in V[i]:
        if dfs(v) == 0:
            continue
        DP[i][w] *= DP[v][w] + DP[v][b]
        DP[i][b] *= DP[v][w]
        DP[i][w] %= p
        DP[i][b] %= p

dfs(root)
print(sum(DP[root]) % p)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

X = [[] for _ in range(N)]

for _ in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
    
P = [-1] * N
def dfs(i):
    for j in X[i]:
        if j != 0 and P[j] < 0:
            P[j] = i
            dfs(j)

dfs(0)

for i in range(N):
    if i != 0:
        X[i].remove(P[i])

ans = 0
B = [0] * N
W = [0] * N

def dfs2(i):
    _ansb = 1
    _answ = 1
    for j in X[i]:
        __ansb, __answ = dfs2(j)
        _ansb *= __answ
        _answ *= (__ansb+__answ)
        _ansb %= MOD
        _answ %= MOD
    
    return (_ansb, _answ)

print(sum(dfs2(0)) % MOD)

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
n = int(input())
m = 1000000007
d = [[-1 for i in range(100000)] for j in range(2)]
v = [[] for j in range(100000)]

def f(x, c, p):
    if d[c][x] != -1: return d[c][x]
    d[c][x] = 1
    for i in v[x]:
        if i != p:
            t = f(i, 0, x)
            if c == 0: t += f(i, 1, x)
            t %= m
            d[c][x] = (d[c][x]*t)%m
    return d[c][x]

for i in range(n-1):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    v[x].append(y)
    v[y].append(x)
ans = (f(0, 0, -1) + f(0, 1, -1))%m
print(ans)

Solution (Python):


MOD = 1000000007

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

bfs = [0]
mark = [False] * n
mark[0] = True
for i in range(n - 1):
    for v in tree[bfs[i]]:
        if not mark[v]:
            bfs.append(v)
            mark[v] = True

dpw = [1] * n
dpb = [1] * n
mark = [False] * n
for i in range(n - 1, -1, -1):
    u = bfs[i]
    mark[u] = True
    for v in tree[u]:
        if mark[v]:
            dpb[u] = dpb[u] * dpw[v] % MOD
            dpw[u] = dpw[u] * (dpw[v] + dpb[v]) % MOD
print((dpw[bfs[0]] + dpb[bfs[0]]) % MOD)

Solution (Python):

import sys
sys.setrecursionlimit(10000000)
N = int(input())
from collections import defaultdict
MOD = 10**9 + 7


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

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

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

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

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

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

check=[0]*(N+1)

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

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

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

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

    check[x]=1
        

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

        return b,w

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    e = collections.defaultdict(set)
    for _ in range(n-1):
        a,b = LI()
        e[a].add(b)
        e[b].add(a)

    def f(i, p):
        w = 1
        b = 1
        for c in e[i]:
            if c == p:
                continue
            ww,bb = f(c, i)
            w *= (ww+bb)
            w %= mod
            b *= ww
            b %= mod
        return (w,b)

    r = f(1,-1)

    return sum(r) % mod


print(main())

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(10**7)
MOD = 10**9+7
n = int(input())
edges = [[] for _ in range(n)]
for _ in range(n-1):
	x, y = map(int, input().split())
	edges[x-1].append(y-1)
	edges[y-1].append(x-1)

dp = [[1 for _ in range(2)] for _ in range(n)]


def dfs(cur, par):
	for e in edges[cur]:
		if e == par:
			continue
		dfs(e, cur)
		dp[cur][0] = (dp[cur][0] * (dp[e][0]+dp[e][1])) % MOD
		dp[cur][1] = (dp[cur][1] * dp[e][0]) % MOD

	return

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

Solution (Python):
from collections import deque

MOD = 10**9 + 7

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

I = []
que = deque([0])
used = [0]*N; used[0] = 1
while que:
    v = que.popleft()
    gv = G0[v]
    I.append(v)
    for w in G[v]:
        if used[w]:
            continue
        gv.append(w)
        used[w] = 1
        que.append(w)
dp = [None for i in range(N)]
for v in reversed(I):
    r0 = r1 = 1
    for w in G0[v]:
        a, b = dp[w]
        r0 = (r0 * (a + b)) % MOD
        r1 = (r1 * a) % MOD
    dp[v] = (r0, r1)
print(sum(dp[0]) % MOD)

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

MOD = 10**9 + 7

def rec(vNow, vPar):
    W, B = 1, 1
    for v2 in adjL[vNow]:
        if v2 == vPar: continue
        W2, B2 = rec(v2, vNow)
        W = (W * (W2+B2)) % MOD
        B = (B * W2) % MOD
    return (W, B)

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

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

Solution (Python):
from collections import deque

MOD = 10**9 + 7

N = int(input())
adjL = [[] for v in range(N)]
degs = [0] * N
for _ in range(N-1):
    x, y = map(int, input().split())
    adjL[x-1].append(y-1)
    adjL[y-1].append(x-1)
    degs[x-1] += 1
    degs[y-1] += 1

dpWhite = [1] * N
dpBlack = [1] * N
vNow = 0
Q = deque([v for v in range(N) if degs[v] == 1])
while Q:
    vNow = Q.popleft()
    if degs[vNow] == 0: break
    dpW, dpB = dpWhite[vNow], dpBlack[vNow]
    for v2 in adjL[vNow]:
        if degs[v2] == 0: continue
        dpWhite[v2] *= dpW + dpB
        dpWhite[v2] %= MOD
        dpBlack[v2] *= dpW
        dpBlack[v2] %= MOD
        degs[v2] -= 1
        if degs[v2] == 1:
            Q.append(v2)
    degs[vNow] = 0

print((dpWhite[vNow] + dpBlack[vNow]) % MOD)

Solution (Python):
from collections import deque
n = int(input())
mod = 10**9+7
g = [[] for i in range(n)]
g2 = [[] for i in range(n)]
for i in range(n-1):
  x,y = list(map(int,input().split()))
  g[x-1].append(y-1)
  g[y-1].append(x-1)
dp = [[0]* 2 for i in range(n)]
hukasa = [float("inf")]*n
hukasa[0] = 0
def dfs(x,y):
  for i in g[x]:
    if hukasa[i] > y+1:
      hukasa[i] = y+1
      que.append([i,y+1])
      g2[x].append(i)
que = deque([])
que.append([0,0])
while que:
  x,y = que.popleft()
  dfs(x,y)
for i in range(n):
  hukasa[i] = [hukasa[i],i]
hukasa.sort(key = lambda x:-x[0])
for i,j in hukasa:
  if len(g2[j]) == 0:
    dp[j][0] = dp[j][1] = 1
    continue
  tmp = 1
  tmp2 = 1
  for k in g2[j]:
    tmp *= dp[k][0]
    tmp2 *= (dp[k][0]+dp[k][1])
    tmp %= mod
    tmp2 %= mod
  dp[j][1] = tmp
  dp[j][0] = tmp2
print((dp[0][0]+dp[0][1])%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
N=int(input())
table=[[] for i in range(N)]
for i in range(N-1):
    w,v=map(int,input().split())
    table[w-1].append(v-1)
    table[v-1].append(w-1)
mod=10**9+7
f=[-1]*N
g=[-1]*N
def ser(par,son):
    if f[son]!=-1 and g[son]!=-1:
        return f[son],g[son]
    s=1
    t=1
    for grason in table[son]:
        if grason==par:
            continue
        x,y=ser(son,grason)
        s*=x
        s%=mod
        t*=(x+y)
        t%=mod
    f[son],g[son]=t,s
    return t,s
z=1
w=1
for i in table[0]:
    ser(0,i)
    z*=f[i]
    z%=mod
    w*=(f[i]+g[i])
    w%=mod
print((z+w)%mod)