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: Wrong Answer

Solution code:
import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range;R=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in R(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in R(base**n):s=[tb//(base**bt)%base for bt in R(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read;readline=sys.stdin.buffer.readline;input=lambda:sys.stdin.readline().rstrip()

########################################################################################################################################################################
# Verified by 
# https://atcoder.jp/contests/abc014/tasks/abc014_4
# https://atcoder.jp/contests/abc133/tasks/abc133_f

# import SparseTable
# initialize
# Tree() => n; (a,b);*(n-1)
# Tree(n) => (a,b);*(n-1)
# Tree(init=False); Tree.stdin(); => n; (a,b);*(n-1)
# Tree(init=False); Tree.listin(ls,index=0); => (a,b);*(n-1)

import sys,bisect,string,math,time,functools,random,fractions
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
rep=range
def Golf():n,*t=map(int,open(0).read().split())
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def MI():return map(int,input().split())
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def RA():return map(int,open(0).read().split())
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            org_inp.append(inp)
        else:
            inp=ls[i]
        if len(inp)==2:
            a,b=inp;c=1
        else:
            a,b,c=inp
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
    #h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def accum(ls):
    rt=[0]
    for i in ls:rt+=[rt[-1]+i]
    return rt
def bit_combination(n,base=2):
    rt=[]
    for tb in range(base**n):s=[tb//(base**bt)%base for bt in range(n)];rt+=[s]
    return rt
def gcd(x,y):
    if y==0:return x
    if x%y==0:return y
    while x%y!=0:x,y=y,x%y
    return y
def YN(x):print(['NO','YES'][x])
def Yn(x):print(['No','Yes'][x])
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

mo=10**9+7
inf=float('inf')
FourNb=[(-1,0),(1,0),(0,1),(0,-1)];EightNb=[(-1,0),(1,0),(0,1),(0,-1),(1,1),(-1,-1),(1,-1),(-1,1)];compas=dict(zip('WENS',FourNb));cursol=dict(zip('LRUD',FourNb))
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
read=sys.stdin.buffer.read
readline=sys.stdin.buffer.readline
input=lambda: sys.stdin.readline().rstrip()

class Tree:
    def __init__(self,inp_size=None,ls=None,init=True,index=1):
        self.LCA_init_stat=False
        self.ETtable=[]
        if init:
            if ls==None:
                self.stdin(inp_size,index=index)
            else:
                self.node_size=len(ls)+1
                self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def stdin(self,inp_size=None,index=1):
        if inp_size==None:
            self.node_size=int(input())
        else:
            self.node_size=inp_size
        self.edges,_=GI(self.node_size,self.node_size-1,index=index)
        return
    
    def listin(self,ls,index=0):
        self.node_size=len(ls)+1
        self.edges,_=GI(self.node_size,self.node_size-1,ls,index=index)
        return
 
    def dfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def bfs(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        while q:
            c=q.popleft()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
        return v
 
    def parent(self,x):
        return self.dfs(0,func=lambda pr,prv,nx,dist:pr,root_v=-1)
 
    def topological_sort(self,x):  # return topological sort of the tree
        tps=[]
        q=deque([x])
        v=[None]*self.node_size
        v[x]=0
        while q:
            c=q.popleft()
            tps.append(c)
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=0
        return tps
 
    def EulerTour(self,x):
        q=deque()
        q.append(x)
        self.depth=[None]*self.node_size
        self.depth[x]=0
        self.ETtable=[]
        self.ETdepth=[]
        self.ETin=[-1]*self.node_size
        self.ETout=[-1]*self.node_size
        cnt=0
        while q:
            c=q.pop()
            if c<0:
                ce=~c
            else:
                ce=c
                for nb,d in self.edges[ce]:
                    if self.depth[nb]==None:
                        q.append(~ce)
                        q.append(nb)
                        self.depth[nb]=self.depth[ce]+1
            self.ETtable.append(ce)
            self.ETdepth.append(self.depth[ce])
            if self.ETin[ce]==-1:
                self.ETin[ce]=cnt
            else:
                self.ETout[ce]=cnt
            cnt+=1
        return
    
    def doubling_LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.depth=[None]*self.node_size
            self.depth=self.bfs(0,func=lambda pr,prv,nxt,dist:prv+1)
            self.par=self.bfs(0,func=lambda pr,prv,nxt,dist:pr)
            self.db=[self.par]
            for i in range(self.node_size.bit_length()):
                #show(self.db)
                self.db+=[[self.db[-1][self.db[-1][i]] for i in range(self.node_size)]]
            self.LCA_init_stat=True
        dx=self.depth[x]
        dy=self.depth[y]
        if dx>dy:
            dx,dy=dy,dx
        c=self.node_size.bit_length()
        while c>0:
            if dx+c<=dy:
                x=self.db[c][x]
                dx+=1<<c
            c>>=1
        
        if x==y:
            return x
        
        c=self.node_size.bit_length()
        while c>0:
            if self.db[c][x]!=self.db[c][y]:
                x=self.db[c][x]
                y=self.db[c][y]
            c>>=1
        
        return self.par[x]
        
    def LCA_init(self,root):
        self.EulerTour(root)
        self.st=SparseTable(self.ETdepth,init_func=min,init_idl=inf)
        #self.st=SegTree(self.node_size*2-1,self.ETdepth,function=min,ide=inf)
        self.LCA_init_stat=True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            self.LCA_init(root)
        xin,xout=self.ETin[x],self.ETout[x]
        yin,yout=self.ETin[y],self.ETout[y]
        a=min(xin,yin)
        b=max(xout,yout,xin,yin)
        id_of_min_dep_in_et=self.st.query_id(a,b+1)
        return self.ETtable[id_of_min_dep_in_et]
 
    def __str__(self):
        return  str(self.edges)
 
    def show(self):
        if all([all([d==1 for nd,d in e]) for e in self.edges]):
            print( [[nd for nd,d in e] for e in self.edges] )
        else:
            print(self)
 
    def dfs2(self,x,func=lambda pr,prv,nx,dist:prv+dist,root_v=0):
        q=deque([x])
        v=[None]*self.node_size
        v[x]=root_v
        dfs_tr=[x]
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==None:
                    q.append(nb)
                    v[nb]=func(c,v[c],nb,d)
                    dfs_tr+=nb,
        return v,dfs_tr

show_flg=False
show_flg=True

ans=0
n=I()
tr=Tree(n)
v,root=tr.dfs2(0)
p=tr.parent(0)
x=[[1,1]for i in range(n)]
for c in root[::-1]:        
    x[p[c]][0]*=sum(x[c])
    x[p[c]][1]*=x[c][0]

print(sum(x[0]))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline

n = int(input())
C = [list(map(int,input().split())) for i in range(n-1)]
mod = 10**9 + 7

for i in range(n-1):
    for j in range(2):
        C[i][j] -= 1

ans = 0
M = [[] for i in range(n)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])

D = [[1,1] for i in range(n)]
MN = [len(M[i]) for i in range(n)]
# print("MN", MN)

V = [0] * n
Q = []
for i in range(1, n):
    if MN[i] == 1:
        Q.append(i)
        V[i] = 1

# print(Q)

s = 0
while s < len(Q):
    x = Q[s]
    for y in M[x]:
        if V[y] == 0:
            print("y",y)
            D[y][0] = (D[y][0] * sum(D[x])) % mod
            D[y][1] = (D[y][1] * D[x][0]) % mod
            MN[y] -= 1
            if (y != 0 and MN[y] == 1) or (y == 0 and MN[y] == 0):
                V[y] = 1
                Q.append(y)
    s += 1

print(sum(D[0]) % mod)

Submission status: Wrong Answer

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

MOD = 10 ** 9 + 7
def dfs(v, pv):
    dp[v][0] = dp[v][1] = 1
    for nv in edge[v]:
        if nv == pv: continue
        dfs(nv, v)
        dp[v][0] *= dp[nv][0] + dp[nv][1]
        dp[v][0] %= MOD
        dp[v][1] *= dp[nv][0]
        dp[v][1] %= MOD

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

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

dp = [[0] * 2 for _ in range(10**5+10)]
dfs(0,-1)

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**9)
MOD = 10 ** 9 + 7
def dfs(v, pv):
    dp[v][0] = dp[v][1] = 1
    for nv in edge[v]:
        if nv == pv: continue
        dfs(nv, v)
        dp[v][0] *= dp[nv][0] + dp[nv][1]
        dp[v][0] %= MOD
        dp[v][1] *= dp[nv][0]
        dp[v][1] %= MOD

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

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

dp = [[0] * 2 for _ in range(10**5+10)]
dfs(0,-1)

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

Submission status: Wrong Answer

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

def memodp(DPW, DPB, near, x, FLAG):
    if DPW[x] + DPB[x] > 2:
        return DPB[x] + DPW[x]
    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]
        return DPW[x] + DPB[x]


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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6) 

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: Wrong Answer

