Problem p03181 (python)

Fixed submission:
n,m = map(int,input().split())
mod = m
# mod = 10**9+7

# 前準備
import sys
input = sys.stdin.readline
from collections import deque

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

ini = 1

def calc(a,b):
    p = a * b % mod
    return p

# calc1 の定義
def calc1(c,p):
    p_num = ini
    for i in graph[c]:
        if i == p:
            continue
        p_num = calc(p_num, dp1[i])
    p_num += 1
    dp1[c] = p_num % mod

# calc2 の定義
def calc2(p):
    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [ini]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [ini]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        prod.append(calc(a,b))

    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            dp2[c] = (x + 1)%mod



# 根から探索して親と探索順を記録
root = 1
order = []
parent = [0] * (n+1)
stack = deque()
stack.append(root)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        stack.append(y)
        parent[y] = x

# 親→子の値を算出
dp1 = [None] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])

# 子→親の値を算出　累積和チックにすることでうに対策。
dp2 = [None] * (n+1)
dp2[root] = ini
for i in order:
    calc2(i)

for i in range(1,n+1):
    ans = calc(dp1[i]-1, dp2[i])
    print(ans)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)

n,m = map(int,input().split())

neighbor = {}
for i in range(1,n+1):
    neighbor[i] = []

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

dp = [{} for _ in range(n+1)]
dp_prod = [{'list':{}} for _ in range(n+1)]
prod_make_check = [0] * (n+1)
for i in range(1,n+1):
    prod_make_check[i] = -1 * len(neighbor[i])
    for idx, j in enumerate(neighbor[i]):
        dp_prod[i]['list'][j] = idx
        dp[i][j] = -1

def calc(x,y):
    if(dp[x][y] != -1):
        return(dp[x][y])

    if(len(neighbor[y]) == 1):
        dp[x][y] = 2 % m
        prod_make_check[x] += 1
        if(prod_make_check[x] == 0):
            calc_prod(x)
        return(dp[x][y])

    if(prod_make_check[y] == 0):
        idx = dp_prod[y]['list'][x]
        dp[x][y] = (1 + dp_prod[y]['left'][idx] * dp_prod[y]['right'][idx+1])  % m
        prod_make_check[x] += 1
        if(prod_make_check[x] == 0):
            calc_prod(x)
        return(dp[x][y])

    temp = 1
    for i in neighbor[y]:
        if(i == x):
            continue
        temp = temp * calc(y, i) % m
    temp = (temp+1) % m
    dp[x][y] = temp
    prod_make_check[x] += 1
    if(prod_make_check[x] == 0):
        calc_prod(x)
    return(dp[x][y])


def calc_prod(y):
    left = 1
    right = 1
    len_ = len(neighbor[y]) + 1
    dp_prod[y]['left'] = [1] * len_
    dp_prod[y]['right'] = [1] * len_
    for idx, z in enumerate(neighbor[y]):
        left = left * dp[y][z] % m
        dp_prod[y]['left'][idx+1] = left

    for idx, z in enumerate(neighbor[y][::-1]):
        right = right * dp[y][z] % m
        dp_prod[y]['right'][len_ - 2 -idx] = right

for i in range(1,n+1):
    for j in neighbor[i]:
        calc(i,j)

for i in range(1,n+1):
    print(dp_prod[i]['right'][0])