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:
import sys
def input(): return sys.stdin.readline().strip()


"""
ABC160-Fの解説放送での実装をPythonで焼きなおしてみました。
内訳：
    class Combination : mod付きの組み合わせの計算用クラス
    class DP : 木DPを行うためのクラス（本問用に特殊化）
    dfs(v, p=-1) : 頂点v以下の部分木に対してdpした結果を返す
    bfs(v, p=-1) : 頂点vに入ってくるdp値の総和を取り、頂点vの子供に親からのdp値を渡す
"""

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

# 早速グローバル変数として用意しておく
cmb = Combination(2 * 10 ** 5)


class DP:
    """
    木DPをする準備として、dpの値と木のサイズを両方保持するクラスを定義する。
    さらに演算子オーバーロードにより足し算記号でdpの値の更新（今回は組み合わせ含む掛け算）と
    木のサイズの合算を同時にやってくれるようにする。
    """
    def __init__(self, m_dp=1, m_t=0):
        self.dp = m_dp
        self.t = m_t
    
    def __iadd__(self, other):
        """
        a = DP(3, 2); b = DP(4, 5)として
        a += bによりa = DP(12, 7)みたいになる。
        二つの木を合わせるために新しくつける根はまだ足していないことに注意。
        """
        self.dp *= other.dp * cmb(self.t + other.t, self.t)
        self.t += other.t
        return self
    
    def __sub__(self, other):
        """
        引き算も同様にオーバーロード（ただしこっちは二項演算）。
        また、こちらはbfsで親の木のdp値を送ることを念頭においていることに注意。
        """
        dp = self.dp / (other.dp * cmb(self.t - 1, other.t))
        t = self.t - other.t
        return DP(dp, t)
    
    def addRoot(self):
        self.t += 1
        return self
    
    def subroot(self):
        self.t -= 1
        return self



def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    mod = 10 ** 9 + 7

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

    """
    まずは頂点0を根として木DPをする、すなわち頂点0に数字1を書き込んだ場合の
    残りの数の書き込み方の場合の数を計算する。
    """

    # 最初の木DPの途中経過を記録する配列を準備
    # dp[v][i] = (頂点vのi番目の子を根とする部分木から頂点vに渡されるdp値)
    dp = [[DP() for u in repn[v]] for v in range(N)]
    # dpSum[v] = (頂点vの子供を根とする部分木からそれぞれ頂点vに渡されるdp値の総和)
    dpSum = [DP() for _ in range(N)]

    def dfs(v, p=-1):
        """
        dfsというよりは木DPをした結果を返す関数。

        根がvの部分木（頂点pはvの親として含めない）のdp結果を返すが、
        そのためにvの各子供に対する部分木dpの結果を足し合わせて、
        最後に木のサイズを1(v自身の分)だけ増やしている。

        v自身が葉ノードの場合はDPクラス内で既に初期化が済んでいることに注意。
        """
        for i, u in enumerate(repn[v]):
            if u == p:
                continue
            dp[v][i] = dfs(u, v)
            dpSum[v] += dp[v][i]
        return dpSum[v].addRoot()

    dfs(0)
    # この時点で各dpSum[v]には、子供らのdp値を総和した値と、頂点vを含む木のサイズが記録される
    # for i in range(N):
    #     print("dpSum[{}]=[{}, {}]".format(i, dpSum[i].dp, dpSum[i].t))

    """
    次に全方位木DPのためのbfsを行う。
    全方位木そのもののアルゴリズムは解説放送を参照。
    あえてポイントを述べるとすれば、
        1. 木の各辺の向きが、部分木と１対１対応する。
        2. dfs時点で各辺の根に上がる向きの部分木dpは記録済み
        3. 逆向きの辺のdp値は、全ての隣接辺に対して入ってくる向きの
        　　dp値がわかっている頂点（例えば根）に関してならdp値の総和を
        　　考えることで出ていく向きのdp値がO(1)で求まる。
        4. これを隣接する頂点ごとに計算すればよい。
    """

    def bfs(v, dpP=DP(), p=-1):
        """
        頂点vからのbfsというかdfsで求めたdp値の逆伝搬（出ていく方のdp値）の計算を行う。
        dpPは頂点vの親から来る部分木のdp値。

        まず親から来る部分木のdp値を加えることで、頂点vに隣接する全ての辺から入ってくる
        dp値の総和を完成させる。
        
        このときdpSum[v]自体が頂点vを含んでしまうとdp計算で木のサイズを使う際に狂いが生じるので、
        一旦頂点vを除いたうえでdpPを加えて、その後頂点vを戻す（これで頂点vに対する解は求まった）。
        """
        
        if p != -1:
            dpSum[v].subroot()
            dpSum[v] += dpP
            dpSum[v].addRoot()

        # 次に頂点vのそれぞれの子（頂点u）に対して、頂点uを主役と見たときの親からのdp値を渡す。、
        for i, u in enumerate(repn[v]):
            if u == p:
                dp[v][i] = dpP
            else:
                d = dpSum[v] - dp[v][i]
                bfs(u, d, v)
    
    bfs(0)
    for i in range(N):
        # print("dpSum[{}]=[{}, {}]".format(i, dpSum[i].dp, dpSum[i].t))
        print(int(dpSum[i].dp))



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from functools import reduce
p = 1000000007  #ここを変える
ccache = []
inv_ccache = []
def powmod(a, n):
    global p
    res = 1
    tmp=a
    while n>0:
        if n & 1 == 1:
            res = (res * tmp) % p
        n=n//2
        tmp = tmp * tmp % p
    return res
