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(10 ** 7)
mod = 10 ** 9 + 7

def memodp(DPW, DPB, near, x, FLAG):
    if DPW[x] + DPB[x] > 2:
        return (DPB[x] + DPW[x]) % mod
    else:
        for i in near[x]:
            if i not in FLAG:
                FLAG.add(i)
                DPW[x] *= memodp(DPW, DPB, near, i, FLAG)
                DPB[x] *= DPW[i]
        DPW[x], DPB[x] = DPW[x] % mod, DPB[x] % mod
        return (DPW[x] + DPB[x]) % mod


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

near = [[] for _ in range(n)]
for x, y in xy:
    near[x - 1].append(y - 1)
    near[y - 1].append(x - 1)

dpw, dpb, flag = [1] * n, [1] * n, set([0])
print(memodp(dpw, dpb, near, 0, flag) % mod)

Submission status: Accepted

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

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

def dfs(v, r):
    w, b = 1, 1
    for u in G[v]:
        if u == r: continue
        c_w, c_b = dfs(u, v)
        w *= c_w + c_b
        b *= c_w
    w %= MOD
    b %= MOD
    return w, b

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
MOD = 1_000_000_007
N = int(input())
G = [[] for _ in range(N+1)]
for _ in range(N - 1):
    x, y = list(map(int, input().split()))
    G[x].append(y)
    G[y].append(x)

def dfs(v, root):
    w, b = 1, 1
    for u in G[v]:
        if u == root:
            continue
        child_w, child_b = dfs(u ,v)
        w *= child_w + child_b
        b *= child_w
    w %= MOD
    b %= MOD
    return w, b

print(sum(dfs(1, None)) % MOD)

Submission status: Accepted

Solution code:
######################################################
############Created by Devesh Kumar###################
#############devesh1102@gmail.com####################
##########For CodeForces(Devesh1102)#################
#####################2020#############################
######################################################
import sys
input = sys.stdin.readline

# import sys
import heapq 
import copy
import math
import decimal
# import sys.stdout.flush as flush
# from decimal import *
#heapq.heapify(li) 
#
#heapq.heappush(li,4) 
#
#heapq.heappop(li)
#
# &	Bitwise AND Operator	10 & 7 = 2
# |	Bitwise OR Operator	10 | 7 = 15
# ^	Bitwise XOR Operator	10 ^ 7 = 13

# <<	Bitwise Left Shift operator	10<<2 = 40
# >>	Bitwise Right Shift Operator
# '''############ ---- Input Functions ---- #######Start#####'''


def inp():
	return(int(input()))
def inlt(): 
	return(list(map(int,input().split())))
def insr():
	s = input()
	return(list(s[:len(s) - 1]))
def insr2():
	s = input()
	return((s[:len(s) - 1]))
def invr():
	return(map(int,input().split()))
############ ---- Input Functions ---- #######End
# #####   

def pr_list(a):
	print(*a, sep=" ")
def main():
	# tests =  inp()
	tests = 1
	mod = 1000000007
	limit = 10**18
	ans = 0
	start = {}
	def pre_sum(arr):
		ans = [arr[0]]
		for i in range(1,len(arr)):
			ans.append(ans[-1]+ arr[i])
		return ans
	for test in range(tests):
		n = inp()
		branch = {}

		# parent = [0 for i in range(n+1)]
		for i in range(n-1):
			[p,r] =  inlt()
			if p in branch:
				branch[p].append(r)
			else:
				branch[p] = [r]
			if r in branch:
				branch[r].append(p)
			else:
				branch[r] = [p]
		parent = [-1 for i in range(n+1)]
		# print(branch)
		# print(parent)
		# print(branch)

		dp = [[0 for j in range(n+1)] for i in range(2)]
		leaf = {}
		ans = 2
		stack = [1]
		parent[1] = 0
		if n == 1:
			print(2)
			continue
		while(stack!=[]):
			# print(stack)
			curr = stack[-1]
			flag = 0
			for i in branch[curr]:
				if parent[i] == -1:
					parent[i] = curr
					stack.append(i)
					flag = 1
			if flag == 0:
				curr= stack.pop()
				white = 1
				black = 1
				for i in branch[curr]:
					if i !=parent[curr]:
						white = (white*(dp[0][i] + dp[1][i]))%mod
						black = (black*(dp[0][i]))%mod
				dp[0][curr] = white
				dp[1][curr] = black

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


		# for i in range(1,n+1):
		# 	if i not in branch:
		# 		leaf[i] = 1
		# 		dp[0][i] =1
		# 		dp[1][i] =1
		# # print(leaf)
		# while(leaf!={}):
		# 	nexts = {}
		# 	for i in leaf:
		# 		nexts[parent[i]] = 1
		# 	# print(nexts)
		# 	if 0 in nexts:
		# 		del nexts[0]
		# 	for i in nexts:
		# 		white = 1
		# 		black = 1
				
		# 		for j in branch[i]:
		# 			white = white*(dp[0][j] + dp[1][j])
		# 			black = black * dp[1][j]##1 is white
		# 		dp[0][i] = black
		# 		dp[1][i] = white
		# 		ans= max(ans, dp[0][i]+dp[1][i])
		# 	leaf = nexts
		# print(ans)




		


