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
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
  N = int(input())
  XY = [tuple(map(int,input().split())) for _ in range(N-1)]
  MOD =10**9+7
  
  E = [[] for _ in range(N)]
  for x,y in XY:
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
  
  def dfs(v,s):
    b = 1
    w = 1
    for u in E[v]:
      if u != s:
        b0,w0 = dfs(u,v)
        b *= w0
        w *= (b0+w0)
    
    
    return b,w

  b,w = dfs(0,-1)
  print((b+w) % MOD)

if __name__ == '__main__':
    main()

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

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

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

def dfs(n,p):
    w = 1
    b = 1
    for i in to[n]:
        if i != p:
            rw, rb = dfs(i, n)
            w *= (rw + rb)
            w %= MOD
            b *= rw
            b %= MOD
    return (w,b)

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

Solution (Python):



import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        dp[v][0] *= (dp[u][0]+dp[u][1])
        dp[v][0] %= mod
        dp[v][1] *= dp[u][0]
        dp[v][1] %= mod

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

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
n=int(input())
s=[[]for i in range(n+1)]
m=10**9+7
for i in range(n-1):
    x,y=map(int,input().split())
    s[x].append(y)
    s[y].append(x)
t=[[0,0]for i in range(n+1)]
def f(a,b):
    t[a][0]=t[a][1]=1
    for i in s[a]:
        if i!=b:
            f(i,a)
            t[a][0]*=t[i][0]+t[i][1]
            t[a][1]*=t[i][0]
f(1,0)
print(sum(t[1])%m)

Solution (Python):

import sys
sys.setrecursionlimit(100005)
mod=1000000007


def dfs(v,a):
    w=b=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 i 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):
from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    E = {}
    for i in range(0, N+1):
        E[i] = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E[a].append(b)
        E[b].append(a)

    dp = [[0 for i in range(2)] for j in range(100100)]

    def dfs(c, p):
        dp[c][0], dp[c][1] = 1, 1
        for to in E[c]:
            if to != p:
                dfs(to, c)
                dp[c][0] *= dp[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

N = int(input())
es = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(lambda x: int(x)-1, input().split())
    es[x].append(y)
    es[y].append(x)
depth = [None] * N
def dfs(v, p, d):
    depth[v] = d
    for u in es[v]:
        if u != p:
            dfs(u, v, d+1)
dfs(0, -1, 0)
dp = [[1] * 2 for i in range(N)]
@functools.lru_cache(maxsize=None)
def rec(v):
    d = depth[v]
    for u in es[v]:
        if d < depth[u]:
            w, b = rec(u)
            dp[v][0] *= w+b
            dp[v][1] *= w
    dp[v][0] %= mod
    dp[v][1] %= mod
    return dp[v][0], dp[v][1]
w, b = rec(0)
print((w+b)%mod)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007



def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])

def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return


def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return


def D():
    n = I()
    a = LI()
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    dp = [[0]*(n+1) for i in range(n)]
    for le in range(1,n):
        for l in range(n-le):
            r = l+le+1
            res = float("inf")
            for i in range(l+1,r):
                m = dp[l][i]+dp[i][r]
                if m < res:
                    res = m
            res += a[r]-a[l]
            dp[l][r] = res
    print(dp[0][n])
    return


def E():

    n = I()
    a = LIR(n)
    m = 1<<n
    dp = [0]*m
    dp[0] = 1
    a = [[j for j in range(n) if a[i][j]] for i in range(n)]
    bit_count = [-1]
    for i in range(n):
        for j in range(len(bit_count)):
            bit_count.append(bit_count[j]+1)
    for k in range(1,m):
        i = bit_count[k]
        for j in a[i]:
            bj = 1<<j
            if bj > k:
                break
            if not k&bj:
                continue
            nk = k^bj
            dp[k] += dp[nk]
    print(dp[m-1]%mod)

