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: Time Limit Exceeded

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])%MOD)
resolve()

Submission status: Time Limit Exceeded

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)
  
  def dfs(v,s):
    b = 1
    w = 1
    for u in E[v]:
      if u != s:
        b0,w0 = dfs(u,v)
        b *= w0
        w *= (b0+w0)
    #b %= MOD
    #w %= MOD
    return b,w

  b,w = dfs(0,-1)
  print((b+w) % MOD)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

def dfs(n,p):
    w = 1
    b = 1
    for i in to[n]:
        if i != p:
            rw, rb = dfs(i, n)
            w *= (rw + rb)
            w %= MOD
            b *= rw
            b %= MOD
    return (w,b)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

visited = [False] * N
def dfs(n):
    visited[n] = True
    w = 1
    b = 1
    for i in to[n]:
        if visited[i] == False:
            rw, rb = dfs(i)
            w *= (rw + rb) % MOD
            b *= rw % MOD
    return (w,b)

ans = dfs(0)
print((ans[0] + ans[1]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

visited = [False] * N
def dfs(n):
    visited[n] = True
    w = 1
    b = 1
    for i in to[n]:
        if visited[i] == False:
            rw, rb = dfs(i)
            w *= rw + rb
            b *= rw
    w %= MOD
    b %= MOD
    return (w,b)

ans = dfs(0)
print((ans[0] + ans[1]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

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

visited = [False] * N
def dfs(n):
    visited[n] = True
    w = 1
    b = 1
    for i in to[n]:
        if visited[i] == False:
            rw, rb = dfs(i)
            w *= rw + rb
            b *= rw
    w %= MOD
    b %= MOD
    return (w,b)

ans = dfs(0)
print((ans[0] + ans[1]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

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

root = {i for i in range(N)}

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

visited = [False] * N
def dfs(n):
    visited[n] = True
    w = 1
    b = 1
    for i in to[n]:
        if visited[i] == False:
            rw, rb = dfs(i)
            w *= rw + rb
            b *= rw
    w %= MOD
    b %= MOD
    return [w,b]

ans = dfs(0)
print((ans[0] + ans[1]) % MOD)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#EDPC P

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        w,b = dp[u]
        dp[v][0] *= (w+b)
        dp[v][0] %= mod
        dp[v][1] *= w
        dp[v][1] %= mod

f(0)
ans = (dp[0][0] + dp[0][1]) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#EDPC P

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        dp[v][0] *= (dp[u][0]+dp[u][1])
        dp[v][0] %= mod
        dp[v][1] *= dp[u][0]
        dp[v][1] %= mod

f(0)
ans = (dp[0][0] + dp[0][1]) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
#EDPC P

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()
graph = [[] for _ in range(n)]
for _ in range(n-1):
    x,y = LI()
    graph[x-1].append(y-1)
    graph[y-1].append(x-1)

dp = [[1,1] for _ in range(n)]
flg = [0]*n
def f(v):
    flg[v] = 1
    for u in graph[v]:
        if flg[u]:
            continue
        f(u)
        dp[v][0] = dp[v][0]*(dp[u][0]+dp[u][1])
        dp[v][0] %= mod
        dp[v][1] = dp[v][1]*dp[u][0]
        dp[v][1] %= mod

f(0)
ans = (dp[0][0] + dp[0][1]) % mod
print(ans)

Submission status: Time Limit Exceeded

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)

Submission status: Time Limit Exceeded

Solution code:
from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    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[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)
                g[x] *= fy
        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))%mod)
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Time Limit Exceeded

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)
                if f[x] >= mod:
                    f[x] %= mod
                g[x] *= fy
                if g[x] >= mod:
                    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))%mod)
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Time Limit Exceeded

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

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

def rec(cur, prev=None):
    white = 1
    black = 1
    for to in edges[cur]:
        if to == prev:
            continue
        w,b = rec(to, cur)
        white *= (w+b)
        white %= mod
        black *= w
        black %= mod
    return white, black

w, b = rec(0)
print((w+b)%mod)

Submission status: Time Limit Exceeded

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

memo = [[-1]*2 for i in range(n)]
def rec(cur, prev=None):
    white = 1
    black = 1
    for to in edges[cur]:
        if to == prev:
            continue
        w,b = rec(to, cur)
        white *= (w+b)
        white %= mod
        black *= w
        black %= mod
    return white, black

w, b = rec(0)
print((w+b)%mod)

Submission status: Time Limit Exceeded

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

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

solver.solve()

Submission status: Time Limit Exceeded

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

BLK = 1
WHT = 0
MOD = 10 ** 9 + 7


def calcdp(r, p, bw):
    if dp[r][bw] != -1:
        return dp[r][bw]

    if p == 0:
        cs = H[r]
    else:
        cs = H[r] - {p}

    if len(cs) == 0:
        dp[r][bw] = 1
        return 1
    else:
        if bw == BLK:
            res = 1
            for c in cs:
                res = (res * calcdp(c, r, WHT)) % MOD
            dp[r][BLK] = res
            return res
        else:
            res = 1
            for c in cs:
                res = (res * (calcdp(c, r, WHT) + calcdp(c, r, BLK))) % MOD
            dp[r][WHT] = res

            return res


N = int(input())
H = [set() for _ in range(N + 1)]
for _ in range(1, N):
    x, y = map(int, input().split())
    H[x].add(y)
    H[y].add(x)

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

print((calcdp(1, 0, BLK) + calcdp(1, 0, WHT)) % MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(1000000)
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[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]


dfs(0,-1)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(1000000000)
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[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]


dfs(0,-1)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(1000000)
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[to][0] + dp[to][1])%MOD
            dp[c][1] *= (dp[to][0])%MOD

dfs(0,-1)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(1000000)
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[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]

dfs(0,-1)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(10000000)
MOD = 10**9+7
E = {}
for i in range(0,N):
    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[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]
            dp[c][0] %= MOD
            dp[c][1] %= MOD

dfs(0,-1)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(1000000)
MOD = 10**9+7
E = {}
for i in range(0,N):
    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[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]
            dp[c][0] %= MOD
            dp[c][1] %= MOD

dfs(0,-1)

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
import sys
sys.setrecursionlimit(1000000)
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(1000100)]

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[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]
            dp[c][0] %= MOD
            dp[c][1] %= MOD

dfs(0,-1)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(500000)

n = int(input())
mod = 10 ** 9 + 7
node = [[] for _ in range(n)]
memo_f, memo_g = [0] * n, [0] * 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):
    if memo_f[x]:
        return memo_f[x]
    memo_f[x] = 1
    for i in node[x]:
        if i == prev:
            continue
        memo_f[x] = (memo_f[x] * g(i, x)) % mod
    memo_f[x] = (memo_f[x] + g(x, prev)) % mod
    return memo_f[x]

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

print(f(0, -1))

Submission status: Time Limit Exceeded

Solution code:
import sys

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


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


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

Submission status: Time Limit Exceeded

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


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


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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


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


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