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: Runtime Error

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])
							black = black*(dp[0][i])
					dp[0][curr] = white
					dp[1][curr] = black

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


			# 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: Runtime Error

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

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

Submission status: Runtime Error

Solution code:
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が黒の時 -> 子は全て白
    all = 1
    black = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            all *= sum(tmp)
            black *= tmp[0]
            all %= MOD
            black %= MOD
    return [all, black]  # [白, 黒]

print(sum(dfs(0, 0)))

Submission status: Runtime Error

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

dp = [[1]*2 for _ in range(N)]
def dfs(pos: int, par: int):
    # dp[pos][0] = 白または黒の積 (posが白の時)
    # dp[pos][1] = 白の積 (posが黒の時)
    all = 1
    only_whilte = 1
    for v in G[pos]:
        if v != par:
            tmp = dfs(v, pos)
            all *= sum(tmp)
            only_whilte *= tmp[0]
            all %= MOD
            only_whilte %= MOD
    return [all, only_whilte]

print(sum(dfs(0, 0)))

Submission status: Runtime Error

Solution code:
n=int(input())
li=[]
mod=10**9+7
for _ in range(n-1):
  li.append([int(k) for k in input().split()])
adjl=[[] for i in range(n+1)]
for j in li:
  adjl[j[0]].append(j[1])
  adjl[j[1]].append(j[0])
#print(adjl)  
visited=[0]*(n+1)
fl=0
dp=[[1 for i in range(2)] for j in range(n+1)]
def findans(adjl,st):
  #print(1)
  fl=0
  visited[st]=1
  for k in range(len(adjl[st])):
      
      if visited[adjl[st][k]]==0:
          fl=1
          ansli=findans(adjl,adjl[st][k])
          dp[st][0]=ansli[1]*dp[st][0]
          dp[st][1]=(ansli[1]+ansli[0])*dp[st][1]
  if len(adjl[st])==1 and fl==0:
      dp[st][0]=1
      dp[st][1]=1
  return dp[st]          
findans(adjl,1)
#print(visited)
#print(dp)
print((dp[1][0]+dp[1][1])%mod)

Submission status: Runtime Error

Solution code:
n=int(input())
if(n==1):
  return 2
li=[]
mod=10**9+7
for _ in range(n-1):
  li.append([int(k) for k in input().split()])
adjl=[[] for i in range(n+1)]
for j in li:
  adjl[j[0]].append(j[1])
  adjl[j[1]].append(j[0])
#print(adjl)  
visited=[0]*(n+1)
fl=0
dp=[[1 for i in range(2)] for j in range(n+1)]
def findans(adjl,st):
  #print(1)
  fl=0
  visited[st]=1
  for k in range(len(adjl[st])):
      
      if visited[adjl[st][k]]==0:
          fl=1
          ansli=findans(adjl,adjl[st][k])
          dp[st][0]=ansli[1]*dp[st][0]
          dp[st][1]=(ansli[1]+ansli[0])*dp[st][1]
  if len(adjl[st])==1 and fl==0:
      dp[st][0]=1
      dp[st][1]=1
  return dp[st]          
findans(adjl,1)
#print(visited)
#print(dp)
print((dp[1][0]+dp[1][1])%mod)

Submission status: Runtime Error

Solution code:
n = int(input())

nax = n+5

adj_list = [[] for _ in range(int(nax))]

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

def mul(a, b):
    mod = 1e9+7
    return a * b % mod

def add(a, b):
    mod = 1e9+7
    return (a+b) % mod

# returns {white, black}
def dfs(x, parent):
    all_white = 1
    sth_black = 0
    
    for nei in adj_list[x]:
        if nei != parent:
            p = dfs(nei, x)
            # p[0] - no. of ways to paint such that nei is white
            # p[1] - no. of ways to paint such that nei is black
            sth_black = add(mul(all_white, p[1]), mul(add(p[0], p[1]), sth_black))
            all_white = mul(all_white, p[0])
    
    return [add(sth_black, all_white), all_white]        

p = dfs(1, -1)
ans = int(add(p[0], p[1]))
print(ans)