def F():

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    f = [1]*n
    g = [1]*n
    bfs = [1]*n
    bfs[0] = 0
    q = deque([0])
    par = [None]*n
    d = [[0,i] for i in range(n)]
    while q:
        x = q.popleft()
        for y in v[x]:
            if bfs[y]:
                bfs[y] = 0
                par[y] = x
                d[y][0] = d[x][0]+1
                q.append(y)
    d.sort(key = lambda x:-x[0])
    for _,x in d[:-1]:
        px = par[x]
        fx,gx = f[x],g[x]
        f[px] *= fx+gx
        if f[px] >= mod:
            f[px] %= mod
        g[px] *= fx
        if g[px] >= mod:
            g[px] %= mod
    print((f[0]+g[0])%mod)
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    F()

Solution (Python):


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

 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
MOD = 10**9+7
def dfs(v,p): 
    b = w = 1
    for c in g[v]:
        if c == p: continue
        bb, ww = dfs(c,v)
        b *= ww
        b %= MOD        
        w *= bb+ww
        w %= MOD
    return b,w

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

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(i):
    w=b=1
    for j in e[i]:
        if j in d:continue
        d.add(j)
        x,y=dfs(j)
        w*=x+y
        b*=x
    return w%M,b%M
M=10**9+7
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for x,y in zip(*[iter(t)]*2):
    e[x-1]+=y-1,
    e[y-1]+=x-1,
d={0}
print(sum(dfs(0))%M)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)
def dfs(i):
    w=b=1
    for j in e[i]:
        if j in d:continue
        d.add(j)
        x,y=dfs(j)
        w*=x+y
        b*=x
    return w%M,b%M
M=10**9+7
n,*t=map(int,open(0).read().split())
e=[[]for _ in range(n)]
for x,y in zip(*[iter(t)]*2):
    e[x-1]+=y-1,
    e[y-1]+=x-1,
d={0}
print(sum(dfs(0))%M)

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

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

def dfs(x=1,parent=None):
    b,w = 1,1 
    for y in graph[x]:
        if y == parent:
            continue
        b1,w1 = dfs(y,x)
        b *= w1
        w *= (b1+w1)
        b %= MOD
        w %= MOD
    return b,w

b,w = dfs()
answer = (b+w) % MOD
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
n = int(input())
nodes = [[] for _ in range(n+1)]
done = [1 for _ in range(n+1)]
mod = int(1e9+7)
def dfs(next):
    w=1
    b=1
    for v in nodes[next]:
        if done[v]:
            done[v]=0
            white,black= dfs(v)
            w *= white+black
            b *= white
            w%=mod
            b%=mod
    return (w,b)
 
for i in range(n-1):
    a,b = map(int,input().split())
    nodes[a].append(b)
    nodes[b].append(a)
done[1]=0
 
ans = dfs(1)
print(sum(ans)%mod)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
n = int(input())
nodes = [[] for _ in range(n+1)]
done = [1 for _ in range(n+1)]
mod = int(1e9+7)
def dfs(next,pre):
    w=1
    b=1
    for v in nodes[next]:
        if v!=pre:
            white,black= dfs(v,next)
            w *= (white+black)
            b *= white
            w%=mod
            b%=mod
    return (w,b)

for i in range(n-1):
    a,b = map(int,input().split())
    nodes[a].append(b)
    nodes[b].append(a)
done[1]=0

ans = dfs(1,-1)
print(sum(ans)%mod)

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

def main():
    input = sys.stdin.readline

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

    def rec(cur, prev=None):
        white = 1
        black = 1
        for to in edges[cur]:
            if to == prev:
                continue
            w,b = rec(to, cur)
            white *= (w+b)
            white %= mod
            black *= w
            black %= mod
        return white, black

    w, b = rec(0)
    print((w+b)%mod)

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

