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:
#!/usr/bin/env python3

from collections import defaultdict
#from heapq import heappush, heappop
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
INF = 10 ** 9 + 1  # sys.maxsize # float("inf")
MOD = 10 ** 9 + 7


def debug(*x):
    print(*x, file=sys.stderr)


def solve(N, edges):
    def visit(parent, self):
        if parent != 0 and len(edges[self]) == 1:
            # self is leaf
            return (1, 2)  # white, total

        black = 1
        white = 1
        for child in edges[self]:
            if child == parent:
                continue
            w, t = visit(self, child)
            black *= w
            black %= MOD
            white *= t
            white %= MOD
        ret = (white, white + black)
        return ret

    return visit(0, 1)[1] % MOD


def main():
    # parse input
    N = int(input())
    edges = defaultdict(list)
    for i in range(N - 1):
        x, y = map(int, input().split())
        edges[x].append(y)
        edges[y].append(x)
    print(solve(N, edges))


# tests
T1 = """
3
1 2
2 3
"""


def test_T1():
    """
    >>> as_input(T1)
    >>> main()
    5
    """


T2 = """
4
1 2
1 3
1 4
"""


def test_T2():
    """
    >>> as_input(T2)
    >>> main()
    9
    """


T3 = """
1
"""


def test_T3():
    """
    >>> as_input(T3)
    >>> main()
    2
    """


T4 = """
10
8 5
10 8
6 5
1 5
4 8
2 10
3 6
9 2
1 7
"""


def test_T4():
    """
    >>> as_input(T4)
    >>> main()
    157
    """
# add tests above


def _test():
    import doctest
    doctest.testmod()


def as_input(s):
    "use in test, use given string as input file"
    import io
    global read, input
    f = io.StringIO(s.strip())

    def input():
        return bytes(f.readline(), "ascii")

    def read():
        return bytes(f.read(), "ascii")


USE_NUMBA = False
if (USE_NUMBA and sys.argv[-1] == 'ONLINE_JUDGE') or sys.argv[-1] == '-c':
    print("compiling")
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', solve.__doc__.strip().split()[0])(solve)
    cc.compile()
    exit()
else:
    input = sys.stdin.buffer.readline
    read = sys.stdin.buffer.read

    if (USE_NUMBA and sys.argv[-1] != '-p') or sys.argv[-1] == "--numba":
        # -p: pure python mode
        # if not -p, import compiled module
        from my_module import solve  # pylint: disable=all
    elif sys.argv[-1] == "-t":
        print("testing")
        _test()
        sys.exit()
    elif sys.argv[-1] != '-p' and len(sys.argv) == 2:
        # input given as file
        input_as_file = open(sys.argv[1])
        input = input_as_file.buffer.readline
        read = input_as_file.buffer.read

    main()

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, islice
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7

N = INT()
xy = [LIST() for _ in range(N-1)]
tree = [[] for _ in range(N)]
for x, y in xy:
    tree[x-1].append(y-1)
    tree[y-1].append(x-1)

def DFS(i, par, c):  # c:0->white, 1->black
    if par and len(tree[i]) == 1:
        return 1
    if c == 0:
        cnt = 1
        for node in tree[i]:
            if node != par:
                cnt *= (DFS(node, i, 0) + DFS(node, i, 1))
                cnt %= mod
        return cnt
    elif c == 1:
        cnt = 1
        for node in tree[i]:
            if node != par:
                cnt *= DFS(node, i, 0)
                cnt %= mod
        return cnt

ans = DFS(0, None, 0)+DFS(0, None, 1)
print(ans%mod)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  x, y = map(int, input().split())
  x -= 1
  y -= 1
  T[x].append(y)
  T[y].append(x)
dp = [[-1]*n for _ in range(2)]
def dfs(color, i, par=-1):
  if dp[color][i] != -1:
    return dp[color][i]
  res = 1
  if color == 0:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i) + dfs(1, v, i)
      res %= MOD
  else:
    for v in T[i]:
      if v == par:
        continue
      res *= dfs(0, v, i)
      res %= MOD
  dp[color][i] = res
  return res
ans = dfs(0, 0) + dfs(1, 0)
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

        if color == BLACK:
            child_rec = lambda x: rec(x, WHITE, node)
        else:
            child_rec = lambda x: rec(x, WHITE, node) + rec(x, BLACK, node)
        
        temp = 1
        for child in edge[node]:
            if child == parent:
                continue
            temp *= child_rec(child)
            temp %= MODP
            
        dp[node][color] = temp
        return dp[node][color]
    
    rec(1, WHITE, 0)
    rec(1, BLACK, 0)
    print((dp[1][WHITE] + dp[1][BLACK]) % MODP)


submit()

Submission status: Time Limit Exceeded

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

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

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

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

        temp = 1
        for child in edge[node]:
            if child == parent:
                continue
            if color == BLACK:
                temp *= rec(child, WHITE, node)
            else:
                temp *= (rec(child, WHITE, node) + rec(child, BLACK, node))
            temp %= MODP
            
        dp[node][color] = temp
        return dp[node][color]
    
    rec(1, WHITE, 0)
    rec(1, BLACK, 0)
    print((dp[1][WHITE] + dp[1][BLACK]) % MODP)


