Problem p03181 (python)

Fixed submission:
import sys
 
sys.setrecursionlimit(100000)
 
 
def dfs1(v, p):
    val = 1
    pre_mul = [1]
    rev_mul = []
    for c in links[v]:
        if c == p:
            pre_mul.append(val)
            rev_mul.append(1)
            continue
        res = 1 + dfs1(c, v)
        val *= res
        val %= m
        pre_mul.append(val)
        rev_mul.append(res)
    dp[v] = val
    for i in range(len(rev_mul) - 2, -1, -1):
        rev_mul[i] *= rev_mul[i + 1]
        rev_mul[i] %= m
    rev_mul.append(1)
    pre_muls[v] = [pre_mul, rev_mul]
    return val
 
 
def dfs2(v, p, a):
    dp[v] = dp[v] * a % m
    pmv = pre_muls[v]
    for i, c in enumerate(links[v]):
        if c == p:
            continue
        pmc = pmv[0][i] * pmv[1][i + 1] % m
        pmc = pmc * a % m
        dfs2(c, v, pmc + 1)
 
 
n, m = map(int, input().split())
links = [[] for _ in range(n)]
dp = [0 for _ in range(n)]
pre_muls = [None for _ in range(n)]
for line in sys.stdin.readlines():
    x, y = map(int, line.split())
    x -= 1
    y -= 1
    links[x].append(y)
    links[y].append(x)
dfs1(0, None)
dfs2(0, None, 1)
print('\n'.join(map(str, dp)))

Buggy submission (verdict: Runtime Error):
import sys 
sys.setrecursionlimit(1000000) 

N, M = map(int, input().split())
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)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]*(nn+1)
    pb = [1]*(nn+1)
    for i in range(nn):
        u1 = G[v][i]
        u2 = G[v][-i-1]
        pf[i+1] = pf[i]*(dp[(v, u1)]+1)
        pb[i+1] = pb[i]*(dp[(v, u2)]+1)
        pf[i+1] %= M
        pb[i+1] %= M
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import sys 
sys.setrecursionlimit(1000000) 

N, M = map(int, input().split())
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)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]
    for u in G[v]:
        pf.append(pf[-1]*(dp[(v, u)]+1)%M)
    pb = [1]
    for u in G[v][::-1]:
        pb.append(pb[-1]*(dp[(v, u)]+1)%M)
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import sys 
sys.setrecursionlimit(1000000) 

N, M = map(int, input().split())
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)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]
    for u in G[v]:
        pf.append(pf[-1]*(dp[(v, u)]+1)%M)
    pb = [1]
    for u in G[v][::-1]:
        pb.append(pb[-1]*(dp[(v, u)]+1)%M)
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)
print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
import sys 
sys.setrecursionlimit(100000) 
import queue

N, M = map(int, input().split())
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)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]
    for u in G[v]:
        pf.append(pf[-1]*(dp[(v, u)]+1)%M)
    pb = [1]
    for u in G[v][::-1]:
        pb.append(pb[-1]*(dp[(v, u)]+1)%M)
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)

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

Buggy submission (verdict: Runtime Error):
import sys 
sys.setrecursionlimit(100000) 
import queue

N, M = map(int, input().split())
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)


dp = {}
def tdc(p, v):
    if G[v] == [p]:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in G[v]:
        if u == p: continue
        res *= (1+tdc(v, u)) 
        res %= M
    dp[(p, v)] = res
    return dp[(p, v)]

r = 1       
tdc(-1, r)

ans = [0]*N
ans[r] = dp[(-1, r)]

def buc(p, v):
    if G[v] == [p]: return 0
    nn = len(G[v])
    pf = [1]
    for u in G[v]:
        pf.append(pf[-1]*(dp[(v, u)]+1)%M)
    pb = [1]
    for u in G[v][::-1]:
        pb.append(pb[-1]*(dp[(v, u)]+1)%M)
    for i in range(nn):
        u = G[v][i]
        if u == p: continue
        dp[(u, v)] = pf[i] * pb[::-1][i+1] 
        dp[(u, v)] %= M
        ans[u] = dp[(v, u)]*(1+dp[(u, v)]) 
        ans[u] %= M
        buc(v, u)

buc(-1, r)

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

Buggy submission (verdict: Runtime Error):
import sys 
sys.setrecursionlimit(100000) 
import queue

N, M = map(int, input().split())
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)


dp = {}
def rec(p, v):
    C = set(G[v]) - set([p])
    if len(C) == 0:
        dp[(p, v)] = 1
        return 1
    res = 1
    for u in C:
        res *= (1+rec(v, u))
    dp[(p, v)] = res
    return dp[(p, v)]

r = 0       
rec(-1, r)

q = queue.Queue()
q.put(r)
ans = [0]*N
ans[r] = dp[(-1, r)]

while not q.empty():
    p = q.get()
    for v in G[p]:
        if ans[v] > 0: continue
        ans[v] = int(dp[(p, v)]*(ans[p]/(1+dp[(p, v)])+1)) % M
        q.put(v)

for a in ans:
    print(a)

Buggy submission (verdict: Runtime Error):
import queue
N, M = map(int, input().split())
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)


dp = [0]*N
def rec(p, v):
    C = set(G[v]) - set([p])
    if len(C) == 0:
        dp[v] = 1
        return 1
    res = 1
    for u in C:
        res *= (1+rec(v, u)) % M
    dp[v] = res % M
    return dp[v]

root = 0       
rec(None, root)

q = queue.Queue()
q.put(root)
ans = [0]*N
ans[root] = dp[root] % M

while not q.empty():
    p = q.get()
    for v in G[p]:
        if ans[v] > 0: continue
        ans[v] = int(dp[v]*(ans[p]/(1+dp[v])+1)) % M
        q.put(v)

for a in ans:
    print(a)