class Tree:
  C, RL = {}, {}
  R, N, D = None, None, None
  def __init__(s, num):
    s.N = num
  def setC(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root = 0):
    s.R = [0] * s.N
    s.R[root] = 1
    s.RL[1] = [root]
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
      s.D += 1
      F = Ft
  def nasu(s, x = 0):
    DP = [[1] * 2 for _ in range(s.N)]
    for d in range(s.D - 2, 0, -1):
      for i in s.RL[d]:
        L = []
        for j in s.C[i]:
          if s.R[j] > s.R[i]:
            L.append(j)
        b = 1
        w = 1
        for k in L:
          b = b * DP[k][0] % MOD
          w = w * (DP[k][0] + DP[k][1]) % MOD
        DP[i] = [w, b]
    return (DP[x][0] + DP[x][1]) % MOD

T = Tree(N)
if N == 1:
  print(2)
  exit()
for x, y in xy:
  x -= 1
  y -= 1
  T.setC(x, y)

T.makeRank()

print(T.nasu())

Solution (Python):


import sys

class PIndependentSet:
    def solve(self):
        from collections import defaultdict
        MOD = 10 ** 9 + 7

        def dfs(s):
            st = [s]
            par = [-1] * n
            done = [0] * n
            o = []
            while st:
                u = st.pop()
                if done[u]: continue
                o.append(u)
                done[u] = 1
                for x in adj[u]:
                    par[x] = u
                    st.append(x)
            done = [0] * n
            o.reverse()
            for u in o:
                dp[u][0] = 1
                dp[u][1] = 1
                done[u] = 1
                for x in adj[u]:
                    if not done[x]:
                        continue
                    dp[u][0] = (dp[u][0] * dp[x][1]) % MOD
                    dp[u][1] = (dp[u][1] * (dp[x][0] + dp[x][1])) % MOD

        n = int(input())
        adj = defaultdict(list)

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

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

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

solver = PIndependentSet()
input = sys.stdin.readline

solver.solve()

Solution (Python):


import sys


class PIndependentSet:
    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)
        MOD = 10 ** 9 + 7

        def dfs(s):
            done[s] = 1
            dp[s][0] = 1
            dp[s][1] = 1
            for x in adj[s]:
                if done[x]:
                    continue
                dfs(x)
                dp[s][0] = (dp[s][0] * dp[x][1]) % MOD
                dp[s][1] = (dp[s][1] * (dp[x][0] + dp[x][1])) % MOD

        n = int(input())
        adj = defaultdict(list)

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

        dp = [[0, 0] for _ in range(n)]
        done = [0] * n
        dfs(0)

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

solver = PIndependentSet()
input = sys.stdin.readline

solver.solve()

Solution (Python):
from collections import defaultdict,deque
import numpy as np
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = inp()
lines = defaultdict(set)
for _ in range(N-1):
    x,y = inpl()
    x,y = x-1,y-1
    lines[x].add(y)
    lines[y].add(x)

lines2 = defaultdict(set)
visited = [False]*N
def dfs(s):
    visited[s] = True
    for t in lines[s]:
        if not visited[t]:
            lines2[s].add(t)
            dfs(t)
dfs(0)

dp = [[-1,-1] for _ in range(N)]
def solve(s,c):
    global dp

    if dp[s][c] != -1:
        return dp[s][c]

    ans = 1
    if c == 0:
        for t in lines2[s]:
            ans *= solve(t,0)+solve(t,1)
            ans %= mod
    else: 
        for t in lines2[s]:
            ans *= solve(t,0)
            ans %= mod

    dp[s][c] = ans
    return ans

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

Solution (Python):
from collections import deque
import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)

N = int(input())
connection = [[] for _ in range(N)]
children = [[] for _ in range(N)]
arrival_order = []
mod = 10 ** 9 + 7
hasReached = [0] * N
dp_white = [1] * N
dp_black = [1] * N
q = deque([])
q.append(0)

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

while len(q) > 0:
	now_node = q.popleft()
	arrival_order.append(now_node)
	hasReached[now_node] = 1
	for next_node in connection[now_node]:
		if hasReached[next_node] == 0:
			q.append(next_node)
			children[now_node].append(next_node)

