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 python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])
#B
def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return

#C
def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return

#D
def D():
    n = I()
    a = LI()
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    dp = [[0]*(n+1) for i in range(n)]
    for le in range(1,n):
        for l in range(n-le):
            r = l+le+1
            res = float("inf")
            for i in range(l+1,r):
                m = dp[l][i]+dp[i][r]
                if m < res:
                    res = m
            res += a[r]-a[l]
            dp[l][r] = res
    print(dp[0][n])
    return

#E
def E():

    n = I()
    a = LIR(n)
    m = 1<<n
    dp = [0]*m
    dp[0] = 1
    a = [[j for j in range(n) if a[i][j]] for i in range(n)]
    bit_count = [-1]
    for i in range(n):
        for j in range(len(bit_count)):
            bit_count.append(bit_count[j]+1)
    for k in range(1,m):
        i = bit_count[k]
        for j in a[i]:
            bj = 1<<j
            if bj > k:
                break
            if not k&bj:
                continue
            nk = k^bj
            dp[k] += dp[nk]
    print(dp[m-1]%mod)
#F
def F():
    def dfs(x):
        for y in v[x]:
            if d[y]:
                d[y] = 0
                fy,gy = dfs(y)
                f[x] *= gy
                f[x] %= mod
                g[x] *= fy
                g[x] %= mod
        f[x] += g[x]
        return f[x],g[x]

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    f = [1]*n
    g = [1]*n
    d = [1]*n
    d[0] = 0
    print(dfs(0)[0])
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007


#A
def A():
    n,k = LI()
    a = LI()
    dp = [0 for i in range(k+1)]
    f = [0 for i in range(k+1)]
    for i in range(k+1):
        if not f[i]:
            for j in a:
                if i-j >= 0:
                    dp[i] = 1-dp[i-j]
                    if dp[i] == 0:
                        break
            else:
                dp[i] = 1
    print(["First","Second"][dp[k]])
#B
def B():
    n = I()
    a = LI()
    ma = n*(n+1)//2
    su = sum(a)
    s = [1 for i in range(n+1)]
    for i in range(1,n):
        s[i+1] = s[i]+n-i+1
    d = [None for i in range(ma+1)]
    d[0] = 0
    k = 1
    for i in range(1,n+1):
        for j in range(n+1-i):
            d[k+j] = i
        k += n+1-i
    k = n%2
    dp = [su if (d[i]+k)%2 else -su for i in range(ma+1)]
    dp[0] = 0
    if k:
        for i in range(n):
            dp[i+1] = a[n-1-i]
    else:
        for i in range(n):
            dp[i+1] = -a[n-1-i]
    for i in range(1,ma):
        r = n-1-(i-s[d[i]])
        l = r+1-d[i]
        j = i+(n-d[i])
        j2 = j+1
        if (d[i]+k)%2:
            if r < n-1:
                if a[r+1]+dp[i] > dp[j]:
                    dp[j] = a[r+1]+dp[i]
            if l > 0:
                if a[l-1]+dp[i] > dp[j2]:
                    dp[j2] = a[l-1]+dp[i]
        else:
            if r < n-1:
                if -a[r+1]+dp[i] < dp[j]:
                    dp[j] = -a[r+1]+dp[i]
            if l > 0:
                if -a[l-1]+dp[i] < dp[j2]:
                    dp[j2] = -a[l-1]+dp[i]
    print(dp[ma])
    return

#C
def C():
    def comb(a,b):
        return fact[a]*inv[b]*inv[a-b]%mod

    n,k = LI()
    a = LI()
    """
    fact = [1]
    for i in range(n+k):
        fact.append(fact[-1]*(i+1)%mod)
    inv = [1]*(n+k+1)
    inv[n+k] = pow(fact[n+k],mod-2,mod)
    for i in range(n+k)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod
    f = [comb(i+n-1,n-1) for i in range(k+1)]
    for i in a:
        for j in range(k-i)[::-1]:
            f[j+i+1] -= f[j]
            f[j+i+1] %= mod
    print(f[k])
    """
    dp = [[0]*(k+1) for i in range(n+1)]
    for i in range(k+1):
        dp[0][i] = 1
    for i in range(n):
        ni = i+1
        ai = a[i]
        for j in range(k+1):
            if j >= ai+1:
                dp[ni][j] = (dp[i][j]-dp[i][j-ai-1])%mod
            else:
                dp[ni][j] = dp[i][j]
        if i < n-1:
            for j in range(k):
                dp[ni][j+1] += dp[ni][j]
                dp[ni][j+1] %= mod
    print(dp[n][k]%mod)
    return