"""
/*

N 

3
1 2 
2 3



*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

const int nax = 1e5+5;

const int mod = 1e9+7;

int mul(int a, int b) {
    return (ll) a * b % mod;
}

int add(int a, int b) {
    return (a + b) % mod;
}

vector<vector<int>> adj_list(nax);

vector<int> dfs(int x, int parent) {
    // dp[0] - no. of ways to paint it white 
    // dp[1] - no. of ways to paint it black
    vector<int> dp(2);
    
    int all_white = 1;
    
    int sth_black = 0;
    
    for (int y : adj_list[x]) {
        if (y != parent) {
            vector<int> p = dfs(y, x);
            // p.first - no. of ways to paint 'y' white
            // p.second - no. of ways to paint 'y' black
            sth_black = add(mul(all_white, p[1]), mul(sth_black, add(p[0], p[1])));
            all_white = mul(all_white, p[0]);
        }
    }
    
    dp[0] = add(all_white, sth_black); // paint this as white
    
    dp[1] = all_white; // paint this as black
    
    return dp;
}

int main() {
    int n;
    
    scanf("%d", &n);
    
    for (int i = 0; i < n - 1; i++) {
        int xi;
        int yi;
        scanf("%d%d", &xi, &yi);
        adj_list[xi].push_back(yi);
        adj_list[yi].push_back(xi);
    }
    
    vector<int> ans = dfs(1, -1);
    
    printf("%d", add(ans[0], ans[1]));
    
	return 0;
}
"""

Submission status: Runtime Error

Solution code:
n = int(input())

nax = n+5

adj_list = [[] for _ in range(int(nax))]

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

def mul(a, b):
    mod = 1e9+7
    return a * b % mod

def add(a, b):
    mod = 1e9+7
    return (a+b) % mod

# returns {black, white}
def dfs(x, parent):
    all_white = 1
    sth_black = 0
    
    for nei in adj_list[x]:
        if nei != parent:
            p = dfs(nei, x)
            # p[0] - no. of ways to paint such that nei is black
            # p[1] - no. of ways to paint such that nei is white
            sth_black = add(mul(all_white, p[0]), mul(add(p[0], p[1]), sth_black))
            all_white = mul(all_white, p[1])
    
    return [all_white, add(sth_black, all_white)]        

p = dfs(1, -1)
ans = int(add(p[0], p[1]))
print(ans)


"""
/*

N 

3
1 2 
2 3



*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

const int nax = 1e5+5;

const int mod = 1e9+7;

int mul(int a, int b) {
    return (ll) a * b % mod;
}

int add(int a, int b) {
    return (a + b) % mod;
}

vector<vector<int>> adj_list(nax);

vector<int> dfs(int x, int parent) {
    // dp[0] - no. of ways to paint it white 
    // dp[1] - no. of ways to paint it black
    vector<int> dp(2);
    
    int all_white = 1;
    
    int sth_black = 0;
    
    for (int y : adj_list[x]) {
        if (y != parent) {
            vector<int> p = dfs(y, x);
            // p.first - no. of ways to paint 'y' white
            // p.second - no. of ways to paint 'y' black
            sth_black = add(mul(all_white, p[1]), mul(sth_black, add(p[0], p[1])));
            all_white = mul(all_white, p[0]);
        }
    }
    
    dp[0] = add(all_white, sth_black); // paint this as white
    
    dp[1] = all_white; // paint this as black
    
    return dp;
}

int main() {
    int n;
    
    scanf("%d", &n);
    
    for (int i = 0; i < n - 1; i++) {
        int xi;
        int yi;
        scanf("%d%d", &xi, &yi);
        adj_list[xi].push_back(yi);
        adj_list[yi].push_back(xi);
    }
    
    vector<int> ans = dfs(1, -1);
    
    printf("%d", add(ans[0], ans[1]));
    
	return 0;
}
"""

Submission status: Runtime Error

Solution code:
n = int(input())

nax = n+5

mod = 1e9+7

adj_list = [[] for _ in range(int(nax))]

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

def mul(a, b):
    return a * b % mod

def add(a, b):
    return (a+b) % mod

