Problem p03181 (python)

Fixed submission:
from collections import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n, m = MI()
to = defaultdict(list)
# dp[u][v] uを根としたときのサブツリーvの値
dp = {}

def dfs(u=0, pu=-1):
    res = 1
    for v in to[u]:
        if v == pu: continue
        res *= dfs(v, u) + 1
        res %= m
    if pu != -1: dp[(pu,u)] = res
    return res

def main():
    for _ in range(n - 1):
        x, y = map(int1, input().split())
        to[x].append(y)
        to[y].append(x)
    dfs()
    # bfsでdfsとは逆向きのdpを完成させる
    que = deque()
    que.append([0, -1])
    while que:
        u, pu = que.popleft()
        tn = len(to[u])
        # 累積積のための配列
        ll = [0] * tn
        rr = [0] * tn
        # uのサブツリーの値+1を入れる
        for i, v in enumerate(to[u]):
            ll[i] = rr[i] = dp[(u,v)] + 1
        # 左右から累積積を作る
        for i in range(1, tn):
            ll[i] = (ll[i - 1] * ll[i]) % m
            rr[tn - 1 - i] = (rr[tn - i] * rr[tn - 1 - i]) % m
        # 配列の最初or最後のために最後に1を追加
        ll += [1]
        rr += [1]
        # uの子vを根とみたときのサブツリーuの値を求める
        for i, v in enumerate(to[u]):
            if v == pu: continue
            dp[(v,u)] = (ll[i - 1] * rr[i + 1]) % m
            que.append([v, u])
    # p2D(dp)
    # 各頂点について答えを出す
    for u in range(n):
        ans = 1
        for v in to[u]:
            ans = (ans * (dp[(u,v)] + 1)) % m
        print(ans)

main()

Buggy submission (verdict: Runtime Error):
import sys

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


def cnt1(i, oya_i=0):
    if len(pair[i]) == 1 and oya_i:
        memo[i][oya_i] = 1
        return 1

    if memo[i][oya_i] != -1:
        return memo[i][oya_i]

    re = 1
    for ko_i in pair[i]:
        if ko_i == oya_i: continue
        re *= (cnt1(ko_i, i) + 1)
    memo[i][oya_i] = re = re % m
    return re


def cnt2(i, ko_i=0, cnt_ko=-1):
    if cnt_ko != -1:
        memo[ko_i][i] = cnt_ko

    oyas = pair[i]
    oya_n = len(oyas)
    ruisekiL = [1] * (oya_n)
    ruisekiR = [1] * (oya_n)
    for k in range(1, oya_n):
        ruisekiL[k] = ruisekiL[k - 1] * (memo[oyas[k - 1]][i] + 1) % m
        ruisekiR[-k - 1] = ruisekiR[-k] * (memo[oyas[-k]][i] + 1) % m

    ans[i] = ruisekiL[-1] * (memo[oyas[-1]][i] + 1) % m

    for k, oya_i in enumerate(oyas):
        if oya_i == ko_i: continue
        cnt2(oya_i, i, ruisekiL[k] * ruisekiR[k] % m)


n, m = map(int, input().split())
memo = [[-1] * (n + 1) for _ in range(n + 1)]
pair = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    pair[x] += [y]
    pair[y] += [x]
ans = [0] * (n + 1)

cnt1(1)
cnt2(1)

print(*ans[1:], sep="\n")

Buggy submission (verdict: Runtime Error):
import sys

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


def cnt1(i, oya_i=0):
    if len(pair[i]) == 1 and oya_i:
        memo[i][oya_i] = 1
        return 1

    if memo[i][oya_i] != 0:
        return memo[i][oya_i]

    re = 1
    for ko_i in pair[i]:
        if ko_i == oya_i: continue
        re *= (cnt1(ko_i, i) + 1)
    memo[i][oya_i] = re = re % m
    return re


def cnt2(i, ko_i=0, cnt_ko=-1):
    if cnt_ko != -1:
        memo[ko_i][i] = cnt_ko

    oya_n = len(pair[i])
    ruisekiL = [1] * (oya_n)
    ruisekiR = [1] * (oya_n)
    for k in range(1, oya_n):
        ruisekiL[k] = ruisekiL[k - 1] * (memo[pair[i][k - 1]][i] + 1) % m
        ruisekiR[-k - 1] = ruisekiR[-k] * (memo[pair[i][-k]][i] + 1) % m

    ans[i] = ruisekiL[-1] * (memo[pair[i][-1]][i] + 1) % m

    for k, oya_i in enumerate(pair[i]):
        if oya_i == ko_i: continue
        cnt2(oya_i, i, ruisekiL[k] * ruisekiR[k] % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
pair = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    pair[x] += [y]
    pair[y] += [x]
ans = [0] * (n + 1)

cnt1(1)
cnt2(1)

print(*ans[1:],sep="\n")

Buggy submission (verdict: Runtime Error):
import sys

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


def cnt1(i, oya_i=0):
    if len(pair[i]) == 1 and oya_i:
        memo[i][oya_i] = 1
        return 1

    if memo[i][oya_i] != 0:
        return memo[i][oya_i]

    re = 1
    for ko_i in pair[i]:
        if ko_i == oya_i: continue
        re *= (cnt1(ko_i, i) + 1)
    memo[i][oya_i] = re = re % m
    return re


def cnt2(i, ko_i=0, cnt_ko=-1):
    if cnt_ko != -1:
        memo[ko_i][i] = cnt_ko

    oya_n = len(pair[i])
    ruisekiL = [1] * (oya_n)
    ruisekiR = [1] * (oya_n)
    for k in range(1, oya_n):
        ruisekiL[k] = ruisekiL[k - 1] * (memo[pair[i][k - 1]][i] + 1) % m
        ruisekiR[-k - 1] = ruisekiR[-k] * (memo[pair[i][-k]][i] + 1) % m

    ans[i] = ruisekiL[-1] * (memo[pair[i][-1]][i] + 1) % m

    for k, oya_i in enumerate(pair[i]):
        if oya_i == ko_i: continue
        cnt2(oya_i, i, ruisekiL[k] * ruisekiR[k] % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
pair = [[] for _ in range(n + 1)]
for _ in range(n - 1):
    x, y = map(int, input().split())
    pair[x] += [y]
    pair[y] += [x]
ans = [0] * (n + 1)

cnt1(1)
cnt2(1)

print(*ans[1:],sep="\n")

Buggy submission (verdict: Runtime Error):
import sys

input = sys.stdin.readline


def cnt(i, oya_i):
    if len(ko[i]) == 1 and oya_i:
        return 1
    if memo[i][oya_i] != 0:
        return memo[i][oya_i]
    re = 1
    for ko_i in ko[i]:
        if ko_i == oya_i: continue
        re *= (cnt(ko_i, i) + 1)
    memo[i][oya_i] = re
    return re


def f(n, m):
    for _ in range(n - 1):
        x, y = map(int, input().split())
        ko[x] += [y]
        ko[y] += [x]
    for start_i in range(1, n + 1):
        print(cnt(start_i, 0) % m)


n, m = map(int, input().split())
memo = [[0] * (n + 1) for _ in range(n + 1)]
ko = [[] for _ in range(n + 1)]
f(n, m)