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
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)
dp = [[0] * n for _ in range(2)]
s = [0]
d = [-1] * n
while s:
    p = s.pop()
    if d[p] == -1:
        d[p] = 0
        s.append(p)
        for node in g[p]:
            if d[node] == -1:
                s.append(node)
    else:
        d[p] = 1
        b = 1
        w = 1
        for node in g[p]:
            if d[node] == 1:
                b *= dp[0][node]
                w *= dp[0][node] + dp[1][node]
        dp[0][p] = w % MOD
        dp[1][p] = b % MOD
print((dp[0][0] + dp[1][0]) % MOD)

Solution (Python):
from collections import deque
N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

mod = 10 ** 9 + 7

parent = [-1] * (N + 1)
node = deque([1])
ts = []
while node:
    s = node.popleft()
    ts.append(s)
    for t in edge[s]:
        if t == parent[s]:
            continue
        parent[t] = s
        node.append(t)

black = [1] * (N + 1)
white = [1] * (N + 1)

while ts:
    s = ts.pop()
    b = 1
    w = 1
    for t in edge[s]:
        if parent[s] == t:
            continue
        b = b * white[t] % mod
        w = w * (white[t] + black[t]) % mod
    black[s] = b
    white[s] = w

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

Solution (Python):
N=int(input())
XY=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for x,y in XY:
    c[x-1].append(y-1)
    c[y-1].append(x-1)
from collections import deque
v=[0]*N
v[0]=1
m=10**9+7
import sys
sys.setrecursionlimit(10**9)
def f(p):
    rw,rb=1,1
    for n in c[p]:
        if not v[n]:
            v[n]=1
            w,b=f(n)
            rw=rw*(w+b)%m
            rb=rb*w%m
    return rw,rb
print(sum(f(0))%m)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(1<<30)
mod=pow(10,9)+7
def f(x,p):
  z[x][0]=z[x][1]=1
  for y in v[x]:
    if y!=p:
      if z[y][0]==-1:
        f(y,x)
      z[x][0]=(z[x][0]*z[y][1])%mod
      z[x][1]=(z[x][1]*(z[y][0]+z[y][1]))%mod