Solution code:
import sys

sys.setrecursionlimit(10**6) 

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: Wrong Answer

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


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)
def DFS(node):
    global dp
    global adj
    global visited
    if(dp[node][0]>-1):
        return (dp[node][0],dp[node][1])
    visited[node]=1
    numofw=1
    numofb=1
    for j in adj[node]:
        if(visited[j]==0):
            white=(DFS(j))[0]
            black=(DFS(j))[1]
            numofw*=(white+black)
            numofb*=white
            numofw%=1000000007
            numofb%=1000000007
    dp[node][0]=numofw
    dp[node][1]=numofb
    return (numofw,numofb)
n=int(input())
adj=[[] for i in range(n+1)]
for i in range(n-1):
    l=input().split()
    u=int(l[0])
    v=int(l[1])
    adj[u].append(v)
    adj[v].append(u)
dp=[[-1 for i in range(2)]for i in range(n+1)]
visited=[0 for i in range(n+1)]
x=DFS(1)
print(x[0]+x[1])

Submission status: Wrong Answer

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)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
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
        dp[1][p] = b
print(dp[0][0] + dp[1][0])

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
setrecursionlimit(1<<30)
mod=pow(10,9)+7
def f(x,p,c):
  if z[x][c]==-1:
    z[x][c]=1 if (len(v[x])==1 and v[x][0]==p) or len(v[x])==0 else 0
    for y in v[x]:
      if y!=p:
      	z[x][c]=(z[x][c]+f(y,x,1)+c*f(y,x,0))%mod
  return z[x][c]