# returns {black, white}
def dfs(x, parent):
    all_white = 1
    sth_black = 0
    
    for nei in adj_list[x]:
        if nei != parent:
            p = dfs(nei, x)
            # p[0] - no. of ways to paint such that nei is black
            # p[1] - no. of ways to paint such that nei is white
            sth_black = add(mul(all_white, p[0]), mul(add(p[0], p[1]), sth_black))
            all_white = mul(all_white, p[1])
    
    return [all_white, add(sth_black, all_white)]        

p = dfs(1, -1)
ans = int(add(p[0], p[1]))
print(ans)


"""
/*

N 

3
1 2 
2 3



*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

const int nax = 1e5+5;

const int mod = 1e9+7;

int mul(int a, int b) {
    return (ll) a * b % mod;
}

int add(int a, int b) {
    return (a + b) % mod;
}

vector<vector<int>> adj_list(nax);

vector<int> dfs(int x, int parent) {
    // dp[0] - no. of ways to paint it white 
    // dp[1] - no. of ways to paint it black
    vector<int> dp(2);
    
    int all_white = 1;
    
    int sth_black = 0;
    
    for (int y : adj_list[x]) {
        if (y != parent) {
            vector<int> p = dfs(y, x);
            // p.first - no. of ways to paint 'y' white
            // p.second - no. of ways to paint 'y' black
            sth_black = add(mul(all_white, p[1]), mul(sth_black, add(p[0], p[1])));
            all_white = mul(all_white, p[0]);
        }
    }
    
    dp[0] = add(all_white, sth_black); // paint this as white
    
    dp[1] = all_white; // paint this as black
    
    return dp;
}

int main() {
    int n;
    
    scanf("%d", &n);
    
    for (int i = 0; i < n - 1; i++) {
        int xi;
        int yi;
        scanf("%d%d", &xi, &yi);
        adj_list[xi].push_back(yi);
        adj_list[yi].push_back(xi);
    }
    
    vector<int> ans = dfs(1, -1);
    
    printf("%d", add(ans[0], ans[1]));
    
	return 0;
}
"""

Submission status: Runtime Error

Solution code:
n = int(input())

nax = 1e5+5

mod = 1e9+7

adj_list = [[] for _ in range(int(nax))]

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

def mul(a, b):
    return a * b % mod

def add(a, b):
    return (a+b) % mod

# returns {black, white}
def dfs(x, parent):
    all_white = 1
    sth_black = 0
    
    for nei in adj_list[x]:
        if nei != parent:
            p = dfs(nei, x)
            # p[0] - no. of ways to paint such that nei is black
            sth_black = add(mul(all_white, p[0]), mul(add(p[0], p[1]), sth_black))
            all_white = mul(all_white, p[1])
    
    return [all_white, add(sth_black, all_white)]        

p = dfs(1, -1)
ans = int(add(p[0], p[1]))
print(ans)


"""
/*

N 

3
1 2 
2 3



*/

#include <bits/stdc++.h>
using namespace std;

using ll = long long; 

const int nax = 1e5+5;

const int mod = 1e9+7;

int mul(int a, int b) {
    return (ll) a * b % mod;
}

int add(int a, int b) {
    return (a + b) % mod;
}

vector<vector<int>> adj_list(nax);

vector<int> dfs(int x, int parent) {
    // dp[0] - no. of ways to paint it white 
    // dp[1] - no. of ways to paint it black
    vector<int> dp(2);
    
    int all_white = 1;
    
    int sth_black = 0;
    
    for (int y : adj_list[x]) {
        if (y != parent) {
            vector<int> p = dfs(y, x);
            // p.first - no. of ways to paint 'y' white
            // p.second - no. of ways to paint 'y' black
            sth_black = add(mul(all_white, p[1]), mul(sth_black, add(p[0], p[1])));
            all_white = mul(all_white, p[0]);
        }
    }
    
    dp[0] = add(all_white, sth_black); // paint this as white
    
    dp[1] = all_white; // paint this as black
    
    return dp;
}

int main() {
    int n;
    
    scanf("%d", &n);
    
    for (int i = 0; i < n - 1; i++) {
        int xi;
        int yi;
        scanf("%d%d", &xi, &yi);
        adj_list[xi].push_back(yi);
        adj_list[yi].push_back(xi);
    }
    
    vector<int> ans = dfs(1, -1);
    
    printf("%d", add(ans[0], ans[1]));
    
	return 0;
}
"""