n=int(input())
v=[[] for _ in range(n)]
for x,y in [map(int,raw_input().split()) for _ in range(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in range(n)]
f(0,-1)
print sum(z[0])%mod

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(1<<30)
mod=pow(10,9)+7
def f(x,p):
  if z[x][0]==-1:
    z[x][0]=z[x][1]=1
    for y in v[x]:
      if y!=p:
        f(y,x)
      	z[x][0]=(z[x][0]*z[y][1])%mod
        z[x][1]=(z[x][1]*(z[y][0]+z[y][1]))%mod
n=int(input())
v=[[] for _ in range(n)]
for x,y in [map(int,raw_input().split()) for _ in range(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in range(n)]
f(0,-1)
print sum(z[0])%mod

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

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

dp = [[-1] * 2 for _ in range(N)]
def dfs(v,color,p = -1):
    if dp[v][color] != -1:
        return dp[v][color]
    if color == 0:
        ans = 1
        for e in G[v]:
            if e == p:
                continue
            ans *= dfs(e,0,v) + dfs(e,1,v)
            ans %= MOD
        dp[v][color] = ans
        return ans
    else:
        ans = 1
        for e in G[v]:
            if e == p:
                continue
            ans *= dfs(e,0,v)
            ans %= MOD
        dp[v][color] = ans
        return ans

ans = (dfs(0,0) + dfs(0,1))%MOD
print(ans)

Solution (Python):
from collections import defaultdict
n = int(input())
dic = defaultdict(list)
mod = 10**9 + 7
for i in range(n-1):
    x, y = map(int, input().split())
    dic[x].append(y)
    dic[y].append(x)
dic_pc = {}
dp = [[1, 1] for i in range(n+1)]
parent = [0] * (n + 1)
v = [0] * (n+1)
q = [1]
cnt = 0
order = []
while q:
    p = q.pop()
    v[p] = 1
    order.append(p)
    for child in dic[p]:
        if v[child]:
            continue
        parent[child] = p
        q.append(child)
order.reverse()
for i in order:
    p = parent[i]
    dp[p][0] *= dp[i][0] + dp[i][1]
    dp[p][0] %= mod
    dp[p][1] *= dp[i][0]
    dp[p][1] %= mod
print(dp[0][0])

Solution (Python):
import sys

input=sys.stdin.readline

sys.setrecursionlimit(100000)

N=int(input())
edge={i:[] for i in range(1,N+1)}
for i in range(0,N-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
mod=10**9+7

parent={i:0 for i in range(1,N+1)}

q=set([1])
sub=set([])
while q:
    while q:
        x=q.pop()
        for p in edge[x]:
            if p!=1 and parent[p]==0:
                parent[p]=x
                sub.add(p)

        if not q:
            q=sub
            sub=set([])
            break


def dfs(num):
    if len(edge[num])==1 and num!=1:
        return (1,1)

    WHITE=1
    BLACK=1
    for i in edge[num]:
        if i!=parent[num]:
            s,t=dfs(i)
            WHITE=(WHITE*(s+t))%mod
            BLACK=(BLACK*s)%mod

    return (WHITE,BLACK)

w,b=dfs(1)
print((w+b)%mod)

Solution (Python):

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 1000000007  

N = int(readline())
adj = [[] for _ in range(N)]
for _ in range(N - 1):
    x, y = [int(a) - 1 for a in readline().split()]
    adj[x].append(y)
    adj[y].append(x)


def solve(node, parent):
    w, b = 1, 1
    for nxt in adj[node]:
        if nxt != parent:
            w1, b1 = solve(nxt, node)
            w *= w1 + b1
            w %= MOD
            b *= w1
            b %= MOD
    return w, b


if __name__ == "__main__":
    print(sum(solve(0, -1)) % MOD)

Solution (Python):
import sys
import collections
from collections import deque
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
e = [[] for i in range(N+1)]
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

vis = [0] * (N + 1)
dp = [[1] * 2 for _ in range(N + 1)]
order = deque()
parent = [0] * (N + 1)
s = [1]

while len(s):
  x = s.pop()
  vis[x] = 1
  order.appendleft(x)
  for y in e[x]:
    if vis[y]:continue
    s.append(y)
    parent[y] = x


for x in order:
  y = parent[x]
  dp[y][0] *= dp[x][0] + dp[x][1]
  dp[y][0] %= mod
  dp[y][1] *= dp[x][0]
  dp[y][1] %= mod

print(dp[0][0])

Solution (Python):
n = int(input())
edge = [[] for _ in range(n)]
mod = 10**9 + 7
for i in range(n-1):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
stack = [0]
parent = [-1]*n
deep = [[0,i] for i in range(n)]
while stack:
    p = stack.pop()
    for c in edge[p]:
        if c == parent[p]:continue
        parent[c] = p
        deep[c][0] = deep[p][0] + 1
        stack.append(c)
deep.sort(reverse = True)
ans = [[1,1] for _ in range(n)]
for d,i in deep[:-1]:
    p = parent[i]
    ans[p][0] *= ans[i][1]
    ans[p][0] %= mod
    ans[p][1] *= sum(ans[i])%mod
    ans[p][1] %= mod
print(sum(ans[0])%mod)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    dp = [[1] * 2 for _ in range(n)]
    stack = [(~0, -1), (0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            v = ~v
            white = black = 1
            for nv in E[v]:
                if nv == p:
                    continue
                white = white * (dp[nv][0] + dp[nv][1]) % MOD
                black = black * dp[nv][0] % MOD
            dp[v][0], dp[v][1] = white, black

    print((dp[0][0] + dp[0][1]) % MOD)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    dp = [[1] * 2 for _ in range(n)]
    deg = [len(E[v]) - 1 for v in range(n)]
    deg[0] += 1
    stack = [(~0, -1), (0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            v = ~v
            if deg[v] == 0:
                white = black = 1
                for nv in E[v]:
                    if nv == p:
                        continue
                    white = white * (dp[nv][0] + dp[nv][1]) % MOD
                    black = black * dp[nv][0] % MOD
                dp[v][0], dp[v][1] = white, black
            deg[p] -= 1

    print((dp[0][0] + dp[0][1]) % MOD)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)
    deg = [len(E[v]) - 1 for v in range(n)]
    deg[0] += 1

    topological_sort = []
    parent = [None] * n
    stack = [(~0, -1), (0, -1)] 
    while stack:
        v, p = stack.pop()
        if v >= 0:
            parent[v] = p
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            if deg[~v] == 0:
                topological_sort.append(~v)
            deg[p] -= 1

    dp = [[None] * 2 for _ in range(n)]
    for v in topological_sort:
        white = black = 1
        for nv in E[v]:
            if nv == parent[v]:
                continue
            white *= dp[nv][0] + dp[nv][1]
            black *= dp[nv][0]
            white %= MOD
            black %= MOD
        dp[v][0] = white
        dp[v][1] = black

    print((dp[0][0] + dp[0][1]) % MOD)
resolve()

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

import queue

P=10**9+7
N=int(input())
G=[[] for index1 in range(N+1)]
for index3 in range(N-1):
    x,y=map(int,input().split())
    G[x].append(y)
    G[y].append(x)


DP=[]
DP_sum=[0]*(N+1)
for index4 in range(N+1):
    DP.append([-1,-1])  
q=queue.Queue()
q.put(1)
DP_sum[1]=2

def dfs(v,pv=0):
    
        
    nvs=G[v]
    if v!=1:
        nvs.remove(pv)
    if not nvs:
        DP[v]=[1,1]
        DP_sum[v]=DP[v][0]+DP[v][1]
        return DP[v]
    else:
        v_white=1
        v_black=1
        for nv in nvs:
            nvxy=dfs(nv,v)
            v_white*=(nvxy[0]+nvxy[1])
            v_black*=nvxy[0]
            v_white%=P
            v_black%=P
        DP[v]=[v_white,v_black]
        DP_sum[v]=(DP[v][0]+DP[v][1])%P
        return DP[v]

dfs(1)
print(DP_sum[1])

Solution (Python):
import sys
sys.setrecursionlimit(100000)
n = int(input())
G = [[] 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)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print((dp(0, 0)+dp(0, 1))%p)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
MOD=10**9+7
def dfs(v,p):
    if seen[v]:
        return dp[v]
    seen[v]=1
    b,w=1,1
    for nv in G[v]:
        if(nv==p):
            continue
        bw=dfs(nv,v)
        w*=sum(bw);w%=MOD
        b*=bw[1];b%=MOD
    dp[v]=(b,w)
    return (b,w)
    
N=int(input())
G,dp,seen=[],[],[]
for i in range(N):
    G.append([]);dp.append([0,0]);seen.append(0)
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
print(sum(dfs(0,-1))%MOD)

Solution (Python):
N = int(input())
edge = [[] for _ 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)

import sys
sys.setrecursionlimit(10**8)

mod = 10**9+7
def dfs(v):
    white,black = 1,1
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            w,b = dfs(u)
            white *= w+b
            white %= mod
            black *= w
            black %= mod
    return white,black

visited = [False]*N
visited[0]=True
print(sum(dfs(0))%mod)

Solution (Python):



import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
mod=10**9+7
n=int(input())
es=[[] for i in range(n)]
for i in range(n-1):
   a,b=map(int,input().split())
   es[a-1].append(b-1)
   es[b-1].append(a-1)
dp=[[0,0] for i in range(n)]
def dfs(v,p):
    if dp[v][0]:
        return
    dp[v][0]=dp[v][1]=1
    for i in es[v]:
        if i-p:
            dfs(i,v)
            dp[v][0]*=dp[i][1]
            dp[v][0]%=mod
            dp[v][1]*=dp[i][0]+dp[i][1]
            dp[v][1]%=mod
dfs(0,-1)
print((dp[0][0]+dp[0][1])%mod)

Solution (Python):
import sys
sys.setrecursionlimit(1000000000)
input = sys.stdin.readline
mod=10**9+7
n=int(input())
es=[[] for i in range(n)]
for i in range(n-1):
   a,b=map(int,input().split())
   es[a-1].append(b-1)
   es[b-1].append(a-1)
dp=[[0,0] for i in range(n)]
def dfs(v,c,p):
    if dp[v][c]:
        return dp[v][c]
    ans=1
    if c:
        for i in es[v]:
            if i-p:
                ans*=dfs(i,0,v)+dfs(i,1,v)
                ans%=mod
    else:
        for i in es[v]:
            if i-p:
                ans*=dfs(i,1,v)
                ans%=mod
    
    dp[v][c]=ans
    return ans
print((dfs(0,0,-1)+dfs(0,1,-1))%mod)

Solution (Python):

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    f=[1]*N
    g=[1]*N
    
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        x,y=MI()
        x-=1
        y-=1
        adj[x].append(y)
        adj[y].append(x)
        
    Ld=[[]for _ in range(N)]
    Lp=[0]*N
    Md=0
    
    import queue
    
    q=queue.Queue()
    q.put((0,-1,0))
    
    while not q.empty():
        v,p,d=q.get()
        Ld[d].append(v)
        Lp[v]=p
        Md=max(d,Md)
        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q.put((nv,v,d+1))
                

        
    for i in range(Md-1,-1,-1):
        for j in range(len(Ld[i])):
            v=Ld[i][j]
            tempf=1
            tempg=1
            for k in range(len(adj[v])):
                pv=adj[v][k]
                if pv!=Lp[v]:
                    tempf*=(f[pv]+g[pv])
                    tempg*=f[pv]
                    tempf%=mod
                    tempg%=mod
                
            f[v]=tempf
            g[v]=tempg
            
    print((f[0]+g[0])%mod)

                
    

main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N, *XY = map(int,open(0).read().split())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for x,y in zip(*[iter(XY)]*2):
    neighbor[x-1].append(y-1)
    neighbor[y-1].append(x-1)

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

def dp(node, color, parent):
    if memo[node][color] != -1:
        return memo[node][color]
    output = 1
    for child in neighbor[node]:
        if child == parent:
            pass
        else:
            tmp = dp(child, 0, node)
            if color == 0:
                tmp += dp(child, 1, node)
            output *= tmp
            output %= MOD
    memo[node][color] = output
    return output

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N, *XY = map(int,open(0).read().split())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for x,y in zip(*[iter(XY)]*2):
    neighbor[x-1] += y-1,
    neighbor[y-1] += x-1,

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

def dp(node, color, parent):
    if memo[node][color] != -1:
        return memo[node][color]
    output = 1
    for child in neighbor[node]:
        if child == parent:
            pass
        else:
            tmp = dp(child, 0, node)
            if color == 0:
                tmp += dp(child, 1, node)
            output *= tmp
            output %= MOD
    memo[node][color] = output
    return output

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

Solution (Python):
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N, *XY = map(int,open(0).read().split())
MOD = 10**9 + 7

neighbor = [[] for _ in range(N)]
for x,y in zip(*[iter(XY)]*2):
    neighbor[x-1] += y-1,
    neighbor[y-1] += x-1,

parent = {0}

def dp(node):
    black_output = white_output = 1
    for child in neighbor[node]:
        if child in parent:
            continue
        else:
            parent.add(child)
            tmp_black, tmp_white = dp(child)
            black_output *= tmp_white
            white_output *= tmp_black + tmp_white
    black_output %= MOD
    white_output %= MOD
    return black_output, white_output

print(sum(dp(0)) % MOD)

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

adj = [[] for _ in range(n)]
for a, b in ab:
    a -= 1
    b -= 1
    adj[a].append(b)
    adj[b].append(a)


def dfs(s):
    d = [-1] * n
    p = [-1] * n
    c = [[] for _ in range(n)]

    d[s] = 0
    stack = [s]

    while stack:
        u = stack.pop()
        for v in adj[u]:
            if d[v] == -1:
                d[v] = d[u] + 1
                p[v] = u
                c[u].append(v)
                stack.append(v)

    return d, p, c


d, p, c = dfs(0)

di = [[e, i] for i, e in enumerate(d)]
di.sort(reverse=True)

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

for _, i in di:
    if c[i]:
        for ec in c[i]:
            dp[i][0] *= dp[ec][1]
            dp[i][0] %= mod

            dp[i][1] *= dp[ec][0] + dp[ec][1]
            dp[i][1] %= mod

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

Solution (Python):
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

mod = 10**9+7

def dfs(i=0, r=-1):
    b = w = 1
    for j in e[i]:
        if j == r:
            continue
        bb, ww = dfs(j, i)
        b = b * ww % mod
        w = w * (bb + ww) % mod
    return b, w

print(sum(dfs())%mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
mod = 10**9+7
N = int(input())
G = [[] 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)
    
def dfs(i, pi):
    b = 1
    w = 1
    for ni in G[i]:
        if ni == pi:
            continue
        [nb, nw] = dfs(ni, i)
        b *= nw
        b %= mod
        w *= nw + nb
        w %= mod
    return [b, w]

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

Solution (Python):
import sys
input = sys.stdin.readline
n = int(input())
if n == 1:
  print(2)
  exit()
ab = [list(map(int,input().split())) for i in range(n-1)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
stack = []
for i in range(2,n+1):
  if deg[i] == 1:
    stack.append(i)
deg[1] += 1
dp = [[] for i in range(n+1)]
cnt = [-1 for i in range(n+1)]
while stack:
  x = stack.pop()
  if dp[x]:
    bl = 1
    wh = 1
    for i in dp[x]:
      ibl = i%mod
      iwh = i//mod
      wh = (wh*(ibl+iwh))%mod
      bl = (bl*iwh)%mod
    cnt[x] = wh*mod+bl
  else:
    cnt[x] = mod+1
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(cnt[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
print((cnt[1]%mod+cnt[1]//mod)%mod)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)

get = lambda: int(raw_input().strip())
getl = lambda: raw_input().strip()
gets = lambda: map(int, raw_input().strip().split())
getss = lambda n: [gets() for _ in xrange(n)]

n = get()
G = [[] for i in xrange(n + 1)]
for i in xrange(n - 1):
    i, j = gets()
    G[i].append(j)
    G[j].append(i)
mod = 10**9 + 7


def dfs(i, pre=0):
    black, white = 1, 1
    for j in G[i]:
        if j == pre: continue
        b, w = dfs(j, i)
        black = black * w % mod
        white = white * (b + w) % mod
    return [black, white]
print sum(dfs(1)) % mod

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def main():
  MOD = 10**9+7
  N = int(input())
  edge = [[] for _ in range(N+1)]
  dp = [[0]*2 for i in range(100005)]
  
  
  for i in range(N-1):
      x,y = map(int,input().split())
      edge[x].append(y)
      edge[y].append(x)

  
  def dfs(v,last=-1):
      dp[v][0] = 1
      dp[v][1] = 1
      for nv in edge[v]:
          if nv == last:
              continue
          dfs(nv, v)
          dp[v][0] = dp[v][0] * ((dp[nv][0] + dp[nv][1]) % MOD) % MOD
          dp[v][1] = dp[v][1] * dp[nv][0] % MOD


  dfs(1)
  print((dp[1][0] + dp[1][1])%MOD)
if __name__ == '__main__':
  main()

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

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


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


def dfs(x, parent):
    for v in PATH[x]:
        if v == parent:
            continue
        dfs(v, x)

        dp[x][0] *= (dp[v][0] + dp[v][1])
        dp[x][0] %= MOD
        dp[x][1] *= dp[v][0]
        dp[x][1] %= MOD

    return 0


dfs(1, -1)
ans = sum(dp[1])
ans %= MOD
print(ans)

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

def main():
    N = int(input())
    edge = [[] for _ in range(N)]
    MOD = 10**9+7
    
    for _ in range(N-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        
    dp = [[1]*2 for _ in range(N)] 
    
    def col(now,prev):
        for fol in edge[now]:
            if fol == prev:
                continue
            col(fol,now)
            dp[now][0] *= (dp[fol][0]+dp[fol][1])
            dp[now][0] %= MOD
            dp[now][1] *= dp[fol][0]
            dp[now][1] %= MOD
        return
    
    col(0,-1)
    print(sum(dp[0])%MOD)

if __name__ == "__main__":
    main()

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

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

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

    s = []
    order = []
    par = [-1]*n
    s.append(0)
    while s:
        v = s.pop()
        order.append(v)
        for u in g[v]:
            if u == par[v]:
                continue
            par[u] = v
            s.append(u)

    order.reverse()
    for v in order:
        if par[v] == -1:
            continue
        dp[par[v]][0] *= (dp[v][0]+dp[v][1])%mod
        dp[par[v]][1] *= dp[v][0]%mod
    ans = dp[0][0]+dp[0][1]
    
    print(ans%mod)

if __name__ == '__main__':
    main()

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

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

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



s = []
order = []
par = [-1]*n
s.append(0)
while s:
    v = s.pop()
    order.append(v)
    flag = True
    for u in g[v]:
        if u == par[v]:
            continue
        flag = False
        par[u] = v
        s.append(u)

order.reverse()
for v in order:
    if par[v] == -1:
        continue
    dp[par[v]][0] *= (dp[v][0]+dp[v][1])%mod
    dp[par[v]][1] *= dp[v][0]%mod
ans = dp[0][0]+dp[0][1]

print(ans%mod)

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

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

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



s = []
order = []
par = [-1]*n
s.append(0)
while s:
    v = s.pop()
    order.append(v)
    flag = True
    for u in g[v]:
        if u == par[v]:
            continue
        flag = False
        par[u] = v
        s.append(u)

order.reverse()
for v in order:
    if par[v] == -1:
        continue
    dp[par[v]][0] *= (dp[v][0]+dp[v][1])%mod
    dp[par[v]][1] *= dp[v][0]%mod
ans = dp[0][0]+dp[0][1]

print(ans%mod)

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

mod = 10**9+7

def dfs(v, Pa=-1):
    white, black = 1, 1
    for u in to[v]:
        if u == Pa: continue
        x, y = dfs(u, v)
        white *= x+y
        black *= x
    return white, black

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

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

white, black = dfs(0)
print((white+black) % mod)

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

n = int(input())
g = [[] 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, pv):
    blk, wht = 1, 1
    for nv in g[v]:
        if nv == pv: continue
        nb, nw = dfs(nv, v)
        blk *= nw
        wht *= nb + nw
        blk %= MOD
        wht %= MOD
    return blk, wht

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

Solution (Python):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
e = dd(list)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

vis = [0] * (N + 1)
dp = [[1] * 2 for _ in range(N + 1)]
order = []
parent = [0] * (N + 1)
s = [1]
while len(s):
  x = s.pop()
  vis[x] = 1
  order.append(x)
  for y in e[x]:
    if vis[y]: continue
    s.append(y)
    parent[y] = x
order.reverse()
for x in order:
  y = parent[x]
  dp[y][0] *= dp[x][0] + dp[x][1]
  dp[y][0] %= mod
  dp[y][1] *= dp[x][0]
  dp[y][1] %= mod
print(dp[0][0])

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

Solution (Python):
MOD = 10**9+7

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

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

for e in E:
    tree[e[0] - 1].append(e[1] - 1)
    tree[e[1] - 1].append(e[0] - 1)

visited = [0 for _ in range(N)]
visited[0] = 1

order = [None for _ in range(N)]
od = 0
order[0] = 0

parent = [0 for _ in range(N)]
parent[0] = -1

stack = [0]

while stack:
    node = stack.pop()
    for adj in tree[node]:
        if not visited[adj]:
            visited[adj] = 1
            od += 1
            order[od] = adj
            parent[adj] = node
            stack.append(adj)

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

for node in order[::-1]:
    for adj in tree[node]:
        if parent[adj] == node:
            dp[node][0] *= dp[adj][0] + dp[adj][1]
            dp[node][0] %= MOD
            dp[node][1] *= dp[adj][0]
            dp[node][1] %= MOD

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

Solution (Python):

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)