def invmod(n):
    return powmod(n, p - 2)
def cmod(n, r):
    global p
    global ccache
    global inv_ccache
    global N
    if len(ccache) == 0:
      ccache.append(1)
      inv_ccache.append(1)
      for i in range(N):
        ccache.append(ccache[i]*(i+1)%p)
        inv_ccache.append(1)
      inv_ccache[N]=invmod(ccache[N])
      for i in range(N-1):
        inv_ccache[N-1-i]=inv_ccache[N-i]*(N-i)%p
    if r > n or r < 0:
        return 0
    if r > n // 2:
        return cmod(n, n - r)
    return ccache[n]*inv_ccache[r]%p*inv_ccache[n-r]%p
 
n = int(input())
adj_of = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    adj_of[a - 1].append(b - 1)
    adj_of[b - 1].append(a - 1)
stack = [(0, -1)] # root, excludee
course = []
while len(stack) > 0:
    popped = stack.pop()
    course.append(popped)
    for adj in adj_of[popped[0]]:
        if adj != popped[1]:
            stack.append((adj, popped[0]))
sizes = [{} for _ in range(n)] #size, pattern_num
pattern_nums = [{} for _ in range(n)]
for step in reversed(course):
    size = 1
    pattern_num = 1
    for adj in adj_of[step[0]]:
        if adj != step[1]:
            size += sizes[adj][step[0]]
            pattern_num *= pattern_nums[adj][step[0]] * cmod(size - 1, sizes[adj][step[0]]) % p
            pattern_num %= p
    sizes[step[0]][step[1]] = size
    pattern_nums[step[0]][step[1]] = pattern_num
 
#print(course)
#print(sizes)
#print(pattern_nums)
 
ans = [None] * n
for step in course:
    if step[0] == 0:
        ans[0] = pattern_nums[0][-1]
        continue
    #ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums[step[1]][step[0]]\
    #             * cmod(sizes[step[0]][step[1]] + sizes[step[1]][step[0]], sizes[step[0]][step[1]]) % p
    pattern_nums_step1_step0 = ans[step[1]] * invmod(cmod(n - 1, sizes[step[0]][step[1]]) % p * pattern_nums[step[0]][step[1]]) % p
    ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums_step1_step0 % p\
                 * cmod(n - 1, sizes[step[0]][step[1]] - 1) % p
 
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
from functools import reduce
p = 1000000007  #ここを変える
ccache = []
inv_ccache = []
def powmod(a, n):
    global p
    res = 1
    while n>0:
        res = (res * res) % p
        if n & 1 == 1:
            res = (res * a) % p
    return res
def invmod(n):
    return powmod(n, p - 2)
def cmod(n, r):
    global p
    global ccache
    global inv_ccache
    if len(ccache) = 0:
      ccache.append(1)
      inv_ccache.append(1)
      for i in range(1000000):
        ccache.append(ccache[i]*(i+1)%p)
        inv_ccache.append(invmod(ccache[i+1]))
    if r > n or r < 0:
        return 0
    if r > n // 2:
        return cmod(n, n - r)
    return ccache[n]*inv_ccache[r]%p*inv_ccache[n-r]%p
 