n=input()
v=[[] for _ in xrange(n)]
for x,y in [map(int,raw_input().split()) for _ in xrange(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in xrange(n)]
print (f(0,-1,0)+f(0,-1,1))%mod

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
MOD=10**9+7
def dfs(v,p):
    if seen[v]:
        return dp[v]
    seen[v]=1
    if not G[v]:
        dp[v]=[1,1]
        return [1,1]
    b,w=1,1
    for nv in G[v]:
        if(nv==p):
            continue
        w=(w*sum(dfs(nv,v)))%MOD
        b=(b*dfs(nv,v)[1])%MOD
    dp[v]=[b,w]
    return [b,w]
    
N=int(input())
G=[[] for i in range(N)]
dp=[[0,0] for i in range(N)]
seen=[0]*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)
print(sum(dfs(0,-1)))

Submission status: Wrong Answer

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=0
    if c:
        for i in es[v]:
            if i-p:
                ans+=dfs(i,0,v)+dfs(i,1,v)
    else:
        for i in es[v]:
            if i-p:
                ans+=dfs(i,1,v)
    # print(ans,c,v)
    dp[v][c]=max(ans%mod,1)
    return max(ans%mod,1)
print((dfs(0,0,-1)+dfs(0,1,-1))%mod)

Submission status: Wrong Answer

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=[0]*N#根が白
    g=[0]*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()