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:
#!/usr/bin/env pypy3
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N=I()
    f=[1]*N#根が白
    g=[1]*N
    
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        x,y=MI()
        x-=1
        y-=1
        adj[x].append(y)
        adj[y].append(x)
        
    Ld=[[]for _ in range(N)]#深さ別
    Lp=[0]*N
    Md=0#最深部
    
    import queue
    
    q=queue.Queue()
    q.put((0,-1,0))#v,p,d
    
    while not q.empty():
        v,p,d=q.get()
        Ld[d].append(v)
        Lp[v]=p
        Md=max(d,Md)
        for i in range(len(adj[v])):
            nv=adj[v][i]
            if nv!=p:
                q.put((nv,v,d+1))
                

        
    for i in range(Md-1,-1,-1):
        for j in range(len(Ld[i])):
            v=Ld[i][j]
            tempf=1
            tempg=1
            for k in range(len(adj[v])):
                pv=adj[v][k]
                if pv!=Lp[v]:
                    tempf*=(f[pv]+g[pv])
                    tempg*=f[pv]
                    tempf%=mod
                    tempg%=mod
                
            f[v]=tempf
            g[v]=tempg
            
    print(f[0]+g[0])

                
    

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N, *XY = map(int,open(0).read().split())
MOD = 10**9 + 7

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

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

def dp(node, color, parent):
    if memo[node][color] != -1:
        return memo[node][color]
    output = 1
    for child in neighbor[node]:
        if child == parent:
            pass
        else:
            tmp = dp(child, 0, node)
            if color == 0:
                tmp += dp(child, 1, node)
            output *= tmp
    memo[node][color] = output
    return output

print(dp(0,0,-1) + dp(0,1,-1))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(1000000000)

N = int(input())

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

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

def dp(node, color, parent):
    if memo[node][color] != -1:
        return memo[node][color]
    output = 1
    for child in neighbor[node]:
        if child == parent:
            pass
        else:
            tmp = dp(child, 0, node)
            if color == 0:
                tmp += dp(child, 1, node)
            output *= tmp
    memo[node][color] = output
    return output

print(dp(0,0,-1) + dp(0,1,-1))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
e = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

mod = 10**9+7

def dfs(i=0, r=-1):
    b = w = 1
    for j in e[i]:
        if j == r:
            continue
        bb, ww = dfs(j, i)
        b = b * ww % mod
        w = w * (bb + ww) % mod
    return b, w