if __name__== "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
adj=[[] for i in range(n+1)]
dp=[[-1,-1] for i in range(n+1)]
mod=10**9 +7
def dfs(node,parent,color):
    if dp[node][color]!=-1:
        return dp[node][color]
    count=1
    if color==0:
        for i in adj[node]:
            if i==parent:
                continue
            temp=(dfs(i,node,0)+dfs(i,node,1))%mod
            count=(count*temp)%mod
    else:
        for i in adj[node]:
            if i==parent:
                continue
            temp=dfs(i,node,0)%mod
            count=(count*temp)%mod
    dp[node][color]=count
    return count
for _ in range(n-1):
    u,v=map(int,input().split())
    adj[u].append(v)
    adj[v].append(u)
print((dfs(1,-1,0)+dfs(1,-1,1))%mod)

Submission status: Accepted

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

n = int(input())
e = [[] for i in range(n+1)]
mod = 10**9+7

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

def dfs(x,bef):
    w = 1
    b = 1
    for nex in e[x]:
        if nex == bef:
            continue
        nw,nb = dfs(nex,x)
        w *= (nw+nb)%mod
        b *= nw%mod
        w %= mod
        b %= mod
    return w,b

a,b = dfs(1,-1)
print((a+b)%mod)

Submission status: Accepted

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

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(pos: int, par: int):
    # posが白の時 -> 子はなんでも良い
    # posが黒の時 -> 子は全て白
    white = 1
    black = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            white *= sum(tmp)
            black *= tmp[0]
            white %= MOD
            black %= MOD
    return [white, black]  # [白, 黒]

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

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


