Problem p03181 (python)

Fixed submission:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [tuple(map(int, l.split())) for l in sys.stdin]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    if n == 1:
        return 1
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b = LI_()
        e[a].append(b)
        e[b].append(a)

    w = [None] * n

    d = [None] * n
    def f(i,p):
        r = 1
        s = [1]
        t = []
        for c in e[i]:
            if c == p:
                s.append(r)
                t.append(1)
                continue
            u = f(c,i) + 1
            r *= u
            r %= m
            s.append(r)
            t.append(u)
        for j in range(len(t)-2, -1, -1):
            t[j] *= t[j+1]
            t[j] %= m
        t.append(1)
        d[i] = [s, t]
        w[i] = r
        return r

    def g(i,p,k):
        w[i] *= k
        w[i] %= m
        s,t = d[i]
        for j,c in enumerate(e[i]):
            if c == p:
                continue
            g(c,i,(s[j] * t[j+1] * k) % m + 1)

    f(0, -1)
    g(0, -1, 1)
    return '\n'.join(map(str, w))


print(main())

Buggy submission (verdict: Runtime Error):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m = LI()
    if n == 1:
        return 1
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b = LI_()
        e[a].append(b)
        e[b].append(a)

    rr = [None] * n
    tt = [None] * n

    fm = {}
    def f(i,p,pp):
        if not p is None:
            k = (i,p)
            if k in fm:
                return fm[k]
            if not tt[i] is None:
                return tt[i][p]
            r = 1
            for c in e[i]:
                if c != p:
                    r *= f(c,i,-1) + 1
                    r %= m
            fm[k] = r
            return r

        ta = []
        for c in e[i]:
            ta.append(f(c,i,-1) + 1)
        l = len(e[i])
        if l == 1:
            tt[i] = [1]
            rr[i] = ta[0] % m
            if pp is None:
                f(e[i][0],None,i)
            return 0

        aa = [0] * l
        aa[0] = ta[0]
        for j in range(1,l):
            aa[j] = aa[j-1] * ta[j] % m

        ba = [0] * l
        ba[-1] = ta[-1]
        for j in range(l-2,-1,-1):
            ba[j] = ba[j+1] * ta[j] % m

        ei = e[i]
        ca = {}
        ca[ei[0]] = ba[1]
        for ej,j in zip(ei[1:-1],range(l-2)):
            ca[ej] = aa[j] * ba[j+2] % m
        ca[ei[-1]] = aa[-2]
        tt[i] = ca
        rr[i] = ba[0] % m
        for c in e[i]:
            if c != pp:
                f(c,None,i)
        return 0

    f(0,None,None)

    return '\n'.join(map(str, rr))



print(main())