Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i.
For each k=1, ..., N, solve the problem below:

Consider writing a number on each vertex in the tree in the following manner:

First, write 1 on Vertex k.

Then, for each of the numbers 2, ..., N in this order, write the number on the vertex chosen as follows:

Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.

Find the number of ways in which we can write the numbers on the vertices, modulo (10^9+7).

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq a_i,b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

For each k=1, 2, ..., N in this order, print a line containing the answer to the problem.

Sample Input 1

3
1 2
1 3

Sample Output 1

2
1
1

The graph in this input is as follows:

For k=1, there are two ways in which we can write the numbers on the vertices, as follows:

Writing 1, 2, 3 on Vertex 1, 2, 3, respectively

Writing 1, 3, 2 on Vertex 1, 2, 3, respectively

Sample Input 2

2
1 2

Sample Output 2

1
1

The graph in this input is as follows:

Sample Input 3

5
1 2
2 3
3 4
3 5

Sample Output 3

2
8
12
3
3

The graph in this input is as follows:

Sample Input 4

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8

Sample Output 4

40
280
840
120
120
504
72
72

The graph in this input is as follows:



Sample input:
3
1 2
1 3


Sample output:
2
1
1

Submission status: Runtime Error

Solution code:
from collections import deque
MOD = 1000000007

N =  int(input())
childs = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    childs[a].append(b)
    childs[b].append(a)

dp = [0] * (N + 1) # represent the # if i is the root (1)
tree_size = [0]*(N + 1)
ans = [0] * (N + 1)

n_inv = [1, 1]
n_j_mod = [1, 1]

for i in range(2, N+1):
    n_inv.append((pow(i, MOD-2, MOD) * n_inv[-1]) % MOD)
    n_j_mod.append((n_j_mod[-1] * i) % MOD)


def dfs(i, father=-1):
    method_num = 1
    t_size = 1
    for child in childs[i]:
        if child != father:
            num, size = dfs(child, i)
            method_num = (method_num * num * n_inv[size]) % MOD
            t_size += size
    method_num = (method_num * n_j_mod[t_size - 1]) % MOD
    dp[i] = method_num
    tree_size[i] = t_size
    return method_num, t_size

def rdfs(i, f_num, father=-1):
    ans[i] = (dp[i] * f_num * n_j_mod[N-1] * n_inv[N - tree_size[i]] * n_inv[tree_size[i] - 1]) % MOD

    for child in childs[i]:
        if child != father:
            cf_num = (ans[i] * n_j_mod[tree_size[child]] * n_j_mod[N - tree_size[child] - 1] * n_inv[N - 1] * pow(dp[child], MOD-2, MOD)) % MOD
            rdfs(child, cf_num, i)
dfs(1)