sys.setrecursionlimit(10 ** 6)


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    adj_nodes = defaultdict(list)
    for _ in range(N - 1):
        x, y = list(map(int, input().split(' ')))
        x -= 1
        y -= 1
        adj_nodes[x].append(y)
        adj_nodes[y].append(x)
    dp_b = [0 for _ in range(N)]
    dp_w = [0 for _ in range(N)]

    def bfs(node, parent):
        black = 1
        white = 1
        for child in adj_nodes[node]:
            if child == parent:
                continue
            bfs(child, node)
            black *= dp_w[child]
            white *= dp_b[child] + dp_w[child]
            black %= MOD
            white %= MOD
        dp_b[node] = black
        dp_w[node] = white

    bfs(0, None)
    print((dp_b[0] + dp_w[0]) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    """
    OPT[node][BLACK] = product(OPT[child[i]][WHITE])
    OPT[node][WHITE] = product(OPT[child[i]][WHITE|BLACK])
    """
    N = read_int()
    G = [[] for _ in range(N)]
    modulo = 10**9+7
    for _ in range(N-1):
        x, y = read_ints()
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    # type, node, parent
    VISIT, CALCULATE = 0, 1
    BLACK, WHITE = 0, 1
    OPT = [
        [1, 1] for _ in range(N)
    ]
    Q = [(VISIT, 0, None)]
    while len(Q) != 0:
        t, node, parent = Q.pop()
        if VISIT == t:
            Q.append((CALCULATE, node, parent))
            for child in G[node]:
                if child != parent:
                    Q.append((VISIT, child, node))
        else:
            for child in G[node]:
                if child != parent:
                    OPT[node][BLACK] = (OPT[node][BLACK]*OPT[child][WHITE])%modulo
                    OPT[node][WHITE] = (OPT[node][WHITE]*(OPT[child][WHITE]+OPT[child][BLACK]))%modulo
    return (OPT[0][BLACK]+OPT[0][WHITE])%modulo


if __name__ == '__main__':
    print(solve())

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
mod=10**9+7
def independent_set(n,graph):

	ways=[[0]*2 for _ in  range(n)]
	# ways[i][0]---->white node
	# ways[i][1]---->black node

	def dfs(node,parent):
		# if len(graph[node])==1:
		# 	ways[node][0]=1
		# 	ways[node][1]=1

		w_w=b_w=1

		for i in graph[node]:
			if i!=parent:
				dfs(i,node)	
				w_w=w_w*sum(ways[i])%mod
				b_w=b_w*ways[i][0]%mod
		ways[node][0]=w_w
		ways[node][1]=b_w

	dfs(0,-1)
	# print(ways)
	return (ways[0][0]+ways[0][1])%mod


n=int(input())
graph={i:[] for i in range(n)}

for i in range(n-1):
	u,v=map(lambda x:int(x)-1,input().split())
	graph[u].append(v)
	graph[v].append(u)
# res=independent_set(n,graph)

res=independent_set(n,graph)

# res=ways(100,10**5,[randint(0,10**5) for _ in range(100)])
print(res%(10**9+7))

Submission status: Accepted

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

mod = 10 ** 9 + 7

N, *XY = map(int, open(0).read().split())

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

def dfs(cur, par):
    w, b = 1, 1
    for nxt in E[cur]:
        if nxt == par:
            continue
        ww, bb = dfs(nxt, cur)
        w = (w * (ww + bb)) % mod
        b = (b * ww) % mod
    return (w, b)

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
MOD = 10 ** 9 + 7

N = int(input())
T = [[] for _ in range(N)]

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


def dfs(x, parent):
    b, w = 1, 1
    for n in T[x]:
        if n == parent:
            continue
        nb, nw = dfs(n, x)
        b *= nw
        w *= (nw + nb)
    b %= MOD
    w %= MOD
    return b, w


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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
from collections import deque
def main():
    n=int(input())
    XY=[tuple(map(int,input().split())) for i in range(n-1)]
    graph=[[]for _ in range(n)]
    for x,y in XY:
        graph[x-1].append(y-1)
        graph[y-1].append(x-1)
    queue=deque([0])
    visited=[False]*n
    use=[False]*n
    #i番目に訪れた頂点までについて，i番目の頂点を白に塗る塗り方，黒
    dp=[[0,0] for _ in range(n)]
    mod=10**9+7
    while queue:
        node=queue[-1] #末尾の要素がvisited→葉に着いた
        if not visited[node]:
            visited[node]=True
            for xnode in graph[node]:
                if visited[xnode]:continue
                queue.append(xnode)
        else:
            queue.pop()
            b,w=1,1
            for xnode in graph[node]:   
                if use[xnode]:
                    w=w*(dp[xnode][0]+dp[xnode][1])%mod
                    b=b*dp[xnode][0]%mod 
            dp[node][0]=w%mod
            dp[node][1]=b%mod 
            use[node]=True
    print(sum(dp[0])%mod)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n=int(input())
mod=10**9+7
l=[[]for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    l[a].append(b)
    l[b].append(a)
def dp(x,par):
    res_w,res_t=1,1
    for y in l[x]:
        if y==par:
            continue
        w,t=dp(y,x)
        res_w=(res_w*w)%mod
        res_t=(res_t*t)%mod
    w,t=res_t,(res_t+res_w)%mod
    return w,t
print(dp(1,0)[1])

Submission status: Accepted

Solution code:
from collections import deque

n = int(input())
mod = 10 ** 9 + 7
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)

start = 1

que = deque([1])
par = [-1] * (n + 1)
topo = []
while que:
    v = que.popleft()
    topo.append(v)
    for u in graph[v]:
        if par[v] == u:
            continue
        par[u] = v
        que.append(u)

dpb = [0] * (n + 1)
dpw = [0] * (n + 1)

for i in topo[::-1]:
    dpb[i] = 1
    dpw[i] = 1
    for j in graph[i]:
        if j == par[i]:
            continue
        dpb[i] *= dpw[j]
        dpw[i] *= dpb[j] + dpw[j]
    dpw[i] %= mod
    dpb[i] %= mod

print((dpw[1] + dpb[1]) % mod)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

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

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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
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()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
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()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
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)] # (v, p)
    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()

Submission status: Accepted

Solution code:
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):
    #if DP[v]!=[-1,-1]:#不要
        #return DP[v]
    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])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#dp[i][j]=(頂点iをjで塗った時,iを親とする部分木の塗り方の場合の数) j=0:黒 j=1:白
#dp[i][0]=(dp[k][0])の総乗(kはiの子)
#dp[i][1]=(dp[k][0]+dp[k][1])の総乗(kはiの子)
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)

Submission status: Accepted

Solution code:
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
    # print(ans,c,v)
    dp[v][c]=ans
    return ans
print((dfs(0,0,-1)+dfs(0,1,-1))%mod)

Submission status: Accepted

Solution code:
#!/usr/bin/env pypy3
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))#v,p,d
    
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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