Problem p02728 (python)

Fixed submission:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import resource
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return (a * b) % self.m

    def div(self, a, b):
        return self.mul(a, self.pow(b, self.m-2))

    @lru_cache(maxsize=None)
    def pow(self, a, b):
        return pow(a, b, self.m)


M = Mod(10**9 + 7)
m = 10**9 + 7
fact = [1] * (2 * (10**5) + 1)
fact_inv = [0] * (2 * (10**5) + 1)
for i in range(1, 2 * (10**5)+1):
    fact[i] = M.mul(fact[i-1], i)
    fact_inv[i] = pow(fact[i], m-2, m)


@mt
def slv(N, AB):
    g = defaultdict(list)
    for a, b in AB:
        g[a].append(b)
        g[b].append(a)

    memo = defaultdict(dict)

    def f(u, p, flag=False):
        if u in memo and p in memo[u]:
            return memo[u][p]
        r = 1
        n = 1
        if p == 0 or flag:
            for v in g[u]:
                if v == p:
                    continue
                n_, r_ = f(v, u, flag)
                n += n_
                r = M.mul(r, r_)
                r = M.mul(r, fact_inv[n_])
            r = M.mul(r, fact[n-1])
        else:
            np, rp = f(p, u, False)
            na, ra = f(u, 0, False)
            r = M.div(ra, rp)
            r = M.mul(r, fact[np])
            n = na - np
            r = M.mul(r, fact_inv[na-1])
            r = M.mul(r, fact[n-1])

        memo[u][p] = n, r
        return n, r

    f(1, 0, True)

    for i in range(1, N+1):
        print(f(i, 0, False)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    slv(N, AB)

    # N = (10**5) * 2
    # AB = [(_, _+1) for _ in range(N-1)]
    # (slv(N, AB))


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-


from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    # def __dfs1(self, u, p):
    #     o = []
    #     s = [(u, -1)]
    #     while s:
    #         u, p = s.pop()
    #         o.append((u, p))
    #         for v in self.tree[u]:
    #             if v == p:
    #                 continue
    #             s.append((v, u))

    #     for u, p in reversed(o):
    #         r = self.ie
    #         for v in self.tree[u]:
    #             if v == p:
    #                 continue
    #             # ep(u_, v, self.dp)
    #             r = self.merge(r, self.f(self.dp[u][v], v))

    #         self.dp[p][u] = self.g(r, u)
    #         print(p, u, self.dp[p][u])

    # def __dfs2(self, u, p, a):
    #     s = [(u, p, a)]

    #     while s:
    #         u, p, a = s.pop()

    #         self.dp[u][p] = a

    #         pl = [0] * (len(self.tree[u]) + 1)
    #         pl[0] = self.ie
    #         for i, v in enumerate(self.tree[u]):
    #             pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

    #         pr = [0] * (len(self.tree[u]) + 1)
    #         pr[-1] = self.ie
    #         for i, v in reversed(list(enumerate(self.tree[u]))):
    #             pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

    #         for i, v in enumerate(self.tree[u]):
    #             if v == p:
    #                 continue
    #             r = self.merge(pl[i], pr[i+1])
    #             s.append((v, u, self.g(r, v)))

    def __dfs1(self, u, p):
        r = self.ie
        for v in self.tree[u]:
            if v == p:
                continue
            self.dp[u][v] = self.__dfs1(v, u)
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)

    def __dfs2(self, u, p, a):
        for v in self.tree[u]:
            if v == p:
                self.dp[u][v] = a
                break
        pl = [0] * (len(self.tree[u]) + 1)
        pl[0] = self.ie
        for i, v in enumerate(self.tree[u]):
            pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

        pr = [0] * (len(self.tree[u]) + 1)
        pr[-1] = self.ie
        for i, v in reversed(list(enumerate(self.tree[u]))):
            pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

        for i, v in enumerate(self.tree[u]):
            if v == p:
                continue
            r = self.merge(pl[i], pr[i+1])
            self.__dfs2(v, u, self.g(r, v))

    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)


