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: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding=utf-8
# Date: 2020-04-07 00:38

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

Submission status: Accepted

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

# TLE

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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)]
    # dp[v][0]: white
    # dp[v][1]: black

    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(dp)
    print(ans%mod)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
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)]
# dp[v][0]: white
# dp[v][1]: black

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(dp)
print(ans%mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
MOD = 10**9 + 7


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

    N = int(input())

    #隣接リスト作成
    adj = [[] for _ in range(N)] #頂点数, 場合によって変える
    for _ in range(N-1):
        a,b = map(int, input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)


    #parent[i]:iの親が格納されてる
    parent = [-1]*(N)
    #order:根からDFSで見る順番に頂点を入れる
    order = []
    d = deque([0])
    #全頂点の親をDFSの要領で決める, 根(頂点0)の親は-1
    while d:
        x = d.pop()
        order.append(x)
        for y in adj[x]:
            if y==parent[x]:
                continue
            parent[y] = x
            d.append(y)

    #dp[i]:iを根とする部分木の場合の数
    dp_b = [1]*(N+1)
    dp_w = [1]*(N+1)

    #orderの逆順で計算していく
    for x in order[::-1]:
        b,w = dp_b[x], dp_w[x]
        p = parent[x]
        dp_b[p] *= w%mod
        dp_w[p] *= (b+w)%mod

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

if __name__ == '__main__':
    main()

Submission status: Accepted

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: Accepted

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

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
Ans=[]
inf=10**6

#親と入次数を求める
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)
 
#トポソする
from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

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

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
Ans=[]
inf=10**6

#親と入次数を求める
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)
 
#トポソする
from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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)
black = [1] * (N+1)
white = [1] * (N+1)

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

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

Submission status: Accepted

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]
    q = deque()
    q.append([0, -1])
    while q:
        node, pre = q.pop()
        for nex in edg[node]:
            if nex == pre:
                continue
            rank[nex] = [rank[node][0] + 1, node]
            q.appendleft((nex, node))

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


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

Submission status: Accepted

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

preorder = [-1] * N # a dfs preordering of each vertex
dp = [[1] * 2 for _ in range(N)]
stack = [(0, -1, 0)] # (vertex, parent, status)
pre_num = 0 # current preordering
while stack:
    v, p, st = stack.pop()
    if st == 0 and preorder[v] < 0: # visited v for the first time
        preorder[v] = pre_num
        pre_num += 1
        n_children = 0
        for u in E[v]:
            if preorder[u] >= 0:
                continue
            if n_children == 0:
                stack += [(v, p, 2), (u, v, 0)]
                n_children += 1
            else:
                stack += [(v, p, 1), (u, v, 0)]
                n_children += 1
        if n_children == 0 and p != -1: # v is a leaf
            dp[p][0] *= dp[v][0] + dp[v][1]
            dp[p][0] %= MOD
            dp[p][1] *= dp[v][0]
            dp[p][1] %= MOD
    elif st == 0 and preorder[v] >= 0: # the edge (v, p) is a back edge
        continue
    elif st == 1: # now searching
        continue
    else: # search finished
        if p != -1:
            dp[p][0] *= dp[v][0] + dp[v][1]
            dp[p][0] %= MOD
            dp[p][1] *= dp[v][0]
            dp[p][1] %= MOD
print((dp[0][0] + dp[0][1]) % MOD)

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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


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


tree(0)

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


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


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

Submission status: Accepted

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

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

#節点iの子のリストを作成
node = [root]
while node:
    s = node.pop()
    seen[s] = True
    for t in edge[s]:
        if seen[t]:
            continue
        node.append(t)
        under[s].append(t)

def BW(s):
    if not under[s]: #葉なら白黒1色ずつ
        return
    for t in under[s]:
        BW(t)
        white[s] = (white[s] * (white[t] + black[t])) % mod
        black[s] = (black[s] * white[t]) % mod

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

Submission status: Accepted

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: Accepted

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

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

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

dp1 = [0]*N # 頂点iが白のときに、頂点iを根とする部分木の塗り方の組み合わせ
dp2 = [0]*N # 頂点iが黒のときに、頂点iを根とする部分木の塗り方の組み合わせ


# nodeを白で塗るときに、nodeを根とする部分木の塗り方の組み合わせを求める
def solve1(node, parent): 
  global dp1
  global dp2
  if dp1[node]:
    return dp1[node]
  else:
    children = tree[node]
    if len(children)==0 or \
        len(children)==1 and children[0]==parent: # nodeがリーフのとき
      dp1[node] = 1 # nodeを白に塗る1通りだけ
      return dp1[node]
    
    else:
      dp1[node] = 1
      for child in children:
        if child == parent:
          continue

        dp1[node] *= solve1(child, node) + solve2(child, node)
        dp1[node] %= MOD

      return dp1[node]


# nodeを黒で塗るときに、nodeを根とする部分木の塗り方の組み合わせを求める
def solve2(node, parent):
  global dp1
  global dp2
  if dp2[node]:
    return dp2[node]
  else:
    children = tree[node]
    if len(children)==0 or \
        len(children)==1 and children[0]==parent: # nodeがリーフのとき
      dp2[node] = 1 # nodeを黒に塗る1通りだけ
      return dp2[node]
    
    else:
      dp2[node] = 1
      for child in children:
        if child == parent:
          continue

        dp2[node] *= solve1(child, node)
        dp2[node] %= MOD

      return dp2[node]


print((solve1(0, -1)+solve2(0, -1))%MOD)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10**9)
MOD = 10**9 + 7

n = int(input())

neighbor = {}
for i in range(1,n+1):
    neighbor[i] = []

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

def calc(next, base):
    edges = neighbor[next]

    white, black = 1, 1
    for edge in edges:
        if(edge != base):
            white_e, black_e = calc(edge, next)
            white = white *  (white_e + black_e) % MOD
            black = black * white_e % MOD
    return white, black

white, black = calc(1,0)
print((white + black) % MOD )