n = int(input())
adj_of = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    adj_of[a - 1].append(b - 1)
    adj_of[b - 1].append(a - 1)
stack = [(0, -1)] # root, excludee
course = []
while len(stack) > 0:
    popped = stack.pop()
    course.append(popped)
    for adj in adj_of[popped[0]]:
        if adj != popped[1]:
            stack.append((adj, popped[0]))
sizes = [{} for _ in range(n)] #size, pattern_num
pattern_nums = [{} for _ in range(n)]
for step in reversed(course):
    size = 1
    pattern_num = 1
    for adj in adj_of[step[0]]:
        if adj != step[1]:
            size += sizes[adj][step[0]]
            pattern_num *= pattern_nums[adj][step[0]] * cmod(size - 1, sizes[adj][step[0]]) % p
            pattern_num %= p
    sizes[step[0]][step[1]] = size
    pattern_nums[step[0]][step[1]] = pattern_num
 
#print(course)
#print(sizes)
#print(pattern_nums)
 
ans = [None] * n
for step in course:
    if step[0] == 0:
        ans[0] = pattern_nums[0][-1]
        continue
    #ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums[step[1]][step[0]]\
    #             * cmod(sizes[step[0]][step[1]] + sizes[step[1]][step[0]], sizes[step[0]][step[1]]) % p
    pattern_nums_step1_step0 = ans[step[1]] * invmod(cmod(n - 1, sizes[step[0]][step[1]]) % p * pattern_nums[step[0]][step[1]]) % p
    ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums_step1_step0 % p\
                 * cmod(n - 1, sizes[step[0]][step[1]] - 1) % p
 
for a in ans:
    print(a)

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
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)

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

size_d = [0]*(N+1)
dp_d = [1]*(N+1)

for v in order[::-1]:  # 根に遠いほうから(down方向のボトムアップ)
    dp_d[v] *= fact[size_d[v]]
    dp_d[v] %= mod
    p = parent[v]
    s = size_d[v] + 1
    size_d[p] += s
    dp_d[p] *= fact_inv[s] * dp_d[v]
    dp_d[p] %= mod

size_u = [N-1-x for x in size_d]
dp_u = [1]*(N+1)

modmul = lambda x, y: x*y%mod

def merge(p1, p2):
    den_inv1, v1 = p1
    den_inv2, v2 = p2
    return den_inv1*den_inv2%mod, v1*v2%mod

for v in order:
    p = parent[v]
    arr = [(fact_inv[size_d[node]+1], dp_d[node]) if node != p else (fact_inv[size_u[v]], dp_u[v]) for node in tree[v]]
    left = [(1, 1)] + list(accumulate(arr, merge))[:-1]
    right = list(accumulate(arr[::-1], merge))[-2::-1] + [(1, 1)]
    contrib = [merge(x, y) for x, y in zip(left, right)]
    for node, c in zip(tree[v], contrib):
        if node != p:
            dp_u[node] = (c[0]*c[1]*fact[size_u[node]-1])%mod
# print(dp_u)
for xd, xu, sd, su in zip(dp_d[1:], dp_u[1:], size_d[1:], size_u[1:]):
    x = xd * xu * fact[sd + su] * fact_inv[sd] * fact_inv[su] % mod
    print(x)

Submission status: Runtime Error

Solution code:
from functools import *
from collections import *
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.buffer.readline
 
M = 10**9+7
N = int(input())

@lru_cache(maxsize=None)
def mod_inv(x):
  if x == 1:
    return 1
  return M // x * -mod_inv(M%x) % M

weght = [0]*(N+1)
size = [0]*(N+1)
def calc_subtree(v):
  W = 1
  S = 1
  for child in Edge[v]:
    Edge[child].remove(v)
    w, s = calc_subtree(child)
    W = W * w % M
    S += s
  weight[v] = W * S % M
  size[v] = S
  return weight[v], size[v]

ans = [0]*(N+1)
def set_ans(v, a):
  ans[v] = a
  for child in Edge[v]:
    n = calc_subtree(child)[1]
    set_ans(child, ans[v] * n * mod_inv(N-n) % M)