rdfs(1, 1)
print('\n'.join(list(map(str, ans[1:]))))

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline
    sys.setrecursionlimit(1000000)

    n = int(input())

    E = [[] for i in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)

    mod = 10 ** 9 + 7
    N = n + 1

    #逆元テーブル
    inv_t = [0]+[1]
    for i in range(2, N):
        inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

    #階乗計算
    kai = [1, 1]
    rev_kai = [1, inv_t[1]]
    for i in range(2, N):
        kai.append(kai[-1] * i % mod)
        rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

    # コンビネーション計算
    def cmb(n, r):
        return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

    down = [{} for i in range(n+1)]
    up = [0 for i in range(n+1)]

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]

    def dfs_up(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ns = []
                cnt = 1
                ns_append = ns.append
                if up[pre]:
                    ni, cnti = up[pre]
                    ns_append(ni)
                    cnt = cnt * cnti % mod
                bros = down[pre]
                for bro in bros:
                    if bro != cur:
                        ni, cnti = bros[bro]
                        ns_append(ni)
                        cnt = cnt * cnti % mod
                s = sum(ns)
                S = s
                for ni in ns:
                    cnt = cnt * cmb(s, ni) % mod
                    s -= ni
                up[cur] = [S+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])


    dfs_down(0, n)
    dfs_up(0, n)


    for i in range(n):
        ns = []
        cnt = 1
        if up[i]:
            ni, cnti = up[i]
            ns_append = ns.append
            ns_append(ni)
            cnt = cnt * cnti % mod
        for bro in down[i]:
            ni, cnti = down[i][bro]
            ns_append(ni)
            cnt = cnt * cnti % mod
        s = sum(ns)
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline
    sys.setrecursionlimit(1000000)

    mod = 10 ** 9 + 7
    N = 200001

    #逆元テーブル
    inv_t = [0]+[1]
    for i in range(2, N):
        inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

    #階乗計算
    kai = [1, 1]
    rev_kai = [1, inv_t[1]]
    for i in range(2, N):
        kai.append(kai[-1] * i % mod)
        rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

    # コンビネーション計算
    def cmb(n, r):
        return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

    n = int(input())

    E = [[] for i in range(n)]
    for i in range(n-1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)

    down = [{} for i in range(n+1)]
    up = [0 for i in range(n+1)]

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]

    def dfs_up(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ns = []
                cnt = 1
                ns_append = ns.append
                if up[pre]:
                    ni, cnti = up[pre]
                    ns_append(ni)
                    cnt = cnt * cnti % mod
                bros = down[pre]
                for bro in bros:
                    if bro != cur:
                        ni, cnti = bros[bro]
                        ns_append(ni)
                        cnt = cnt * cnti % mod
                s = sum(ns)
                S = s
                for ni in ns:
                    cnt = cnt * cmb(s, ni) % mod
                    s -= ni
                up[cur] = [S+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])


    dfs_down(0, n)
    dfs_up(0, n)


    for i in range(n):
        ns = []
        cnt = 1
        if up[i]:
            ni, cnti = up[i]
            ns_append = ns.append
            ns_append(ni)
            cnt = cnt * cnti % mod
        for bro in down[i]:
            ni, cnti = down[i][bro]
            ns_append(ni)
            cnt = cnt * cnti % mod
        s = sum(ns)
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
lim = N+10  # 必要そうな階乗の限界を入れる
fact = [1] * (lim+1)
fact_inv = [1] * (lim+1)
for n in range(1, lim+1):
    fact[n] = (fact[n-1] * n) % mod
fact_inv[lim] = pow(fact[lim], mod-2, mod)
for n in range(lim, 0, -1):
    fact_inv[n-1] = (n * fact_inv[n]) % mod

tree = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
	a, b = MAP()
	tree[a].append(b)
	tree[b].append(a)

order = []
parent = [0]*(N+1)
stack = [1]
while stack:
    n = stack.pop()
    order.append(n)
    for node in tree[n]:
        if node == parent[n]:
            continue
        stack.append(node)
        parent[node] = n

size = [1]*(N+1)
for v in order[::-1]:
    size[parent[v]] += size[v]

dpLeaf = [1] * (N+1)
for v in order[::-1]:
    pr = parent[v]
    dpLeaf[v] = dpLeaf[v]*fact[size[v]-1]%mod
    dpLeaf[pr] = dpLeaf[pr]*dpLeaf[v]*fact_inv[size[v]]%mod

ans = [0]*(N+1)
ans[1] = dpLeaf[1]
for v in order[1:]:
    pr = parent[v]
    ans[v] = (ans[pr]*pow(N-size[v], mod-2, mod)*size[v])%mod
print(*ans[1:], sep="\n")

Submission status: Runtime Error

Solution code:
def main():
    #import random

    # def sample_tree(n):  # n頂点の連結グラフを出力する
    #    l = [random.randrange(0, i+1) for i in range(n-1)]  # 親を指定する
    #    d = {i: j for i, j in enumerate(random.sample(range(n), n))}  # シャッフル
    #    xy = sorted([sorted([d[j]+1, d[i+1]+1])
    #                 for i, j in enumerate(l)])  # グラフを作成
    #    return xy
    #n = 200000
    # print(n)
    #ab = sample_tree(n)

    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 2*10**5+1):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t) % mod, self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                i = visited[p]-1
                dp[p][i] = dpSum[v].addRoot()
                dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs():
        q = [(0, DP(), -1)]
        while q:
            v, dpP, p = q.pop()
            deg = len(g[v])
            for i in range(deg):
                if g[v][i] == p:
                    dp[v][i] = dpP
            dpLeft = [DP() for _ in range(deg+1)]
            dpRight = [DP() for _ in range(deg+1)]
            for i in range(deg):
                dpLeft[i+1] = dpLeft[i]+dp[v][i]
            for i in range(deg-1, -1, -1):
                dpRight[i] = dpRight[i+1]+dp[v][i]
            ans[v] = dpLeft[deg].addRoot()
            for i in range(deg):
                u = g[v][i]
                if u == p:
                    continue
                d = dpLeft[i]+dpRight[i+1]
                q.append((u, d.addRoot(), v))

    dfs()
    bfs()
    for i in range(n):
        print(ans[i].dp)
    # for i in range(n):
    #    print([j.dp for j in dp[i]])


