Problem p03181 (python)

Fixed submission:
import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N)]
for row in sys.stdin.readlines():
    x,y = map(int,row.split())
    graph[x-1].add(y-1)
    graph[y-1].add(x-1)

ldp = [None] * N
rdp = [None] * N

def dfs_1(v=0,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    graph[v].discard(parent)
    ldp[v] = [1] * (len(graph[v])+1)
    rdp[v] = [1] * (len(graph[v])+1)
    vals = [dfs_1(w,v)+1 for w in graph[v]]
    for i,x in enumerate(vals,1):
        ldp[v][i] = ldp[v][i-1] * x % MOD
    for i,x in enumerate(reversed(vals),1):
        rdp[v][-i-1] = rdp[v][-i] * x % MOD
    return ldp[v][-1]

dfs_1()

dp = [None] * N
q = [(0,1)]
while q:
    v,x = q.pop()
    dp[v] = x*ldp[v][-1]%MOD
    for w,L,R in zip(graph[v],ldp[v][:-1],rdp[v][1:]):
        q.append((w,x*L*R%MOD+1))

print('\n'.join(map(str,dp)))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import itertools

N,MOD = map(int,readline().split())
m = map(int,read().split())
XY = zip(m,m)

mult = lambda x,y: x*y%MOD

graph = [[] for _ in range(N+1)]
for x,y in XY:
    graph[x].append(y)
    graph[y].append(x)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

# 自身を黒く塗ったときの根側
dp1 = [0]*(N+1)

for v in order[::-1]:
    x = 1
    for w in graph[v]:
        x *= dp1[w]+1
        x %= MOD
    dp1[v] = x

# 親側
dp2 = [1]*(N+1)

for v in order:
    p = parent[v]
    arr = [dp1[c]+1 if c != p else dp2[v] for c in graph[v]]
    # 1元を除く積を取得
    from_left = [1] + list(itertools.accumulate(arr,mult))[:-1]
    from_right = list(itertools.accumulate(reversed(arr),mult))[-2::-1] + [1]
    prod = [x*y%MOD for x,y in zip(from_left,from_right)]
    for c,x in zip(graph[v],prod):
        if c != p:
            dp2[c] = 1+x

answer = '\n'.join(str(x*y%MOD) for x,y in zip(dp1[1:],dp2[1:]))
print(answer)

Buggy submission (verdict: Runtime Error):
import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

dp_1 = [None] * (N+1)
products = [[] for _ in range(N+1)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    if graph[v]:
        arr = [dfs_1(w,v)+1 for w in graph[v]]
        L = list(itertools.accumulate(arr[:-1], lambda x,y: x*y%MOD))
        R = list(itertools.accumulate(arr[1:][::-1], lambda x,y: x*y%MOD))[::-1]
        products[v] = [x*y%MOD for x,y in zip(L,R)]
        dp_1[v] = products[v][0] * arr[0] % MOD
    else:
        dp_1[v] = 1
    return dp_1[v]

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

Buggy submission (verdict: Runtime Error):
import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

dp_1 = [None] * (N+1)
products = [[] for _ in range(N+1)]

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    if graph[v]:
        arr = [dfs_1(w,v)+1 for w in graph[v]]
        L = [1] + list(itertools.accumulate(arr[:-1], lambda x,y: x*y%MOD))
        R = list(itertools.accumulate(arr[1:][::-1], lambda x,y: x*y%MOD))[::-1] + [1]
        products[v] = [x*y%MOD for x,y in zip(L,R)]
        dp_1[v] = products[v][0] * arr[0] % MOD
    else:
        dp_1[v] = 1
    return dp_1[v]

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

dp_1

products

def dfs_2(v=1,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    dp[v] = x * dp_1[v] % MOD
    for w,p in zip(graph[v],products[v]):
        dfs_2(w,x*p%MOD+1)

dp = [None] * (N+1)
dfs_2()

print('\n'.join(map(str,dp[1:])))

Buggy submission (verdict: Runtime Error):
import itertools
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,MOD = map(int,input().split())
if N == 1:
    print(1)
    exit()
graph = [set() for _ in range(N+1)]
for _ in range(N-1):
    x,y = map(int,input().split())
    graph[x].add(y)
    graph[y].add(x)

def dfs_1(v=1,parent=None):
    # 子ごとに、そこを黒くして適切 or 完全白
    # dp_1 + 1 の積
    x = 1
    graph[v].discard(parent)
    for w in graph[v]:
        x *= (dfs_1(w,v) + 1)
    dp_1[v] = x
    return x

dp_1 = [0] * (N+1) # 自分を黒く塗って、子側の部分木を適切に塗る方法
dfs_1()

def dfs_2(v=1,parent=None,x=1):
    # それぞれの子以外の情報をマージして、子に渡さなければいけない
    arr = [1 + dp_1[w] for w in graph[v]] + [x]
    L = [1] + list(itertools.accumulate(arr[:-1], lambda x,y: x*y%MOD))
    R = list(itertools.accumulate(arr[::-1][:-1], lambda x,y: x*y%MOD))[::-1] + [1]
    products = [x*y%MOD for x,y in zip(L,R)]
    dp[v] = arr[0] * products[0] % MOD
    for w,p in zip(graph[v],products):
        if w==parent:
            continue
        dfs_2(w,v,p+1)

dp = [0] * (N+1)
dfs_2()

print('\n'.join(map(str,dp[1:])))