Edge = defaultdict(set)
fact = N
for i in range(1, N):
  fact = fact * i % M
  a, b = map(int, input().split())
  Edge[a].add(b)
  Edge[b].add(a)

set_ans(1, mod_inv(calc_subtree(1)[0]) * fact % M)
for i in range(1, N+1):
  print(ans[i])

Submission status: Runtime Error

Solution code:
n, *L = map(int, open(0).read().split())
mod = 10 ** 9 + 7
con = [[] for _ in range(n + 1)]
sz = [1] * (n + 1)
par = [0] * (n + 1)

for s, t in zip(*[iter(L)] * 2):
	con[s] += t,
	con[t] += s,


def prepare(m, mod=10 ** 9 + 7):
	fac = [1] * (m + 1)
	inv = [1] * (m + 1)
	for i in range(1, m + 1):
		fac[i] = fac[i - 1] * i % mod
	inv[-1] = pow(fac[-1], mod - 2, mod)
	for i in range(m - 1, -1, -1):
		inv[i] = inv[i + 1] * (i + 1) % mod
	return fac, inv


fac, inv = prepare(n)


def dfs1(cur, pre):
	par[cur] = pre
	for nxt in con[cur]:
		if nxt != pre:
			dfs1(nxt, cur)
			sz[cur] += sz[nxt]
			dp1[cur] *= dp1[nxt] * inv[sz[nxt]] % mod
			dp1[cur] %= mod
	dp1[cur] *= fac[sz[cur] - 1]
	dp1[cur] %= mod


def dfs2(cur, pre):
	dp2[cur] *= dp1[cur] * inv[sz[cur] - 1] % mod
	dp2[cur] %= mod
	dp2[cur] *= fac[n - 1]
	dp2[cur] %= mod
	for nxt in con[cur]:
		if nxt != pre:
			dp2[nxt] = fac[sz[nxt]] * pow(n - sz[nxt], mod - 2, mod) * pow(dp1[nxt], mod - 2, mod) * dp2[cur] * inv[n - 1] % mod
			dfs2(nxt, cur)


dp1 = [1] * (n + 1)
dfs1(1, 0)
dp2 = [1] * (n + 1)
dfs2(1, 0)

print(*dp2[1:], sep="\n")

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**6)

# 組み合わせ
mod = 10 ** 9 + 7
N = 2* 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
# 深さ優先探索
def dfs(v, p=-1):
    
    dp_l = 1  # 自分自身しかない場合
    size_l = 1 # 自分自身のサイズを含める

    # 子の情報をあわせて数え上げる
    for u in E[v]:
        
        # 親へのルートは辿らない
        if u == p:
            continue

        d, s = dfs(u, v)
        d %= mod
        size_l += s
        dp_l = dp_l * d * cmb(size_l-1, s) % mod

    dp[v] = dp_l
    size[v] = size_l
        
    return (int(dp_l), size_l)
  
def bfs(v, p=-1):
    
    for u in E[v]:
        if u == p:
            continue
        
        # u がなくなった場合の dp[v] 値、 size を求める
        # 一旦、uを切り離す

        o_size = size[v] - size[u]

        partial_v = int(dp[v] / dp[u] / cmb(N - 1, size[u]))
        
        # print(partial_v, dp[u])
        
        # u に v 側の部分木が接続された場合の値を求める
        # u に v を根とする部分木をつける

        dp_l = dp[u] * partial_v * cmb(N-1, size[u]-1) % mod
        
        dp[u] = dp_l % mod
    
        bfs(u,v)
        
# 入力処理
# N = int(input())
# E = [[] for _ in range(N)]

# for _ in range(N-1):
#     a, b = map(int, input().split())
#     E[a-1].append(b-1)
#     E[b-1].append(a-1)
      
dp = [1] * N
size = [1] * N


dfs(0)

bfs(0)

for i in range(N):
    print(dp[i])

Submission status: Runtime Error

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

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

mod = 10**9+7 #出力の制限
N = 10**5+10
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

# topological sort
s = []
s.append(0)
parent = [-1]*n
order = []
while s:
    v = s.pop()
    order.append(v)
    for u in g[v]:
        if u == parent[v]:
            continue
        parent[u] = v
        s.append(u)