main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t) % mod, self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                i = visited[p]-1
                dp[p][i] = dpSum[v].addRoot()
                dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs():
        q = [(0, DP(), -1)]
        while q:
            v, dpP, p = q.pop()
            deg = len(g[v])
            for i in range(deg):
                if g[v][i] == p:
                    dp[v][i] = dpP
            dpLeft = [DP() for _ in range(deg+1)]
            dpRight = [DP() for _ in range(deg+1)]
            for i in range(deg):
                dpLeft[i+1] = dpLeft[i]+dp[v][i]
            for i in range(deg-1, -1, -1):
                dpRight[i] = dpRight[i+1]+dp[v][i]
            ans[v] = dpLeft[deg].addRoot()
            for i in range(deg):
                u = g[v][i]
                if u == p:
                    continue
                d = dpLeft[i]+dpRight[i+1]
                q.append((u, d.addRoot(), v))

    dfs()
    bfs()
    for i in range(n):
        print(ans[i].dp)
    # for i in range(n):
    #    print([j.dp for j in dp[i]])


main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    sys.setrecursionlimit(300000)
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t), self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[] for _ in [0]*n]
    ans = [0]*n

    def dfs(v, p=-1):
        dpSum = DP()
        dp[v] = [DP() for _ in [0]*len(g[v])]
        for i in range(len(g[v])):
            u = g[v][i]
            if u == p:
                continue
            dp[v][i] = dfs(u, v)
            dpSum = dpSum+dp[v][i]
        return dpSum.addRoot()

    def bfs(v, dpP=DP(), p=-1):
        deg = len(g[v])
        for i in range(deg):
            if g[v][i] == p:
                dp[v][i] = dpP
        dpLeft = [DP() for _ in range(deg+1)]
        dpRight = [DP() for _ in range(deg+1)]
        for i in range(deg):
            dpLeft[i+1] = dpLeft[i]+dp[v][i]
        for i in range(deg-1, -1, -1):
            dpRight[i] = dpRight[i+1]+dp[v][i]
        ans[v] = dpLeft[deg].addRoot()
        for i in range(deg):
            u = g[v][i]
            if u == p:
                continue
            d = dpLeft[i]+dpRight[i+1]
            bfs(u, d.addRoot(), v)

    dfs(0)
    bfs(0)
    for i in range(n):
        print(ans[i].dp)


main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t), self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                i = visited[p]-1
                dp[p][i] = dpSum[v].addRoot()
                dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs():
        q = [(0, DP(), -1)]
        while q:
            v, dpP, p = q.pop()
            deg = len(g[v])
            for i in range(deg):
                if g[v][i] == p:
                    dp[v][i] = dpP
            dpLeft = [DP() for _ in range(deg+1)]
            dpRight = [DP() for _ in range(deg+1)]
            for i in range(deg):
                dpLeft[i+1] = dpLeft[i]+dp[v][i]
            for i in range(deg-1, -1, -1):
                dpRight[i] = dpRight[i+1]+dp[v][i]
            ans[v] = dpLeft[deg].addRoot()
            for i in range(deg):
                u = g[v][i]
                if u == p:
                    continue
                d = dpLeft[i]+dpRight[i+1]
                q.append((u, d.addRoot(), v))

    dfs()
    bfs()
    for i in range(n):
        print(ans[i].dp)


main()

Submission status: Runtime Error

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 10**5):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t), self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                i = visited[p]-1
                dp[p][i] = dpSum[v].addRoot()
                dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs(v, dpP=DP(), p=-1):
        deg = len(g[v])
        for i in range(deg):
            if g[v][i] == p:
                dp[v][i] = dpP
        dpLeft = [DP() for _ in range(deg+1)]
        dpRight = [DP() for _ in range(deg+1)]
        for i in range(deg):
            dpLeft[i+1] = dpLeft[i]+dp[v][i]
        for i in range(deg-1, -1, -1):
            dpRight[i] = dpRight[i+1]+dp[v][i]
        ans[v] = dpLeft[deg].addRoot()
        for i in range(deg):
            u = g[v][i]
            if u == p:
                continue
            d = dpLeft[i]+dpRight[i+1]
            bfs(u, d.addRoot(), v)

    dfs()
    bfs(0)
    for i in range(n):
        print(ans[i].dp)