for i in reversed(arrival_order):
	for j in children[i]:
		dp_black[i] *= dp_white[j]
		dp_black[i] %= mod
		dp_white[i] *= (dp_black[j] + dp_white[j])
		dp_white[i] %= mod
		
print((dp_black[0] + dp_white[0]) % mod)

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

mod = 10**9 + 7

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

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

def rec(v=0,pv=-1):
    for cv in ad[v]:
        if cv == pv:
            continue
        rec(cv,v)
        dp[v][0] *= (dp[cv][0] + dp[cv][1]) % mod
        dp[v][1] *= dp[cv][0] % mod

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

Solution (Python):
N=int(input())
graph=[[] for i in range(N)]
for i in range(N-1):
    a,b=list(map(int,input().strip().split(' ')))
    a-=1
    b-=1
    graph[a]+=[b]
    graph[b]+=[a]

parent=[-1]*N
checked=[0]*N
dp=[[0]*2 for i in  range(N)]

from collections import deque
q=deque([0])
checked[0]=1
bfs=[]
while q:
    node=q.popleft()
    bfs+=[node]
    for adj in graph[node]:
        if checked[adj]==0:
            parent[adj]=node
            checked[adj]=1
            q+=[adj]

bfs=bfs[::-1]
MOD=10**9+7
for node in bfs:
    temp1=1
    temp2=1
    leaf=1
    for adj in graph[node]:
        leaf=0
        if adj != parent[node]:
            temp1*=(dp[adj][0]+dp[adj][1])
            temp1%=MOD
            temp2*=dp[adj][0]
            temp2%=MOD
    if leaf==1:
        dp[node][0]=1
        dp[node][1]=1
    
    else:
        dp[node][0]=temp1
        dp[node][1]=temp2

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

Solution (Python):
import fileinput
from collections import defaultdict

def longest_path(edges):
    if not edges:
        return 2

    modulo = 10**9 + 7
    graph = defaultdict(list)
    
    min_node = 10**9

    for v_a, v_b in edges:
        graph[v_a].append(v_b)
        graph[v_b].append(v_a)

        min_node = min(min_node, v_a, v_b)
    
    set_count_black = [0] * (len(graph) + 1)
    set_count_white = [0] * (len(graph) + 1)

    node_stack = []
    nodes_on_stack = [True] + [False] * node_count

    node_stack.append([min_node, 0])
    nodes_on_stack[min_node] = True

    while node_stack:
        top_node, last_child = node_stack[-1]
        if top_node in graph and last_child < len(graph[top_node]):
            node_stack[-1][1] += 1
            current_child = graph[top_node][last_child]
            if nodes_on_stack[current_child] == False:
                node_stack.append([current_child, 0])
                nodes_on_stack[current_child] = True
        else:
            node, children = node_stack.pop()
            nodes_on_stack[node] = False

            if (children == 1 and node != min_node) or children == 0:
                set_count_black[node] = 1
                set_count_white[node] = 1
            else:
                bc = 1
                wc = 1
                for child in graph[node]:
                    if nodes_on_stack[child]:
                        continue
                    bc *= set_count_white[child]
                    wc *= (set_count_white[child] + set_count_black[child])
                set_count_white[node] = wc % modulo
                set_count_black[node] = bc % modulo
    return (set_count_white[min_node] + set_count_black[min_node]) % modulo

inp = fileinput.FileInput()

node_count = int(inp.readline())
edges = []

for _ in range(node_count - 1):
    split = inp.readline().split(" ")
    edges.append(
        (int(split[0]), int(split[1]))
    )

print(longest_path(edges))

Solution (Python):
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())








def dfs_tree(G,v,p):
    '''木上のdfsの実装例'''
    for nv in G[v]:
        if nv == p:
            continue
        dfs_tree(G, nv, v)
def main1():
    N = ii()
    G = [[] for i in range(N)]
    for i in range(N - 1):
        a, b = mi()
        G[a].append(b)
        G[b].append(a)
    
    root = 0
    dfs_tree(G, root, -1)