dp = [1]*n
c = [0]*n
order.reverse()
for v in order:
    dp[v] *= g1[c[v]]
    dp[v] %= mod
    c[v] += 1
    if parent[v] == -1:
        continue
    c[parent[v]] += c[v]
    dp[parent[v]] *= (dp[v]*g2[c[v]])
    dp[parent[v]] %= mod

order.reverse()
ans = [0]*n
for v in order:
    ans[v] = dp[v]
    for u in g[v]:
        if u == parent[v]:
            continue
        dp[u] *= ans[v]*g2[c[v]-1]*g1[c[v]-1-c[u]]*g1[c[u]]*pow(dp[u],(mod-2),mod)
        dp[u] *= g2[c[u]-1]
        dp[u] *= g1[c[v]-1]
        dp[u] *= g2[c[v]-c[u]]
        dp[u] %= mod
        c[u] = c[v]
for i in range(n):
    print(ans[i]%mod)

Submission status: Runtime Error

Solution code:
from functools import *
from collections import *

M = 10**9+7

@lru_cache(maxsize=None)
def mod_inv(a):
  b, x, y = M, 1, 0
  while a != 1:
    (d, a), b = divmod(b, a), a
    x, y = y-d*x, x
  return x%M

cache = defaultdict(dict)
def calc_cache(self, parent):
  c = cache[self]
  if not c or parent in c:
    return c[parent]
  
  if c and None not in c:
    for p, (r2, t2, s2) in c.items():
      r3, t3, s3 = calc_cache(p, self)
      r = r2 * t3
      s = s2 + s3
      c[None] = r, None, s
      break
  
  if parent is None:
    return c[parent]
  
  if None in c:
    r0, t0, s0 = c[None]
    r1, t1, s1 = calc_cache(parent, self)
    r = r0 * mod_inv(t1) % M
    s = s0 - s1
    c[parent] = r, r * mod_inv(s) % M, s
    return c[parent]

N = int(input())
Edge = defaultdict(set)
fact = 1
for i in range(1, N):
  fact = fact * i % M
  a, b = map(int, input().split())
  Edge[a].add(b)
  Edge[b].add(a)

cache = defaultdict(dict)
stack = [None, 1]
children = {}
while len(stack) > 1:
  parent = stack[-2]
  self = stack[-1]
  if self not in children:
    children[self] = Edge[self]-{parent}
  if children[self]:
    stack.append(children[self].pop())
  else:
    ret = 1
    size = 1
    for child in (Edge[self] - {parent}):
      r, t, s = cache[child][self]
      ret = ret * t % M
      size += s
    cache[self][parent] = ret, ret * mod_inv(size) % M if parent else None, size
    stack.pop()

for i in range(1, N+1):
  print(calc_cache(i, None)[0] * fact % M)

Submission status: Runtime Error

Solution code:
import math
import sys
sys.setrecursionlimit(10**6)

# 組み合わせ
mod = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

# 深さ優先探索
def dfs(v, p=-1):
    
    dp_l = 1  # 自分自身しかない場合
    size_l = 1 # 自分自身のサイズを含める

    # 子の情報をあわせて数え上げる
    for u in E[v]:
        
        # 親へのルートは辿らない
        if u == p:
            continue

        d, s = dfs(u, v)
        d %= mod
        size_l += s

        comb = int(math.factorial(size_l - 1) / (math.factorial((size_l - 1) - s)) / (math.factorial(s)))
        dp_l = dp_l * d * comb

    dp[v] = dp_l
    size[v] = size_l
        
    return (int(dp_l), size_l)

  
def bfs(v, p=-1):
    
    for u in E[v]:
        if u == p:
            continue
        
        # u がなくなった場合の dp[v] 値、 size を求める
        # 一旦、uを切り離す

        o_size = size[v] - size[u]

        partial_v = int(dp[v] / dp[u] / cmb(N - 1, size[u]))
        
        # u に v 側の部分木が接続された場合の値を求める
        # u に v を根とする部分木をつける

        dp_l = dp[u] * partial_v * cmb(N-1, size[u]-1)
        
        dp[u] = dp_l
    
        bfs(u,v)

# 入力処理
N = int(input())
E = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
      