submit()

Submission status: Time Limit Exceeded

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

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

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

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

        temp = 1
        if color == BLACK: # 黒
            for child in edge[node]:
                if child == parent:
                    continue
                temp *= rec(child, WHITE, node)
                temp %= MODP
        else:
            for child in edge[node]:
                if child == parent:
                    continue
                temp *= (rec(child, BLACK, node) + rec(child, WHITE, node))
                temp %= MODP
        
        dp[node][color] = temp
        return dp[node][color]
    
    rec(1, WHITE, 0)
    rec(1, BLACK, 0)
    print((dp[1][WHITE] + dp[1][BLACK]) % MODP)


submit()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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
    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=int(input())
v=[[] for _ in range(n)]
for x,y in [map(int,input().split()) for _ in range(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in range(n)]
print((f(0,-1,0)+f(0,-1,1))%mod)

Submission status: Time Limit Exceeded

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
    for y in v[x]:
      if y!=p:
      	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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
from functools import lru_cache
MOD = 10 ** 9 + 7

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

@lru_cache(maxsize = None)
def dfs(v,color,p = -1):
    if color == 0:
        ans = 1
        for e in G[v]:
            if e == p:
                continue
            ans *= dfs(e,0,v) + dfs(e,1,v)
            ans %= MOD
        return ans
    else:
        ans = 1
        for e in G[v]:
            if e == p:
                continue
            ans *= dfs(e,0,v)
            ans %= MOD
        return ans

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

Submission status: Time Limit Exceeded

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

import queue

P=10**9+7
N=int(input())
G=[[] for index1 in range(N+1)]
for index3 in range(N-1):
    x,y=map(int,input().split())
    G[x].append(y)
    G[y].append(x)


DP=[]
DP_sum=[0]*(N+1)
for index4 in range(N+1):
    DP.append([-1,-1])  #白、黒
q=queue.Queue()
q.put(1)
DP_sum[1]=2

def dfs(v,pv=0):
    if DP[v]!=[-1,-1]:#不要
        return DP[v]
    else:
        nvs=G[v]
        if pv in nvs:#無駄
            nvs.remove(pv)
        if not nvs:
            DP[v]=[1,1]
            DP_sum[v]=DP[v][0]+DP[v][1]
            return DP[v]
        else:
            v_white=1
            v_black=1
            for nv in nvs:
                nvxy=dfs(nv,v)
                v_white*=(nvxy[0]+nvxy[1])
                v_black*=nvxy[0]
                v_white%=P
                v_black%=P
            DP[v]=[v_white,v_black]
            DP_sum[v]=(DP[v][0]+DP[v][1])%P
            return DP[v]

dfs(1)
print(DP_sum[1])

Submission status: Time Limit Exceeded

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
    b,w=1,1
    for nv in G[v]:
        if(nv==p):
            continue
        bw=dfs(nv,v)
        w*=sum(bw);w%=MOD
        b*=bw[1];b%=MOD
    dp[v]=(b,w)
    return (b,w)
    
N=int(input())
G,dp,seen=[],[],[]
for i in range(N):
    G.append([]);dp.append([0,0]);seen.append(0)
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))%MOD)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edge = [[] for _ 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)

import sys
sys.setrecursionlimit(10**8)

mod = 10**9+7
def dfs(v):
    white,black = 1,1
    for u in edge[v]:
        if visited[u]==False:
            visited[u]=True
            w,b = dfs(u)
            white *= w+b
            white %= mod
            black *= w
            black %= mod
    return white,black

visited = [False]*N
visited[0]=True
print(sum(dfs(0))%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

input=sys.stdin.readline

sys.setrecursionlimit(100000)

N=int(input())
edge={i:[] for i in range(1,N+1)}
for i in range(0,N-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[b].append(a)
mod=10**9+7

parent={i:0 for i in range(1,N+1)}

q=set([1])
sub=set([])
while q:
    while q:
        x=q.pop()
        for p in edge[x]:
            if p!=1 and parent[p]==0:
                parent[p]=x
                sub.add(p)

        if not q:
            q=sub
            sub=set([])
            break


def dfs(num):
    if len(edge[num])==1 and num!=1:
        return (1,1)

    WHITE=1
    BLACK=1
    for i in edge[num]:
        if i!=parent[num]:
            s,t=dfs(i)
            WHITE=(WHITE*(s+t))%mod
            BLACK=(BLACK*s)%mod

    return (WHITE,BLACK)

w,b=dfs(1)
print((w+b)%mod)

Submission status: Time Limit Exceeded

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

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

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)

parent = {0}

def dp(node):
    black_output = white_output = 1
    for child in neighbor[node]:
        if child in parent:
            continue
        else:
            parent.add(child)
            tmp_black, tmp_white = dp(child)
            black_output *= tmp_white
            white_output *= tmp_black + tmp_white
    black_output %= MOD
    white_output %= MOD
    return black_output, white_output

print(sum(dp(0)) % MOD)

Submission status: Time Limit Exceeded

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

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

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
    output %= MOD
    memo[node][color] = output
    return output

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

Submission status: Time Limit Exceeded

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

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

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)