print(sum(dfs()))

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
mod = 10**9+7
graph = [[] for i in range(n+1)]
deg = [0 for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
stack = []
for i in range(2,n+1):
  if deg[i] == 1:
    stack.append(i)
deg[1] += 1
dp = [[] for i in range(n+1)]
cnt = [-1 for i in range(n+1)]
while stack:
  x = stack.pop()
  if dp[x]:
    bl = 1
    wh = 1
    for i in dp[x]:
      ibl = i%mod
      iwh = i//mod
      wh = (wh*(ibl+iwh))%mod
      bl = (bl*iwh)%mod
    cnt[x] = wh*mod+bl
  else:
    cnt[x] = mod+1
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(cnt[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
print((cnt[1]%mod+cnt[1]//mod)%mod)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
MOD = 10**9+7
N = int(input())
edge = [[] for _ in range(N+1)]
dp = [[0]*2 for i in range(100005)]
# dp[v][c]: 頂点vを色cの根とする部分木の塗り分け方の総数
# 葉が決まると順々に求まっていく
for i in range(N-1):
    x,y = map(int,input().split())
    edge[x].append(y)
    edge[y].append(x)

# 0:white,1:black
def dfs(v,last=-1):
    dp[v][0] = 1
    dp[v][1] = 1
    for nv in edge[v]:
        if nv == last:
            continue
        dfs(nv, v)
        dp[v][0] = dp[v][0] * ((dp[nv][0] + dp[nv][1]) % MOD) % MOD
        dp[v][1] = dp[v][1] * dp[nv][0] % MOD


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

Submission status: Wrong Answer

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

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

def dfs(v, pv):
    blk, wht = 1, 1
    for nv in g[v]:
        if nv == pv: continue
        nb, nw = dfs(nv, v)
        blk *= nw
        wht *= nb + nw
    return blk, wht

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

Submission status: Wrong Answer

Solution code:
MOD = 10**9+7

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

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

for e in E:
    tree[e[0] - 1].append(e[1] - 1)
    tree[e[1] - 1].append(e[0] - 1)

visited = [0 for _ in range(N)]
visited[0] = 1

order = [None for _ in range(N)]
od = 0
order[0] = 0

parent = [0 for _ in range(N)]
parent[0] = -1

stack = [0]

while stack:
    node = stack.pop()
    for adj in tree[node]:
        if not visited[adj]:
            visited[adj] = 1
            od += 1
            order[od] = adj
            parent[adj] = node
            stack.append(adj)

dp = [[1, 1] for _ in range(N)]

for node in order[::-1]:
    for adj in tree[node]:
        if parent[node] == adj:
            continue
        dp[node][0] *= dp[adj][0] + dp[adj][1]
        dp[node][0] %= MOD
        dp[node][1] *= dp[adj][0]
        dp[node][1] %= MOD

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

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    mod = 10**9 + 7

    N = int(input())

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


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

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

    for x in order[::-1]:
        b,w = dp_b[x], dp_w[x]
        p = parent[x]
        dp_b[p] *= w%mod
        dp_w[p] *= (b+w)%mod

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

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

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

print(sum(dfs()))

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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

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

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

Submission status: Wrong Answer

Solution code:
n = int(input())
xy = [list(map(int,input().split())) for _ in range(n-1)]
xy = [sorted(xy[i]) for i in range(n-1)]
#print(xy)
xy = sorted(xy)

ans = 0
v = [0 for i in range(n)]

for i in range(n-1):
    #print(v)
    x = xy[i][0]-1
    y = xy[i][1]-1

    if not(v[x] or v[y]):
        v[x] = 1
        v[y] = 2

    elif v[x] and (not v[y]):
        if v[x]==1:
            v[y] = 2
        else:
            v[y] = 1
    elif v[y] and (not v[x]):
        if v[y]==1:
            v[x] = 2
        else:
            v[x] = 1

    elif v[x] and v[y]:
        if v[x]==v[y]:
            ans = -1
        else:
            continue
    
mm1 = 0
mm2 = 0
for i in range(n):
    if v[i] == 1:
        mm1 += 1
    elif v[i]==2:
        mm2 += 1

if ans != -1:
    ans += (2**mm1)-1
    ans += (2**mm2)-1

print(ans+1)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import random

import sys
sys.setrecursionlimit(100000000)

# N, W = 100, 20000
# W_V = [[random.randint(1,1000000), random.randint(1,1000)] for i in range(N)]
N = int(raw_input())
ADG_VERTICES= defaultdict(list)
panting_cache = {}
for i in range(N-1):
    u, v = map(int, raw_input().split())
    ADG_VERTICES[u].append(v)
    ADG_VERTICES[v].append(u)

BLACK_COLOR = 1
WHITE_COLOR = 0
MOD_VAL = int(1e9 + 7)
def get_ways_to_paint_vertices(parent_color, parent_vertex, vertex):
    if ADG_VERTICES[vertex] == [parent_vertex]:
        if parent_color == BLACK_COLOR:
            return 1
        else:
            return 2

    if (parent_color,  parent_vertex, vertex) in panting_cache:
        return panting_cache[parent_color,  parent_vertex, vertex]
    ans1 = 1
    ans2 = 0
    for adg_vertex in ADG_VERTICES[vertex]:
        if adg_vertex != parent_vertex:
            ans1 *= get_ways_to_paint_vertices(WHITE_COLOR, vertex, adg_vertex)
    if parent_color != BLACK_COLOR:
        ans2 = 1
        for adg_vertex in ADG_VERTICES[vertex]:
            if adg_vertex != parent_vertex:
                ans2 *= get_ways_to_paint_vertices(BLACK_COLOR, vertex, adg_vertex)

    ans = ans1 + ans2
    if ans >= MOD_VAL:
        ans -= MOD_VAL
    panting_cache[parent_color, parent_vertex, vertex] = ans
    return ans


print get_ways_to_paint_vertices(None, 0, 1)

Submission status: Wrong Answer

Solution code:
N, = map(int, input().split())
M = 10**9+7
d = [set() for _ in range(N+1)]
from collections import deque
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].add(b)
    d[b].add(a)


stack = deque([1])
leafs = set()
p = [0 for _ in range(N+1)]
vs = set([1])
vv = list()
while stack:
    v = stack.popleft()
    vv.append(v)
    for u in d[v]:
        if u in vs:
            continue
        p[u] = v
        vs.add(u)
        stack.append(u)

dp1 = [-1 for _ in range(N+1)]
dp2 = [-1 for _ in range(N+1)]
for v in vv[::-1]:
    if len(d[v]) == 1 and v != 1:
        dp1[v] = 1
        dp2[v] = 1
        continue
    xx=yy=1
    for u in d[v]:
        if p[v] == u:
            continue
        xx = (xx * dp2[u])%M
        yy = (yy * (dp1[u] + dp2[u]))%M
    dp1[v] = xx
    dp2[v] = yy
print(dp1[1]+dp2[1])

Submission status: Wrong Answer

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


n = int(input())
info = [list(map(int, input().split())) for i in range(n-1)]
MOD = 10**9

tree = [[] for i in range(n)]
for i in range(n-1):
    x, y = info[i]
    x -= 1
    y -= 1
    tree[x].append(y)
    tree[y].append(x)

def solve(pos):
    b = 1
    w = 1
    flag = False
    for next_pos in tree[pos]:
        if not visited[next_pos]:
            visited[next_pos] = True
            flag = True
            tmp_b, tmp_w = solve(next_pos)
            w *= (tmp_b + tmp_w)
            b *= tmp_w
            w %= MOD
            b %= MOD
    if not flag:
        black[pos] = 1
        white[pos] = 1
        return (black[pos], white[pos])
    else:
        black[pos] = b
        white[pos] = w
        return (black[pos], white[pos])

black = [0]*n
white = [0]*n
visited = [False]*n
visited[0] = True
print(sum(solve(0)) % MOD)

Submission status: Wrong Answer

Solution code:
from collections import deque
import copy
p = 10**9+7
N = int(input())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
T = {i:[] for i in range(1,N+1)}
T[1] = G[1][:]
T[1].insert(0,0)
que = deque([1])
while que:
    cur = que.popleft()
    for x in T[cur][1:]:
        T[x] = [cur]
        for y in G[x]:
            if y!=cur:
                T[x].append(y)
        que.append(x)
T1 =copy.deepcopy(T)
C = []
stack = [1]
while stack:
    if len(T1[stack[-1]])==1:
        C.append(stack.pop())
    else:
        stack.append(T1[stack[-1]].pop())
dp = [[1 for _ in range(2)] for _ in range(N+1)]
for i in range(N):
    x = C[i]
    if len(T[x])>1:
        for y in T[x][1:]:
            dp[x][0] = (dp[x][0]*(dp[y][0]+dp[y][1]))%p
            dp[x][1] = (dp[x][1]*dp[y][0])%p
print(dp[1][0]+dp[1][1])

Submission status: Wrong Answer

Solution code:

from functools import lru_cache
import sys
sys.setrecursionlimit(10**9)


def len_max(mat):
    for i in range(len(mat)):
        if len(mat[i])>1:
            return i

n = int(input())
adj_mat =[[] for i in range(n)]



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

root = len_max(adj_mat) or 0


@lru_cache(None)
def cal(parent, node, col):

    nei = adj_mat[node]
    if len(nei)==1:
        if col=='w':
            return 2
        else:
            return 1 
    
    else:
        
        if col=='w':
            sb=1
            sw=1
            for k in nei:
                if k==parent:
                    continue
                sw*=cal(node, k, 'w')
                sb*=cal(node, k, 'b')
            return sb+sw

        else:
            sw=1
            for k in nei:
                if k==parent:
                    continue
                sw*=cal(node, k, 'w')
            return sw


ans = cal(None,root,'w')
if n==0:
    print(0)
elif n==1:
    print(2)
elif n==2:
    print(3)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u=0,pu=-1):
        w,b=1,1
        for v in to[u]:
            if v==pu:continue
            dfs(v,u)
            vw,vb=dp[v]
            w*=(vw+vb)
            b*=vw
        dp[u]=[w,b]

    to=defaultdict(list)
    n=int(input())
    for _ in range(n-1):
        x,y=map(int1,input().split())
        to[x].append(y)
        to[y].append(x)
    dp=[[0]*2 for _ in range(n)]
    dfs()
    print(sum(dp[0]))

main()

Submission status: Wrong Answer

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**9)
    from collections import deque
    mod = 10**9+7
    N = int(input())
    G = [[] for _ in range(N)]
    for _ in range(N-1):
        x, y = map(int, input().split())
        G[x-1].append(y-1)
        G[y-1].append(x-1)
    que = deque([0])
    children = [[] for _ in range(N)]
    while que:
        v = que.pop()
        for nv in G[v]:
            if children[nv]:
                continue
            children[v].append(nv)
            que.append(nv)   
    memo = [[-1]*2 for _ in range(N)]
    def dp(i, c):
        if memo[i][c] >=0:
            return memo[i][c]%mod
        if c == 1:
            res = 1
            for j in children[i]:
                res*=dp(j, 0)
                res%=mod
            memo[i][c] = res
        else:
            res = 1
            for j in children[i]:
                res*=(dp(j, 0)+dp(j, 1))
                res%=mod
            memo[i][c]= res
        return memo[i][c]%mod
    print(dp(0, 0)+dp(0, 1))
main()

Submission status: Wrong Answer

Solution code:

import sys
sys.setrecursionlimit(10**9)
from collections import deque
mod = 10**9+7
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
que = deque([0])
children = [[] for _ in range(N)]
while que:
    v = que.pop()
    for nv in G[v]:
        if children[nv]:
            continue
        children[v].append(nv)
        que.append(nv)   
memo = [[-1]*2 for _ in range(N)]
def dp(i, c):
    if memo[i][c] >=0:
        return memo[i][c]
    if not children[i]:
        memo[i][c] = 1
        return 1
    if c == 1:
        res = 1
        for j in children[i]:
            res*=dp(j, 0)
            res%=mod
        memo[i][c] = res
    else:
        res = 1
        for j in children[i]:
            res*=(dp(j, 0)+dp(j, 1))
            res%=mod
        memo[i][c]= res
    return memo[i][c]
print(dp(0, 0)+dp(0, 1))

Submission status: Wrong Answer

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

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

    v = [False] * N
    def dp(n):
        v[n] = True
        tb = 1
        tw = 1
        for i in E[n]:
            if v[i]:
                continue
            b, w = dp(i)
            tb *= w
            tw *= w + b
        return tb, tw
    return sum(dp(0))


print(main())

Submission status: Wrong Answer

Solution code:
def solve(n, g):
    mod = 10 ** 9 + 7

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

    # dp[j][0/1] := 頂点jを0/1とする場合のjを親とする部分木の塗り方の状態数
    # dp[j][0] = reduce(mul, (dp[k][0] + dp[k][1] for k in g[j]))
    # dp[j][1] = reduce(mul, (dp[k][0] for k in g[j]))

    def dfs(v, parent=-1):
        for u in g[v]:
            if u == parent:
                continue
            dfs(u, v)
            dp[v][0] = dp[v][0] * (dp[u][0] + dp[u][1]) % mod
            dp[v][1] = dp[v][1] * dp[u][0] % mod

    dfs(0)

    return sum(dp[0])


if __name__ == '__main__':
    import sys

    sys.setrecursionlimit(10 ** 7)

    input = sys.stdin.readline

    n = int(input())
    g = tuple(set() for _ in range(n))
    for _ in range(n - 1):
        x, y = (int(j) - 1 for j in input().rstrip().split())
        g[x].add(y)
        g[y].add(x)
    print(solve(n, g))

# 適当な頂点を根とする

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    for _ in range(n-1):
        x,y=map(int,input().split())
        x-=1; y-=1
        E[x].append(y)
        E[y].append(x)
    dp=[[-1]*2 for _ in range(n)] # dp[i][color] 白:0 黒:1
    def dfs(v,p)->NoneType:
        if(dp[v][0]!=-1 and dp[v][1]!=-1): return
        white=black=1
        for nv in E[v]:
            if(nv==p): continue
            dfs(nv,v)
            white*=dp[nv][0]+dp[nv][1] # 白は常にOK
            white%=MOD
            black*=dp[nv][0]           # 黒は子の全てが白のときのみ
            black%=MOD
        dp[v][0]=white
        dp[v][1]=black
    dfs(0,-1)
    print(dp[0][0]+dp[0][1])
resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 9)

def main():
  N = int(input())
  XY = [tuple(map(int,input().split())) for _ in range(N-1)]
  MOD =10**9+7
  
  E = [[] for _ in range(N)]
  for x,y in XY:
    x -= 1
    y -= 1
    E[x].append(y)
    E[y].append(x)
  
  # dp[v][c]:根がvである部分木において、vを色cで塗ったときの塗り方のパターン
  # vの子をu1,u2...unとすると、vが白ならuxは白でも黒でもいい。
  # vが黒ならuxは白でないといけない。
  # uxを根とする部分木の塗り方パターン数を掛け合わせたものが、
  # vを根とする部分木の塗り方のパターン数になる。
  dp = [[0 for _ in range(2)] for _ in range(N)]
  def dfs(v,c,s):
    dp[v][c] = 1
    for u in E[v]:
      if u != s:
        if c == 0: #vが白の場合
          dp[v][c] *= (dfs(u,0,v)+dfs(u,1,v))
        else: #vが黒の場合
          dp[v][c] *= dfs(u,0,v)
    dp[v][c] %= MOD
    return dp[v][c]

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

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
n=int(input())
s=[[]for i in range(n+1)]
m=10**9+7
for i in range(n-1):
    x,y=map(int,input().split())
    s[x].append(y)
    s[y].append(x)
t=[[0,0]for i in range(n+1)]
def f(a,b):
    t[a][0]=t[a][1]=1
    for i in s[a]:
        if i!=b:
            f(i,a)
            t[a][0]=(t[a][0]*(t[i][0]+t[i][1]))%m
            t[a][1]=(t[a][1]*t[i][0])%m
f(1,0)
print(sum(t[1]))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100005)
mod=1000000007
# https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0106_educational_dp_2

def dfs(v,a):
    w=b=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 i 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)