#D
def D():
    n = I()
    a = LI()
    a.insert(0,0)
    for i in range(n):
        a[i+1] += a[i]
    dp = [[0]*(n+1) for i in range(n)]
    for le in range(1,n):
        for l in range(n-le):
            r = l+le+1
            res = float("inf")
            for i in range(l+1,r):
                m = dp[l][i]+dp[i][r]
                if m < res:
                    res = m
            res += a[r]-a[l]
            dp[l][r] = res
    print(dp[0][n])
    return

#E
def E():

    n = I()
    a = LIR(n)
    m = 1<<n
    dp = [0]*m
    dp[0] = 1
    a = [[j for j in range(n) if a[i][j]] for i in range(n)]
    bit_count = [-1]
    for i in range(n):
        for j in range(len(bit_count)):
            bit_count.append(bit_count[j]+1)
    for k in range(1,m):
        i = bit_count[k]
        for j in a[i]:
            bj = 1<<j
            if bj > k:
                break
            if not k&bj:
                continue
            nk = k^bj
            dp[k] += dp[nk]
    print(dp[m-1]%mod)
#F
def F():
    def dfs(x):
        for y in v[x]:
            if d[y]:
                d[y] = 0
                fy,gy = dfs(y)
                f[x] *= (fy+gy)
                f[x] %= mod
                g[x] *= fy
                g[x] %= mod
        return f[x],g[x]

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        x,y = LI()
        x -= 1
        y -= 1
        v[x].append(y)
        v[y].append(x)
    f = [1]*n
    g = [1]*n
    d = [1]*n
    d[0] = 0
    print(sum(dfs(0)))
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    F()

Submission status: Wrong Answer

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

MOD = 1e9+7

n = int(input())

dp = [[-1]*2 for i in range(n+1)]

g = [list() for i in range(n)]

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

def dfs(u, p, c):
    
    if dp[u][c]!=-1:
        return dp[u][c]

    ans=1
    for v in g[u]:
        if v==p:
            continue
        ans = (ans*((dfs(v, u, 0)+(dfs(v, u, 1) if c==0 else 0))%MOD))%MOD
    
    dp[u][c]=ans
    return ans

