Buggy python submission (verdict: Time Limit Exceeded):


import sys
sys.setrecursionlimit(1000000)

def dfs1(u, pu):
    dp[u] = 1
    for v in tree[u]:
        if v != pu:
            dfs1(v, u)
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

def dfs2(u, pu, pval):
    resp[u] = (dp[u] * pval) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval
    for i in range(len(chlds)):
        v = chlds[i]
        vval = (1 + pref * cumulr[i]) % MOD

        dfs2(v, u, vval)

        pref *= (dp[v] + 1)
        pref %= MOD


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)

dp = [0] * n
resp = [0] * n
dfs1(0, -1)
dfs2(0, -1, 1)
for i in range(n):
    print(resp[i])


Fixed submission:


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)


cola = [(0, -1)]
qind = 0
while qind < len(cola):
    u, pu = cola[qind]
    qind += 1
    for v in tree[u]:
        if v != pu:
            cola.append((v, u))

dp = [1] * n
for i in range(n - 1, -1, -1):
    u, pu = cola[i]
    for v in tree[u]:
        if v != pu:
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

resp = [0] * n
pval = [1] * n
for j in range(n):
    u, pu = cola[j]
    resp[u] = (dp[u] * pval[u]) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval[u]
    for i in range(len(chlds)):
        v = chlds[i]
        pval[v] = (1 + pref * cumulr[i]) % MOD
        pref *= (dp[v] + 1)
        pref %= MOD

for i in range(n):
    print(resp[i])

Buggy python submission (verdict: Runtime Error):


def dfs1(u, pu):
    dp[u] = 1
    for v in tree[u]:
        if v != pu:
            dfs1(v, u)
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

def dfs2(u, pu, pval):
    resp[u] = (dp[u] * pval) % MOD
    
    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval
    for i in range(len(chlds)):
        v = chlds[i]
        vval = (1 + pref * cumulr[i]) % MOD

        dfs2(v, u, vval)

        pref *= (dp[v] + 1)
        pref %= MOD


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)

dp = [0] * n
resp = [0] * n
dfs1(0, -1)
dfs2(0, -1, 1)
for i in range(n):
    print(resp[i])


Fixed submission:


n, MOD = map(int, raw_input().split())
tree = [[] for _ in range(n)]
for _ in range(n - 1):
    u, v = map(lambda u: int(u) - 1, raw_input().split())
    tree[u].append(v)
    tree[v].append(u)


cola = [(0, -1)]
qind = 0
while qind < len(cola):
    u, pu = cola[qind]
    qind += 1
    for v in tree[u]:
        if v != pu:
            cola.append((v, u))

dp = [1] * n
for i in range(n - 1, -1, -1):
    u, pu = cola[i]
    for v in tree[u]:
        if v != pu:
            dp[u] *= (dp[v] + 1)
            dp[u] %= MOD

resp = [0] * n
pval = [1] * n
for j in range(n):
    u, pu = cola[j]
    resp[u] = (dp[u] * pval[u]) % MOD

    chlds = [v for v in tree[u] if v != pu]
    cumulr = [1] * len(chlds)
    for i in range(len(chlds) - 2, -1, -1):
        cumulr[i] = cumulr[i + 1] * (1 + dp[chlds[i + 1]]) % MOD

    pref = pval[u]
    for i in range(len(chlds)):
        v = chlds[i]
        pval[v] = (1 + pref * cumulr[i]) % MOD
        pref *= (dp[v] + 1)
        pref %= MOD

for i in range(n):
    print(resp[i])