Submission status: Runtime Error

Solution code:
from collections import defaultdict


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


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	P
# CreatedDate:  2020-05-31 17:39:34 +0900
# LastModified: 2020-05-31 17:51:10 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd

def f(prev_f,n,path,u):
    sum_f=1
    for v in path[u]:
        if prev_f!=v:
            sum_f*=(f(u,n,path,v)+g(u,n,path,v))
            sum_f=sum_f%1000000007
    return sum_f

def g(prev_g,n,path,u):
    sum_g=1
    for v in path[u]:
        if prev_g!=v:
            sum_g*=f(u,n,path,v)
            sum_g=sum_g%1000000007
    return sum_g

def main():
    n = int(input())
    path = [[] for _ in range(n+1)]
    for _ in range(n-1):
        x,y = map(int,input().split())
        path[x].append(y)
        path[y].append(x)
#    print(path)
    print((f(0,n,path,1)+g(0,n,path,1))%1000000007)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	P
# CreatedDate:  2020-05-31 17:39:34 +0900
# LastModified: 2020-05-31 17:50:01 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd

def f(prev_f,n,path,u):
    sum_f=1
    for v in path[u]:
        if prev_f!=v:
            sum_f*=(f(u,n,path,v)+g(u,n,path,v))
            sum_f%=1000000007
    return sum_f

def g(prev_g,n,path,u):
    sum_g=1
    for v in path[u]:
        if prev_g!=v:
            sum_g*=f(u,n,path,v)
            sum_f%=1000000007
    return sum_g

def main():
    n = int(input())
    path = [[] for _ in range(n+1)]
    for _ in range(n-1):
        x,y = map(int,input().split())
        path[x].append(y)
        path[y].append(x)
#    print(path)
    print((f(0,n,path,1)+g(0,n,path,1))%1000000007)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	P
# CreatedDate:  2020-05-31 17:39:34 +0900
# LastModified: 2020-05-31 17:45:23 +0900
#


import os
import sys
#import numpy as np
#import pandas as pd

def f(prev_f,n,path,u):
    sum_f=1
    for v in path[u]:
        if prev_f!=v:
            sum_f*=(f(u,n,path,v)+g(u,n,path,v))
    return sum_f

def g(prev_g,n,path,u):
    sum_g=1
    for v in path[u]:
        if prev_g!=v:
            sum_g*=f(u,n,path,v)
    return sum_g

def main():
    n = int(input())
    path = [[] for _ in range(n+1)]
    for _ in range(n-1):
        x,y = map(int,input().split())
        path[x].append(y)
        path[y].append(x)
#    print(path)
    print((f(0,n,path,1)+g(0,n,path,1))%1000000007)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

Solution code:


def submit():
    n = int(input())
    edge = {i: [] for i in range(1, n + 1)}
    for _ in range(n - 1):
        x, y = map(int, input().split())
        edge[x].append(y)
        edge[y].append(x)

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

    BLACK = 1
    WHITE = 0
    MODP = 10 ** 9 + 7
    def rec(node, color, parent):
        """
        nodeをcolorにした時、nodeを根とする部分木の色分けパターン
        """
        if dp[node][color] > 0:
            return dp[node][color]
            
        temp = 1
        if color == BLACK: # 黒
            for child in edge[node]:
                if child == parent:
                    continue
                temp *= rec(child, WHITE, node)
        else:
            for child in edge[node]:
                if child == parent:
                    continue
                temp *= (rec(child, BLACK, node) + rec(child, WHITE, node))
        
        dp[node][color] = temp % MODP
        return dp[node][color]
    
    rec(1, WHITE, 0)
    rec(1, BLACK, 0)
    print((dp[1][WHITE] + dp[1][BLACK]) % MODP)


submit()

Submission status: Runtime Error

Solution code:


def submit():
    n = int(input())
    edge = {i: [] for i in range(1, n + 1)}
    for _ in range(n - 1):
        x, y = map(int, input().split())
        edge[x].append(y)
        edge[y].append(x)

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

    BLACK = 1
    WHITE = 0
    MODP = 10 ** 9 + 7
    def rec(node, color, parent):
        """
        nodeをcolorにした時、nodeを根とする部分木の色分けパターン
        """
        temp = 1
        if color == BLACK: # 黒
            for child in edge[node]:
                if child == parent:
                    continue
                temp *= rec(child, WHITE, node)
        else:
            for child in edge[node]:
                if child == parent:
                    continue
                temp *= (rec(child, BLACK, node) + rec(child, WHITE, node))
        
        dp[node][color] = temp % MODP
        return dp[node][color]
    
    rec(1, WHITE, 0)
    rec(1, BLACK, 0)
    print((dp[1][WHITE] + dp[1][BLACK]) % MODP)


submit()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000)
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))

Submission status: Runtime Error

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

Submission status: Runtime Error

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: Runtime Error

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: Runtime Error

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

Submission status: Runtime Error

Solution code:
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, w = 1, 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: Runtime Error

Solution code:
from collections import defaultdict
mod = 10**9+7
N = int(input())
d = defaultdict(list)
for i in range(N-1):
    x, y = map(int, input().split())
    d[x].append(y)
    d[y].append(x)
    
def dfs(i, pi):
    b, w = 1, 1
    for ni in d[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(1, -1))%mod)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mod = 10**9+7
N = int(input())
d = defaultdict(list)
for i in range(N-1):
    x, y = map(int, input().split())
    d[x-1].append(y-1)
    d[y-1].append(x-1)
    
def dfs(i, pi):
    b, w = 1, 1
    for ni in d[i]:
        if ni == pi:
            continue
        nb, nw = dfs(ni, i)
        b = b*nw%mod
        w = w*(nw+nb)%mod
    return b, w

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mod = 10**9+7
N = int(input())
d = defaultdict(list)
for i in range(N-1):
    x, y = map(int, input().split())
    d[x-1].append(y-1)
    d[y-1].append(x-1)
    
def dfs(i, pi):
    b, w = 1, 1
    for ni in d[i]:
        if ni == pi:
            continue
        nb, nw = dfs(ni, i)
        b = b*nw%mod
        w = w*(nw+nb)%mod
    return b, w

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
mod = 10**9+7
N = int(input())
d = defaultdict(list)
for i in range(N-1):
    x, y = map(int, input().split())
    d[x-1].append(y-1)
    d[y-1].append(x-1)
    
def f(i):
    if flag[i]:
        return
    flag[i] = 1
    dp[i][0] = 1 #white
    dp[i][1] = 1 #black
    for j in d[i]:
        if not flag[j]:
            f(j)
            dp[i][0] = dp[i][0]*(dp[j][0] + dp[j][1])%mod
            dp[i][1] = dp[i][1]*dp[j][0]%mod
flag = [0] * N
dp = [[0,0] for i in range(N)]
f(0)
print(dp[0][0]+dp[0][1])

Submission status: Runtime Error

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

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: Runtime Error

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

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

# fi = open('sample4.in', 'r')
# raw_input = fi.readline

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


def dfs(i):
    G[i], A = None, G[i]
    black, white = 1, 1
    for j in A:
        G[j].remove(i)
        b, w = dfs(j)
        black = black * w % mod
        white = white * (b + w) % mod
    return [black, white]
print sum(dfs(1))

Submission status: Runtime Error

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

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 = [set() for i in xrange(n + 1)]
for i in xrange(n - 1):
    i, j = gets()
    G[i].add(j)
    G[j].add(i)


def dfs(i):
    G[i], A = None, G[i]
    black, white = 1, 1
    for j in A:
        G[j].remove(i)
        b, w = dfs(j)
        black *= w
        white *= b + w
    return [black, white]
print sum(dfs(1))

Submission status: Runtime Error

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

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

fi = open('sample4.in', 'r')
raw_input = fi.readline

n = get()
G = [set() for i in xrange(n + 1)]
for i in xrange(n - 1):
    i, j = gets()
    G[i].add(j)
    G[j].add(i)


def dfs(i):
    G[i], A = None, G[i]
    black, white = 1, 1
    for j in A:
        G[j].remove(i)
        b, w = dfs(j)
        black *= w
        white *= b + w
    return [black, white]
print sum(dfs(1))