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:
# @author 

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()

Submission status: Accepted

Solution code:
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: # c == 1
        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)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

# dfsの様々な実装例 in Python
# https://qiita.com/drken/items/a803d4fc4a727e02f7ba
# BEGIN CUT HERE


# v : 現在探索中の頂点，p : vの親（v が親のときは -1）
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)

# 0を頂点とした木の根からの深さ，各頂点を根とした部分木のサイズを求める
# さっきのやつからすこし改造する
depth = [0] * (10 ** 5 + 10)
subtree_size = [0] * (10 ** 5 + 10)
# d : 頂点 v の深さ
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  # 仮に頂点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))
    
# END CUT HERE

if __name__ == '__main__':
    EDPC_P()

Submission status: Accepted

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

# dfsの様々な実装例 in Python
# https://qiita.com/drken/items/a803d4fc4a727e02f7ba
# BEGIN CUT HERE


# v : 現在探索中の頂点，p : vの親（v が親のときは -1）
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)

# 0を頂点とした木の根からの深さ，各頂点を根とした部分木のサイズを求める
# さっきのやつからすこし改造する
depth = [0] * (10 ** 5 + 10)
subtree_size = [0] * (10 ** 5 + 10)
# d : 頂点 v の深さ
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  # 仮に頂点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))
    
# END CUT HERE

if __name__ == '__main__':
    EDPC_P()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
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)

#print(used)
#print(ansb)
#print(answ)

Submission status: Accepted

Solution code:
import sys


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

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

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

Submission status: Accepted

Solution code:
import sys

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


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


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

Submission status: Accepted

Solution code:
from collections import deque

MOD = 10**9 + 7


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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8

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

mod = int(1e9 + 7)

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
edge = [[] for i in range(n)]
for i in range(n-1):
    x,y = map(int,input().split())
    edge[x-1].append(y-1)
    edge[y-1].append(x-1)
mod = 10**9+7
p = -1
le = -1
for i in range(n):
    if len(edge[i]) > le:
        p = i
#c[i]:iの子の集合
c = [[] for i in range(n)]
def ch(x,y):
    for e in edge[x]:
        if e == y:
            continue
        c[x].append(e)
        ch(e,x)
ch(p,-1)

#dp[i][k]:iを親とする木の場合の数.kが0ならiは黒,1なら白
dp = [[-1,-1] for i in range(n)]

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

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

Submission status: Accepted

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

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

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

mod = 10**9 + 7

memo = [0] * n
# dp[v][0]:= 頂点vを白に塗ったときの、vを親とする部分木の塗り方の総数
# dp[v][1]:= 頂点vを黒に塗ったときの、vを親とする部分木の塗り方の総数
dp = [[0, 0] for _ in range(n+1)]


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

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

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

Submission status: Accepted

Solution code:
#n == 1でバグるけど2が返ってくるのでヨシ！
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

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

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

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

Submission status: Accepted

Solution code:
#n == 1でバグるけど2が返ってくるのでヨシ！
from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

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

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

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

dfs(0)

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:


MOD = 1000000007

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

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

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

Submission status: Accepted

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

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

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


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

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

    r = f(1,-1)

    return sum(r) % mod


print(main())

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(100005)
MOD = 1000000007


def dfs(v, a):
    w, b = 1, 1
    for u in links[v]:
        if u == a:
            continue
        cw, cb = dfs(u, v)
        w *= cw + cb
        b *= cw
        w %= MOD
        b %= MOD
    return w, b


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].add(y)
    links[y].add(x)

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

Submission status: Accepted

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

dp = [[1 for _ in range(2)] for _ in range(n)]
#0が白, 1が黒

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

	return

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

Submission status: Accepted

Solution code:
from collections import deque

MOD = 10**9 + 7

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

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

Submission status: Accepted

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

MOD = 10**9 + 7

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

MOD = 10**9 + 7

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

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

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