depth = [0] * (10 ** 5 + 10)
subtree_size = [0] * (10 ** 5 + 10)

def dfs_tree_kai(G, v, p, d):
    
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        else:
            dfs_tree_kai(G, nv, v, d + 1)
    
    
    subtree_size[v] = 1  
    for c in G[v]:
        if c == p:
            continue
        subtree_size[v] += subtree_size[c]
    return depth, subtree_size

def main2():
    '''木DPの簡単な例（部分木のサイズを求める）'''
    N = ii()
    G = [[] for i in range(N)]
    for i in range(N - 1):
        a, b = mi()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    root = 0  
    dfs_tree_kai(G, root, -1, 0)
    
    for v in range(N):
        print(v, ": depth = ", depth[v], ", subtree_size = ", subtree_size[v])
    
def EDPC_P():
    N = ii()
    dp = [[1, 1] for _ in range(N)]
    G = [[] for i in range(N)]
    for _ in range(N - 1):
        a, b = mi()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    def dfs_EDPC_P(G, v, p):
        for nv in G[v]:
            if nv == p:
                continue
            dfs_EDPC_P(G, nv, v)
        for c in G[v]:
            if c == p:
                continue
            dp[v][0] *= (dp[c][0] + dp[c][1]) % (10 ** 9 + 7)
            dp[v][1] *= dp[c][0]
    dfs_EDPC_P(G,0,-1)
    print((dp[0][0]+dp[0][1])%(10**9+7))
    


if __name__ == '__main__':
    EDPC_P()

Solution (Python):
import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())








def dfs_tree(G,v,p):
    '''木上のdfsの実装例'''
    for nv in G[v]:
        if nv == p:
            continue
        dfs_tree(G, nv, v)
def main1():
    N = ii()
    G = [[] for i in range(N)]
    for i in range(N - 1):
        a, b = mi()
        G[a].append(b)
        G[b].append(a)
    
    root = 0
    dfs_tree(G, root, -1)



depth = [0] * (10 ** 5 + 10)
subtree_size = [0] * (10 ** 5 + 10)

def dfs_tree_kai(G, v, p, d):
    
    depth[v] = d
    for nv in G[v]:
        if nv == p:
            continue
        else:
            dfs_tree_kai(G, nv, v, d + 1)
    
    
    subtree_size[v] = 1  
    for c in G[v]:
        if c == p:
            continue
        subtree_size[v] += subtree_size[c]
    return depth, subtree_size

def main2():
    '''木DPの簡単な例（部分木のサイズを求める）'''
    N = ii()
    G = [[] for i in range(N)]
    for i in range(N - 1):
        a, b = mi()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    root = 0  
    dfs_tree_kai(G, root, -1, 0)
    
    for v in range(N):
        print(v, ": depth = ", depth[v], ", subtree_size = ", subtree_size[v])
    
def EDPC_P():
    N = ii()
    dp = [[1, 1] for _ in range(N)]
    G = [[] for i in range(N)]
    for i in range(N - 1):
        a, b = mi()
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    depth = [0]*N
    def dfs_EDPC_P(G, v, p, d):
        depth[v] = d
        for nv in G[v]:
            if nv == p:
                continue
            dfs_EDPC_P(G, nv, v, d + 1)
        for c in G[v]:
            if c == p:
                continue
            dp[v][0] *= (dp[c][0] + dp[c][1]) % (10 ** 9 + 7)
            dp[v][1] *= dp[c][0]
    dfs_EDPC_P(G,0,-1,0)
    print((dp[0][0]+dp[0][1])%(10**9+7))
    


if __name__ == '__main__':
    EDPC_P()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
 