dp = [1] * N
size = [1] * N

dfs(0)
bfs(0)

for i in range(N):
    print(dp[i])

Submission status: Runtime Error

Solution code:
import math
import sys
sys.setrecursionlimit(10**6)

# 組み合わせ
mod = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

# 深さ優先探索
def dfs(v, p=-1):
    
    dp_l = 1  # 自分自身しかない場合
    size_l = 1 # 自分自身のサイズを含める

    # 子の情報をあわせて数え上げる
    for u in E[v]:
        
        # 親へのルートは辿らない
        if u == p:
            continue

        d, s = dfs(u, v)
        d %= mod
        size_l += s

        comb = int(math.factorial(size_l - 1) / (math.factorial((size_l - 1) - s)) / (math.factorial(s)))
        dp_l = dp_l * d * comb

    dp[v] = dp_l
    size[v] = size_l
        
    return (int(dp_l), size_l)

  
def bfs(v, p=-1):
    
    for u in E[v]:
        if u == p:
            continue
        
        # u がなくなった場合の dp[v] 値、 size を求める
        # 一旦、uを切り離す

        o_size = size[v] - size[u]

        partial_v = int(dp[v] / dp[u] / cmb(N - 1, size[u]))
        
        # u に v 側の部分木が接続された場合の値を求める
        # u に v を根とする部分木をつける

        dp_l = dp[u] * partial_v * cmb(N-1, size[u]-1)
        
        dp[u] = dp_l
    
        bfs(u,v)

# 入力処理
N = int(input())
E = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
      
dp = [0] * N
size = [0] * N

dfs(0)
bfs(0)

for i in range(N):
    print(dp[i])

Submission status: Runtime Error

Solution code:
import math
import sys
sys.setrecursionlimit(10**6)

# 組み合わせ
mod = 10 ** 9 + 7
N = 10 ** 6  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = int(input())
E = [[] for _ in range(N)]

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

# 深さ優先探索
def dfs(v, p=-1):
    
    dp_l = 1  # 自分自身しかない場合
    size_l = 1 # 自分自身のサイズを含める

    # 子の情報をあわせて数え上げる
    for u in E[v]:
        
        # 親へのルートは辿らない
        if u == p:
            continue

        d, s = dfs(u, v)
        d %= mod
        size_l += s

        comb = int(math.factorial(size_l - 1) / (math.factorial((size_l - 1) - s)) / (math.factorial(s)))
        dp_l = dp_l * d * comb

    dp[v] = dp_l
    size[v] = size_l
        
    return (int(dp_l), size_l)
  
def bfs(v, p=-1):
    
    for u in E[v]:
        if u == p:
            continue
        
        o_size = size[v] - size[u]

        tmp = int(dp[v] / dp[u] / (math.factorial(N - 1) / (math.factorial(size[u]) * math.factorial(N - 1 - size[u]))))
        
        # comb = int(math.factorial((size[u] - 1) + (N - size[u])) / (math.factorial(size[u] - 1) * math.factorial(N - size[u])))
        comb = int(math.factorial(N - 1) / (math.factorial(size[u] - 1) * math.factorial(N - size[u])))
        dp_l = dp[u] * tmp * comb
        
        dp[u] = dp_l
    
        bfs(u,v)

dp = [0] * N
size = [0] * N

dfs(0)
bfs(0)

for i in range(N):
    print(dp[i])

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys


MAX_INT = 2**62-1
sys.setrecursionlimit(10**7)

input = sys.stdin.readline

# @profile
MOD = 10**9 + 7


def mul_mod(a, b, mod=MOD):
    return (a * b) % mod

@profile
def solve(g, f, fi, m):
    mul = mul_mod

    stack = [(0, 1)]
    pre_order = []
    n = len(g) - 1

    while stack:
        pre, cur = stack.pop()
        pre_order.append((pre, cur))

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    size = [1] * (n+1)
    dp = [1] * (n+1)

    for pre, cur in reversed(pre_order):
        dp[cur] = mul(dp[cur], f[size[cur]-1])
        dp[pre] = mul(mul(dp[pre], dp[cur]), fi[size[cur]])
        size[pre] += size[cur]

    ans = [1] * (n+1)
    ans[1] = dp[1]

    for pre, cur in pre_order[1:]:
        ans[cur] = mul(ans[pre], size[cur]) // (n-size[cur])
    print(*ans[1:], sep='\n')