def dp(node, color, parent):
    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)
                tmp %= MOD
            output *= tmp
            output %= MOD
    return output

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

Submission status: Time Limit Exceeded

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

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

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)
                tmp %= MOD
            output *= tmp
            output %= MOD
    memo[node][color] = output
    return output

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

Submission status: Time Limit Exceeded

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

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

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
            output %= MOD
    memo[node][color] = output
    return output

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
def main():
  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])%MOD)
if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

def dfs(node, parent=-1):
    if dp[node][0] != -1 and dp[node][1] != -1:
        return
    ans = 0
    is_leaf = True
    white, black = 1, 1

    for edge in edges[node]:
        if edge != parent:
            is_leaf = False
            if dp[edge][0] == -1 or dp[edge][1] == -1:
                dfs(edge, node)
            white *= (dp[edge][0] + dp[edge][1])
            black *= dp[edge][0]

    dp[node][0] = white % mod
    dp[node][1] = black % mod

    if is_leaf:
        dp[node][0] = 1
        dp[node][1] = 1


N = int(input())
edges = {i:[] for i 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 j in range(2)] for i in range(N)]
dfs(0)
print((dp[0][0] + dp[0][1]) % mod)

Submission status: Time Limit Exceeded

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


def dfs(node, parent=-1):
    if dp[node][0] != -1 and dp[node][1] != -1:
        return
    ans = 0
    is_leaf = True
    white, black = 1, 1

    for edge in edges[node]:
        if edge != parent:
            is_leaf = False
            if dp[edge][0] == -1 or dp[edge][1] == -1:
                dfs(edge, node)
            white *= (dp[edge][0] + dp[edge][1])
            black *= dp[edge][0]
            white %= mod
            black %= mod

    dp[node][0] = white
    dp[node][1] = black

    if is_leaf:
        dp[node][0] = 1
        dp[node][1] = 1


N = int(input())
edges = {i:[] for i 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 j in range(2)] for i in range(N)]
dfs(0)
print((dp[0][0] + dp[0][1]) % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7


def dfs(node, parent=-1):
    if dp[node][0] != -1 and dp[node][1] != -1:
        return
    ans = 0
    is_leaf = True
    white, black = 1, 1

    for edge in edges[node]:
        if edge != parent:
            is_leaf = False
            if dp[edge][0] == -1 or dp[edge][1] == -1:
                dfs(edge, node)
            white *= (dp[edge][0] + dp[edge][1])
            black *= dp[edge][0]
            white %= mod
            black %= mod

    dp[node][0] = white
    dp[node][1] = black

    if is_leaf:
        dp[node][0] = 1
        dp[node][1] = 1


N = int(input())
edges = {i:[] for i 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 j in range(2)] for i in range(N)]
dfs(0)
print((dp[0][0] + dp[0][1]) % mod)

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

fact = [0] * (N + 10)
t = 1
for i in range(1, N + 1):
    t *= i
    t %= MOD
    fact[i] = t

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


@lru_cache(maxsize=None)
def dfs(x, parent, isBlack=True):
    ret = 1
    for v in PATH[x]:
        if v == parent:
            continue

        cnt = dfs(v, x, False)

        if not isBlack:
            cnt += dfs(v, x, True)

        ret *= cnt
        ret %= MOD

    ret %= MOD

    return ret


ans = dfs(1, -1, True) + dfs(1, -1, False)
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

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


def dfs(x, parent, isBlack=True):
    ret = 1
    for v in PATH[x]:
        if v == parent:
            continue

        cnt = dfs(v, x, False)

        if not isBlack:
            cnt += dfs(v, x, True)

        ret *= cnt
        ret %= MOD

    ret %= MOD

    return ret


ans = dfs(1, -1, True) + dfs(1, -1, False)
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
PATH = [[] for _ in range(N + 1)]
MOD = 10 ** 9 + 7

fact = [0] * (N + 10)
t = 1
for i in range(1, N + 1):
    t *= i
    t %= MOD
    fact[i] = t

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


def dfs(x, parent, isBlack=True):
    ret = 1
    for v in PATH[x]:
        if v == parent:
            continue

        cnt = dfs(v, x, False)

        if not isBlack:
            cnt += dfs(v, x, True)

        ret *= cnt
        ret %= MOD

    ret %= MOD

    return ret


ans = dfs(1, -1, True) + dfs(1, -1, False)
ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)

def dfs(v, pv, c):
    if memo[v][c]!=-1:
        return memo[v][c]
        
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if c==0:
            res *= dfs(nv, v, 0)+dfs(nv, v, 1)
        else:
            res *= dfs(nv, v, 0)
        
        res %= MOD
    
    memo[v][c] = res
    
    return res

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)

memo = [[-1]*2 for _ in range(N)]
MOD = 10**9+7

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