def atcoder_dp_dp_v():
    # https://atcoder.jp/contests/dp/tasks/dp_v
    # https://atcoder.jp/contests/dp/submissions/16664670
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u))


def atcoder_abc60_f():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    M = 10**9+7

    from functools import reduce

    fact = [1]
    for i in range(1, 10**6):
        fact.append(fact[-1]*i % M)

    def f(x, _):
        c = x[0]
        s = x[1]
        c *= pow(fact[s], M-2, M)
        c %= M
        return (c, s)

    def g(x, _):
        c = x[0]
        s = x[1]
        c *= fact[s]
        c %= M
        return (c, s+1)

    def merge(x, y):
        return (x[0]*y[0]%M, x[1]+y[1])

    rr = ReRooting(f, g, merge, (1, 0))
    for a, b in AB:
        rr.add_edge(a, b)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)[0])




if __name__ == '__main__':
    # atcoder_dp_dp_v()
    atcoder_abc60_f()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys, resource
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

resource.setrlimit(resource.RLIMIT_STACK,
                   (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


M = Mod(10**9 + 7)

fact_ = [1] * (2 * (10**5) + 1)
for i in range(1, 2 * (10**5)+1):
    fact_[i] = M.mul(fact_[i-1], i)


def fact(n):
    return fact_[n]




@mt
def slv(N, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    @lru_cache(maxsize=None)
    def f(u, p):
        n = 0
        r = 1
        nn = []
        for v in g[u]:
            if v == p:
                continue
            n_, r_ = f(v, u)
            r = M.mul(r, r_)
            n += n_
            nn.append(n_)

        ret = M.mul(fact(n), r)
        for i in nn:
            ret = M.div(ret, fact(i))

        return n+1, ret

    for i in range(1, N+1):
        print(f(i, 0)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))

    # N = (10**5) * 2
    # AB = [(_, _+1) for _ in range(N-1)]
    # (slv(N, AB))



if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys, resource
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

resource.setrlimit(resource.RLIMIT_STACK,
                   (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

M = 10**9 + 7
@lru_cache(maxsize=None)
def fact(n):
    ret = 1
    for i in range(1, n+1):
        ret *= i
        ret %= M
    return ret

@mt
def slv(N, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    @lru_cache(maxsize=None)
    def f(u, p):
        n = 0
        r = 1
        nn = []
        for v in g[u]:
            if v == p:
                continue
            n_, r_ = f(v, u)
            r *= r_
            r %= M
            n += n_
            nn.append(n_)

        ret = fact(n) * r
        ret %= M
        for i in nn:
            ret //= fact(i)
        return n+1, ret

    for i in range(1, N+1):
        print(f(i, 0)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))



if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys, resource
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

# resource.setrlimit(resource.RLIMIT_STACK,
#                    (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

M = 10**9 + 7
@lru_cache(maxsize=None)
def fact(n):
    ret = 1
    for i in range(1, n+1):
        ret *= i
        ret %= M
    return ret

@mt
def slv(N, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    @lru_cache(maxsize=None)
    def f(u, p):
        n = 0
        r = 1
        nn = []
        for v in g[u]:
            if v == p:
                continue
            n_, r_ = f(v, u)
            r *= r_
            r %= M
            n += n_
            nn.append(n_)

        ret = fact(n) * r
        ret %= M
        for i in nn:
            ret //= fact(i)
        return n+1, ret

    for i in range(1, N+1):
        print(f(i, 0)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))



if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

M = 10**9 + 7
@lru_cache(maxsize=None)
def fact(n):
    ret = 1
    for i in range(1, n+1):
        ret *= i
        ret %= M
    return ret

@mt
def slv(N, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    @lru_cache(maxsize=None)
    def f(u, p):
        n = 0
        r = 1
        nn = []
        for v in g[u]:
            if v == p:
                continue
            n_, r_ = f(v, u)
            r *= r_
            r %= M
            n += n_
            nn.append(n_)

        ret = fact(n) * r
        ret %= M
        for i in nn:
            ret //= fact(i)
        return n+1, ret

    for i in range(1, N+1):
        print(f(i, -1)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()