# @profile
def main():
    mul = mul_mod
    mod = MOD
    n = int(input())
    g = [[] for _ in range(n+1)]

    fact = [1] * (n+1)
    fact_inv = [0] * (n+1)

    for i in range(1, n+1):
        fact[i] = mul(fact[i-1], i)

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(n)[::-1]:
        fact_inv[i] = mul(fact_inv[i+1], (i+1))

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

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()

Submission status: Runtime Error

Solution code:
import math

mod = 10**9 + 7

N = int(input())
E = [[] for _ in range(N)]

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

# 深さ優先探索
def dfs(v, p=-1):
    
    dp_l = 1  # 自分自身しかない場合
    size_l = 1 # 自分自身のサイズを含める

    # 子の情報をあわせて数え上げる
    for u in E[v]:
        
        # 親へのルートは辿らない
        if u == p:
            continue

        d, s = dfs(u, v)
        d %= mod
        size_l += s

        comb = int(math.factorial(size_l - 1) / (math.factorial((size_l - 1) - s)) / (math.factorial(s)))
        dp_l = dp_l * d * comb

    dp[v] = dp_l
    size[v] = size_l
        
    return (int(dp_l), size_l)
  
def bfs(v, p=-1):
    
    for u in E[v]:
        if u == p:
            continue
        
        o_size = size[v] - size[u]

        tmp = int(dp[v] / dp[u] / (math.factorial(N - 1) / (math.factorial(size[u]) * math.factorial(N - 1 - size[u]))))
        
        # comb = int(math.factorial((size[u] - 1) + (N - size[u])) / (math.factorial(size[u] - 1) * math.factorial(N - size[u])))
        comb = int(math.factorial(N - 1) / (math.factorial(size[u] - 1) * math.factorial(N - size[u])))
        dp_l = dp[u] * tmp * comb
        
        dp[u] = dp_l
    
        bfs(u,v)

dp = [0] * N
size = [0] * N

dfs(0)
bfs(0)

for i in range(N):
    print(dp[i])

Submission status: Runtime Error

Solution code:
# 全方位DP
from collections import defaultdict, deque
from math import factorial

MOD = 10**9+7
class Facts():
    def __init__(self, max_num=10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[k]
        c = self.fact[n-k]
        return (a*self.power_func(b, self.p-2) *
                self.power_func(c, self.p-2)) % self.p

    def power_func(self, a, b):
        ans = 1
        while b > 0:
            if b & 1:
                ans = ans * a % self.p
            a = a * a % self.p
            b >>= 1
        return ans

    def fact_inv(self, a):
        return self.power_func(a, self.p-2) % self.p

n = int(input())
fact = Facts(max_num=200000)
edges = defaultdict(lambda: [])

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

# step1 吸い上げ
size = [1 for _ in range(n+1)]
def dfs1(n, par=-1):
    res = 1
    for node in edges[n]:
        if node == par:
            continue
        else:
            res += dfs1(node, n)
    res %= MOD
    size[n] = res
    return res
dfs1(1)
# print(size)
dp = [0 for _ in range(n+1)]
def dfs2(n, par=-1):
    res = fact.fact[size[n] - 1]
    for node in edges[n]:
        if node == par:
            continue
        else:
            res *= dfs2(node, n) * fact.fact_inv(fact.fact[size[node]])
    res %= MOD
    dp[n] = res
    return res
dfs2(1)
# print(dp)

# step2 還元
ans = [0 for _ in range(n+1)]
def dfs3(num, par=-1):
    if par != -1:
        d_par = ans[par] * fact.fact_inv(fact.fact[n-1]) * fact.fact[n-size[num]-1] * fact.fact[size[num]] * fact.fact_inv(dp[num]) % MOD
        res = dp[num] * fact.fact_inv(fact.fact[size[num] - 1]) * fact.fact[n-1] * d_par * fact.fact_inv(fact.fact[n-size[num]]) % MOD
        ans[num] = res
    else:
        ans[num] = dp[num]
    for node in edges[num]:
        if node == par:
            continue
        dfs3(node, num)
dfs3(1)
print("\n".join(list(map(str, ans[1:]))))