main()

Submission status: Runtime Error

Solution code:
import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------

mod = 1000000007
N=int(2*1e5+100)
sz = [0]*N
dp = [0]*N
gr = defaultdict(list)
def modPow(a,b):
    ans=1
    while (b):
        if (b&1): ans=(ans*a)%mod
        b>>=1
        a=(a*a)%mod
    return ans

def modInv(x):
    return modPow(x,mod-2)

def dfs(x, par):
    sz[x]=1
    for item in gr[x]:
        if item==par: continue
        dfs(item,x)
        sz[x]+=sz[item]

def dfs1(x, par):
    for item in gr[x]:
        if item==par: continue
        dp[item]=(dp[x]*(n-sz[item]))%mod
        dp[item]=(dp[item]*modInv(sz[item]))%mod
        dfs1(item,x)

n = int(input())
for i in range(n-1):
    x,y = mapi()
    gr[x].append(y)
    gr[y].append(x)
dfs(1,0)
dp[1]=1
for i in range(1,n+1):
    dp[1]=(dp[1]*sz[i])%mod
dfs1(1,0)
res = 1
for i in range(1,n+1):
    res = (res*i)%mod
for i in range(1,n+1):
    dp[i]=(res*modInv(dp[i]))%mod
for i in range(1,n+1):
    print(dp[i])

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.buffer.readline

# modなしの場合は，mod=1にする

class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

    def factInvN(self, n):
        if n < 0:
            return 0
        return self.factInv[n]

N = int(input())
MOD = 10**9 + 7
comb = Combination(10**5 + 100)

edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    fr, to = map(int, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

order = []
parent = [0] * (N + 1)
st = [1]
while st:
    now = st.pop()
    order.append(now)
    for to in edges[now]:
        if to == parent[now]:
            continue
        st.append(to)
        parent[to] = now

size = [1] * (N + 1)
for v in order[::-1]:
    size[parent[v]] += size[v]

dpLeaf = [1] * (N + 1)
for v in order[:: -1]:
    pr = parent[v]
    dpLeaf[v] = dpLeaf[v] * comb.factN(size[v] - 1) % MOD
    dpLeaf[pr] = dpLeaf[pr] * dpLeaf[v] * comb.factInvN(size[v]) % MOD

ans = [0] * (N + 1)
ans[1] = dpLeaf[1]
for v in order[1:]:
    pr = parent[v]

    x = ans[pr]
    x *= comb.factN(N - 1 - size[v]) * comb.factInvN(N - size[v])
    x *= size[v]
    ans[v] = x % MOD

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

Submission status: Runtime Error

Solution code:

Submission status: Runtime Error

Solution code:
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res

    return 

dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[x] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
    return
dfs2(0,-1)
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res
dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[nex] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
dfs2(0,-1)
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

n = int(input())
e = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int,input().split())
    e[a-1].append(b-1)
    e[b-1].append(a-1)

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res
dfs(0,-1)
print(numl)
print(resl)
ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[nex] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
dfs2(0,-1)
for i in ans:
    print(i)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import resource
sys.setrecursionlimit(2 * 10**5)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))


MOD = 1000000007  # type: int

def solve(N: int, a: "List[int]", b: "List[int]"):
    ff = [1] * (N + 1)
    for i in range(1, N+1):
        ff[i] = (ff[i-1] * i) % MOD
    iff = [pow(ff[i], MOD-2, MOD) for i in range(N+1)]
    cache = {}
    def f(source, sink):
        key = (source, sink)
        if key in cache:
            return cache[key]
        c, ic, p = 0,1, 1
        for e in edges[sink]:
            if e == source:
                continue
            cc, pp = f(sink, e)
            p = (p * pp) % MOD
            c += cc
            ic = (ic * iff[cc]) % MOD
        cache[key] = c+1, p * (ff[c] * ic) % MOD
        return cache[key]

    def g(node):
        c, ic, p = 0, 1, 1
        for e in edges[node]:
            cc, pp = f(node, e)
            c += cc
            p = (p * pp) % MOD
            ic = (ic * iff[cc]) 
        return (((ff[c] * ic) % MOD) * p) % MOD
    
    edges = [[] for _ in range(N+1)]
    for aa, bb in zip(a, b):
        edges[aa].append(bb)
        edges[bb].append(aa)

    for i in range(1, N+1):
        print(g(i))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()