print(str((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD).split('.')[0])

Submission status: Wrong Answer

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

MOD = 1e9+7

n = int(input())

dp = [[-1]*2 for i in range(n+1)]

g = [list() for i in range(n)]

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

def dfs(u, p, c):
    
    if dp[u][c]!=-1:
        return dp[u][c]

    ans=1
    for v in g[u]:
        if v==p:
            continue
        ans = (ans*(dfs(v, u, 0)+(dfs(v, u, 1) if c==0 else 0)))%MOD
    
    dp[u][c]=ans
    return ans

print(int((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD))

Submission status: Wrong Answer

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

MOD = 1e9+7

n = int(input())

g = [list() for i in range(n)]

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

def dfs(u, p, c):
    
    

    ans=1
    for v in g[u]:
        if v==p:
            continue
        ans = (ans*(dfs(v, u, 0)+(dfs(v, u, 1) if c==0 else 0)))%MOD
    
    return ans

print(int((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())
nodes = [[] for _ in range(n+1)]
done = [1 for _ in range(n+1)]
mod = 1e9+7
def dfs(next,pre):
    w=1
    b=1
    for v in nodes[next]:
        if v!=pre:
            white,black= dfs(v,next)
            w *= (white+black)%mod
            b *= white
            w%=mod
            b%=mod
    return (w,b)

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

ans = dfs(1,-1)
print(int(sum(ans)%mod))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())
nodes = [[] for _ in range(n+1)]
done = [1 for _ in range(n+1)]
mod = 1e9+7
def dfs(next):
    w=1
    b=1
    for v in nodes[next]:
        if done[v]:
            done[v]=0
            white,black= dfs(v)
            w *= (white+black)%mod
            b *= white
            w%=mod
            b%=mod
    return (w,b)

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

ans = dfs(1)
print(int(sum(ans)%mod))

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(100000000)
n = int(input())
nodes = [[] for _ in range(n+1)]
done = [1 for _ in range(n+1)]
mod = 1e9+7
def dfs(next):
    w=1
    b=1
    for v in nodes[next]:
        if done[v]:
            done[v]=0
            white,black= dfs(v)
            w *= white+black
            b *= white
            w%=mod
            b%=mod
    return (w,b)

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

ans = dfs(1)
print(int(sum(ans)%mod))

Submission status: Wrong Answer

Solution code:
# @author 

import sys


class PIndependentSet:
    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)
        MOD = 10 ** 9 + 7

        def dfs(s):
            done[s] = 1
            dp[s][0] = 1
            dp[s][1] = 1
            for x in adj[s]:
                if done[x]:
                    continue
                _in = True
                dfs(x)
                dp[s][0] = (dp[s][0] * dp[x][1]) % MOD
                dp[s][1] = (dp[s][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)]
        done = [0] * n
        dfs(0)

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

solver = PIndependentSet()
input = sys.stdin.readline

solver.solve()

Submission status: Wrong Answer

Solution code:
import fileinput
from collections import defaultdict

def longest_path(edges):
    if not edges:
        return 0

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

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) == 1:
        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: Wrong Answer

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 len(H[r]) <= 1:
        dp[r][bw] = 1
        return 1
    else:
        cs = H[r] - {p}
        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: Wrong Answer

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(10000000)
MOD = 10**9+7
E = {}
for i in range(0,N+1):
    E[i] = []
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

dp = [ [0 for i in range(2)] for j in range(100100)]

def dfs(c,p):
    dp[c][0],dp[c][1] = 1,1
    for to in E[c]:
        if to != p:
            dfs(to,c)
            dp[c][0] = dp[c][0]*(dp[to][0] + dp[to][1]) % MOD
            dp[c][1] = (dp[c][1]*dp[to][0]) % MOD

dfs(0,-1)

ans = (dp[0][0] + dp[0][1]) % MOD

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**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
        cw*=(eb+ew)
    ansb[x]=cb
    answ[x]=cw
    return (cb,cw)

print(sum(dfs(0)))

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

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(500000)

n = int(input())
mod = 10 ** 9 + 7
node = [[] for _ in range(n)]
for i in range(n - 1):
    x, y = map(int, input().split())
    node[x - 1].append(y - 1)
    node[y - 1].append(x - 1)

def f(x, prev):
    cnt = 1
    for i in node[x]:
        if i != prev:
            cnt *= g(i, x)
            cnt %= mod
    return g(x, prev) + cnt

def g(x, prev):
    cnt = 1
    for i in node[x]:
        if i != prev:
            cnt *= f(i, x)
            cnt %= mod
    return cnt

print(f(0, -1))

Submission status: Wrong Answer

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


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

#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(0,-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(0)+whi(0))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N = int(input())
# T = [ [int(j) for j in input().split()] for _ in range(N-1)]

from collections import defaultdict

MOD = 10**9 + 7
T = defaultdict(list)
for i in range(N-1):
    x,y = map(int, input().split())
    x,y = min(x,y), max(x,y)
    T[x] += [y]

# DP = defaultdict(lambda : 0 )
DP = [[0] * (N+1) for _ in range(2)]
# visited = [False] * (N+1)

# 0 for black
# 1 for white

def dfs(c,n):
    if len(T[n]) == 0:
        DP[0][n] = 1
        DP[1][n] = 1
        return 1

    if c == 0:
        black = 0
        for child_n in T[n]:
            black += dfs(1, child_n) % MOD
        DP[0][n] = black % MOD
        return black % MOD
    else:
        white = 0
        for child_n in T[n]:
            white += dfs(0, child_n) + dfs(1, child_n) % MOD
        DP[1][n] = white % MOD
        return white % MOD

print( (dfs(0, 1) + dfs(1,1)) % MOD)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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 = [[0 for _ in range(2)] for _ in range(n)]
#0が白, 1が黒

def dfs(cur, par):
	dp[cur] = [1, 1]
	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])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

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

if N==1:
    print(2)
    exit()

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
dp = [[1,1] for i in range(N)]

def rec(i,parent):
    for to in es[i]:
        if to==parent: continue
        rec(to,i)
        dp[i][0] *= (dp[to][0] + dp[to][1])
        dp[i][1] *= dp[to][0]
    dp[i][0] %= MOD
    dp[i][1] %= MOD

rec(0,-1)
print(sum(dp[0]))

Submission status: Wrong Answer

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

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

if N==1:
    print(2)
    exit()

es = [[] for i in range(N)]
for a,b in src:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

MOD = 10**9+7
dp = [[1,1] for i in range(N)]

def rec(i,parent):
    for to in es[i]:
        if to==parent: continue
        rec(to,i)
        dp[i][0] *= (dp[to][0] + dp[to][1])
        dp[i][0] %= MOD
        dp[i][1] *= dp[to][0]
        dp[i][1] %= MOD

rec(0,-1)
print(sum(dp[0]))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
from collections import deque

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
        dpBlack[v2] *= dpW
        degs[v2] -= 1
        if degs[v2] == 1:
            Q.append(v2)
    degs[vNow] = 0

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