BLK = 1
WHT = 0
MOD = 10 ** 9 + 7
 
 
def calcdp(r, p, bw):
    if dp[r][bw] != -1:
        return dp[r][bw]
 
    if p == 0:
        cs = H[r]
    else:
        cs = H[r] - {p}
 
    if len(cs) == 0:
        dp[r][bw] = 1
        return 1
    else:
        if bw == BLK:
            res = 1
            for c in cs:
                res = (res * calcdp(c, r, WHT)) % MOD
            dp[r][BLK] = res
            return res
        else:
            res = 1
            for c in cs:
                res = (res * (calcdp(c, r, WHT) + calcdp(c, r, BLK))) % MOD
            dp[r][WHT] = res
 
            return res
 
 
N = int(input())
H = [set() for _ in range(N + 1)]
for _ in range(1, N):
    x, y = map(int, input().split())
    H[x].add(y)
    H[y].add(x)
 
dp = [[-1] * 2 for _ in range(N + 1)]
 
print((calcdp(1, 0, BLK) + calcdp(1, 0, WHT)) % MOD)

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

MOD=10**9+7
 
n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
  p,q = [int(i)-1 for i in input().split()]
  edge[p].append(q)
  edge[q].append(p)

flag=[0]*n
flag[0]=1
if n==1:
  ans=2
else:
  dp=[[0] * 2 for i in range(n)]
  for i in range(n):
    if len(edge[i])==1:
      dp[i]=[1,1]
      flag[i]=1
    else:
      dp[i]=[0,0]
  dp[0]=[0,0]
  stack = [0]
  while len(stack)!=0:
    term=0
    white=1
    black=1
    length=len(stack)-1
    for i in range(len(edge[stack[length]])):
      if flag[edge[stack[length]][i]]==0:
        flag[edge[stack[length]][i]]=1
        stack.append(edge[stack[length]][i])
        term=1
      else:
        sub1=max(1,(dp[edge[stack[length]][i]][0]+dp[edge[stack[length]][i]][1])%MOD)
        sub2=max(1,dp[edge[stack[length]][i]][0])
        white=(white*sub1)%MOD
        black=(black*sub2)%MOD
    if term == 0:
      dp[stack[length]]=[white,black]
      stack.pop()
  
  ans = (dp[0][0]+dp[0][1])%MOD

print(ans)

Solution (Python):
import sys
def getpar(Edge, p = 0):
    N = len(Edge)
    par = [0]*N
    par[p]  -1
    stack = [p]
    visited = set([p])
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            stack.append(vf)
    return par

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

Dim[0] += 2
Leaf = [i for i in range(N) if Dim[i] == 1]

par = getpar(Edge)
dpw = [1]*N
dpb = [1]*N
stack = Leaf[:]
while stack:
    vn = stack.pop()
    vp = par[vn]
    dpw[vp] = (dpw[vp]*(dpw[vn] + dpb[vn])) % mod
    dpb[vp] = dpb[vp]*dpw[vn] % mod
    Dim[vp] -= 1
    if Dim[vp] == 1:
        stack.append(vp)
print((dpw[0] + dpb[0])%mod)

Solution (Python):


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

n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    p,q = [int(i)-1 for i in input().split()]
    edge[p].append(q)
    edge[q].append(p)

    
used = [0]*n

def dfs(x):
    used[x] = 1
    cb=1; cw=1;
    for e in edge[x]:
        if used[e]: continue
        eb,ew = dfs(e)
        cb*=ew
        cb%=MOD
        cw*=(eb+ew)
        cw%=MOD        
    return (cb,cw)

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

Solution (Python):


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

n=int(input())
edge=[[] for _ in range(n)]
for _ in range(n-1):
    p,q = [int(i)-1 for i in input().split()]
    edge[p].append(q)
    edge[q].append(p)

    
used = [0]*n
ansb = [0]*n
answ = [0]*n

def dfs(x):
    if used[x]: return (ansb[x], answ[x])
    used[x] = 1
    cb=1; cw=1;
    for e in edge[x]:
        if used[e]: continue
        eb,ew = dfs(e)
        cb*=ew
        cb%=MOD
        cw*=(eb+ew)
        cw%=MOD        
    ansb[x]=cb
    answ[x]=cw
    return (cb,cw)

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