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: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b): return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

#零元
zero = T(1, 0)
#一個上に遷移した時の変化
#def step(x): return T(x.num, x.child+1)
#マージ
def merge(x, y):
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(N)]
down_data = [zero for _ in range(N)]
dat = [zero for _ in range(N)]
rev_data = [zero for _ in range(N)]

class p:
    num = -1
    parent = -1

    def __init__(self, x, y):
        self.num = x
        self.parent = y
node_list = []
def makeNodeList(root):
    #dfsでの探索順の作成
    stack = []
    stack.append(p(root, -1))
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now.num]:
            if to == now.parent: continue
            stack.append(p(to, now.num))
    node_list.reverse()

def dfs(root):
    for now in node_list:
        for to in G[now.num]:
            if to == now.parent: continue
            #down_data[now.num] = merge(down_data[now.num], step(down_data[to]))
            down_data[now.num] = merge(down_data[now.num], T(down_data[to].num, down_data[to].child+1))


def dfs_rev(root):
    for now in node_list:
        #累積
        rev = rev_data[now.num]
        left = []
        right = []
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            if len(left)==0: left.append(T(down_data[to].num, down_data[to].child+1))
            else: left.append(merge(left[cnt-1], T(down_data[to].num, down_data[to].child+1)))
            cnt += 1
        cnt = 0
        for to in reversed(G[now.num]):
            if to==now.parent: continue
            if len(right)==0: right.append(T(down_data[to].num, down_data[to].child+1))
            else: right.append(merge(right[cnt-1], T(down_data[to].num, down_data[to].child+1)))
            cnt += 1
        dat[now.num] = merge(rev, down_data[now.num])
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            x = zero if cnt==0 else left[cnt-1]
            y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
            z = merge(rev, merge(x, y))
            rev_data[to] = T(z.num, z.child+1)
            cnt += 1

def calc(data_num):
    root = -1
    for i in range(1, data_num+1):
        if len(G[i]) == 1:
            root = i
            break
    makeNodeList(root)
    dfs(root)
    node_list.reverse()
    dfs_rev(root)
#-------------------------------------------------------------------
def main():
    n = int(input())
    for i in range(n-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    calc(n)

    for i in range(1, n+1): print(dat[i].num)

if __name__ == "__main__": main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(4100000)

#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b): return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

#零元
zero = T(1, 0)
#一個上に遷移した時の変化
def step(x):
    return T(x.num, x.child+1)
#マージ
def merge(x, y):
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(N)]
down_data = [zero for _ in range(N)]
dat = [zero for _ in range(N)]
rev_data = [zero for _ in range(N)]


class p:
    num = -1
    parent = -1

    def __init__(self, x, y):
        self.num = x
        self.parent = y
node_list = []
def makeNodeList(root):
    #dfsでの探索順の作成
    stack = []
    stack.append(p(root, -1))
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now.num]:
            if to == now.parent: continue
            stack.append(p(to, now.num))

def dfs(root):
    for i in range(len(node_list)):
        now = node_list[len(node_list)-1-i]
        for to in G[now.num]:
            if to == now.parent: continue
            down_data[now.num] = merge(down_data[now.num], step(down_data[to]))

def dfs_rev(root):
    for now in node_list:
        #累積
        rev = rev_data[now.num]
        left = []
        right = []
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            if len(left)==0: left.append(step(down_data[to]))
            else: left.append(merge(left[cnt-1], step(down_data[to])))
            cnt += 1
        cnt = 0
        for to in reversed(G[now.num]):
            if to==now.parent: continue
            if len(right)==0: right.append(step(down_data[to]))
            else: right.append(merge(right[cnt-1], step(down_data[to])))
            cnt += 1
        dat[now.num] = merge(rev, down_data[now.num])
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            x = zero if cnt==0 else left[cnt-1]
            y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
            rev_data[to] = step(merge(rev, merge(x, y)))
            cnt += 1

def calc(data_num):
    root = -1
    for i in range(1, data_num+1):
        if len(G[i]) == 1:
            root = i
            break
    makeNodeList(root)
    dfs(root)
    dfs_rev(root)
#-------------------------------------------------------------------
def main():
    n = int(input())
    for i in range(n-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    calc(n)
    for i in range(1, n+1): print(dat[i].num)

if __name__ == "__main__": main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b): return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

#零元
zero = T(1, 0)
#一個上に遷移した時の変化
def step(x):
    return T(x.num, x.child+1)
#マージ
def merge(x, y):
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(N)]
down_data = [zero for _ in range(N)]
dat = [zero for _ in range(N)]
rev_data = [zero for _ in range(N)]


node_list = []
def makeNodeList(root):
    #dfsでの探索順の作成
    stack = []
    stack.append([root, -1])
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now[0]]:
            if to == now[1]: continue
            stack.append([to, now[0]])

def dfs(root):
    for i in range(len(node_list)):
        now = node_list[len(node_list)-1-i]
        for to in G[now[0]]:
            if to == now[1]: continue
            down_data[now[0]] = merge(down_data[now[0]], step(down_data[to]))

def dfs_rev(root):
    for now in node_list:
        #累積
        rev = rev_data[now[0]]
        left = []
        right = []
        cnt = 0
        for to in G[now[0]]:
            if to==now[1]: continue
            if len(left)==0: left.append(step(down_data[to]))
            else: left.append(merge(left[cnt-1], step(down_data[to])))
            cnt += 1
        cnt = 0
        for to in reversed(G[now[0]]):
            if to==now[1]: continue
            if len(right)==0: right.append(step(down_data[to]))
            else: right.append(merge(right[cnt-1], step(down_data[to])))
            cnt += 1
        dat[now[0]] = merge(rev, down_data[now[0]])
        cnt = 0
        for to in G[now[0]]:
            if to==now[1]: continue
            x = zero if cnt==0 else left[cnt-1]
            y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
            rev_data[to] = step(merge(rev, merge(x, y)))
            cnt += 1

def calc(data_num):
    root = -1
    for i in range(1, data_num+1):
        if len(G[i]) == 1:
            root = i
            break
    makeNodeList(root)
    dfs(root)
    dfs_rev(root)
#-------------------------------------------------------------------
def main():
    n = int(input())
    for i in range(n-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    calc(n)
    for i in range(1, n+1): print(dat[i].num)

if __name__ == "__main__": main()

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(4100000)

#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b or b < 0: return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

#零元
zero = T(1, 0)
#一個上に遷移した時の変化
def step(x):
    return T(x.num, x.child+1)
#マージ
def merge(x, y):
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(N)]
down_data = [zero for _ in range(N)]
dat = [zero for _ in range(N)]
rev_data = [zero for _ in range(N)]

class p:
    num = -1
    parent = -1

    def __init__(self, x, y):
        self.num = x
        self.parent = y
node_list = []
def makeNodeList(root):
    #dfsでの探索順の作成
    stack = []
    stack.append(p(root, -1))
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now.num]:
            if to == now.parent: continue
            stack.append(p(to, now.num))
    node_list.reverse()

def dfs(root):
    for now in node_list:
        for to in G[now.num]:
            if to == now.parent: continue
            down_data[now.num] = merge(down_data[now.num], step(down_data[to]))

def dfs_rev(root):
    for now in node_list:
        #累積
        rev = rev_data[now.num]
        left = []
        right = []
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            if len(left)==0: left.append(step(down_data[to]))
            else: left.append(merge(left[cnt-1], step(down_data[to])))
            cnt += 1
        cnt = 0
        for to in reversed(G[now.num]):
            if to==now.parent: continue
            if len(right)==0: right.append(step(down_data[to]))
            else: right.append(merge(right[cnt-1], step(down_data[to])))
            cnt += 1
        dat[now.num] = merge(rev, down_data[now.num])
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            x = zero if cnt==0 else left[cnt-1]
            y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
            rev_data[to] = step(merge(rev, merge(x, y)))
            cnt += 1

def calc(data_num):
    root = -1
    for i in range(1, data_num+1):
        if len(G[i]) == 1:
            root = i
            break
    makeNodeList(root)
    dfs(root)
    node_list.reverse()
    dfs_rev(root)
#-------------------------------------------------------------------
def main():
    n = int(input())
    for i in range(n-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    calc(n)
    #for i in range(1, n+1): print(down_data[i].num, down_data[i].child)

    for i in range(1, n+1): print(dat[i].num)

if __name__ == "__main__": main()

Submission status: Accepted

Solution code:
#f
from functools import reduce
p = 1000000007  #ここを変える
cmod_max = 200000  #ここを変える
ccache = []
inv_ccache = [None] * (cmod_max + 1)
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
    if len(ccache) == 0:
        ccache.append(1)
        for i in range(cmod_max):
            ccache.append(ccache[i]*(i+1)%p)
        inv_ccache[cmod_max] = invmod(ccache[cmod_max])
        for i in range(cmod_max, 0, -1):
            inv_ccache[i - 1] = inv_ccache[i] * 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]])
            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]]) * pattern_nums[step[0]][step[1]]) % p
    ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums_step1_step0\
                 * cmod(n - 1, sizes[step[0]][step[1]] - 1) % p

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)


"""
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の値の更新（今回は組み合わせ含む掛け算）と
    木のサイズの合算を同時にやってくれるようにする。
    dp計算は全てmodを取ることに注意。
    """
    def __init__(self, m_dp=1, m_t=0, mod=10**9+7):
        self.dp = m_dp
        self.t = m_t
        self.mod = mod
    
    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.dp %= self.mod
        self.t += other.t
        return self
    
    def __sub__(self, other):
        """
        引き算も同様にオーバーロード（ただしこっちは二項演算）。
        また、こちらはbfsで親の木のdp値を送ることを念頭においていることに注意。
        """
        dp = self.dp * pow(other.dp * cmb(self.t - 1, other.t), self.mod - 2, self.mod) # 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: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs_1(s,p): #部分木のサイズを数えるdfs
    par[s] = p
    for v in edges[s]:
        if v == p:
            continue
        size[s] += dfs_1(v,s)
    return size[s]

def dfs_2(s,p): #1を根としたときに進む向きのdp計算用dfs
    dp1[s] = fact[size[s]-1]
    for v in edges[s]:
        if v == p:
            continue
        dp1[s] = (dp1[s]*dfs_2(v,s))%mod
        dp1[s] = (dp1[s]*pow(fact[size[v]], mod-2, mod))%mod
    return dp1[s]

def comb(n,r):
    return fact[n]*pow(fact[r],mod-2,mod)*pow(fact[n-r],mod-2,mod) % mod

def bfs(s):
    que = deque()
    que.append((s,-1))
    while que:
        v,p = que.popleft()
        if v == 0:
            dp2[v] = dp1[v]
        else:
            inv = (dp2[p]*pow((dp1[v]*comb(n-1,size[v]))%mod,mod-2,mod)) % mod
            dp2[v] = (dp1[v]*inv*comb(n-1,size[v]-1)) % mod
        for u in edges[v]:
            if u == p:
                continue
            que.append((u,v))
n = I()
fact = [1]*(n+1)
par = [None]*n
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

edges = [[] for _ in range(n)]
size = [1]*n
dp1 = [0]*n #1を根としたときに進む向きのdp
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

dfs_1(0,-1)
dfs_2(0,-1)
dp2 = [0]*n
bfs(0)
for i in dp2:
    print(i)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs_1(s,p): #部分木のサイズを数えるdfs
    par[s] = p
    for v in edges[s]:
        if v == p:
            continue
        size[s] += dfs_1(v,s)
    return size[s]

def dfs_2(s,p): #1を根としたときに進む向きのdp計算用dfs
    dp1[s] = fact[size[s]-1]
    for v in edges[s]:
        if v == p:
            continue
        dp1[s] *= dfs_2(v,s)
        dp1[s] %= mod
        dp1[s] *= pow(fact[size[v]], mod-2, mod)
        dp1[s] %= mod
    return dp1[s]

def comb(n,r):
    return fact[n]*pow(fact[r],mod-2,mod)*pow(fact[n-r],mod-2,mod) % mod

def bfs(s): #dp1と逆向きに進むdp計算用bfs
    que = deque()
    que.append((s,-1))
    while que:
        v,p = que.popleft()
        if v == 0:
            dp2[v] = dp1[v]
        else:
            inv = (dp2[p]*pow((dp1[v]*comb(n-1,size[v]))%mod,mod-2,mod)) % mod
            dp2[v] = (dp1[v]*inv*comb(n-1,size[v]-1)) % mod
        for u in edges[v]:
            if u == p:
                continue
            que.append((u,v))
n = I()
fact = [1]*(n+1)
par = [None]*n
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

edges = [[] for _ in range(n)]
size = [1]*n
dp1 = [0]*n #1を根としたときに進む向きのdp
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

dfs_1(0,-1)
dfs_2(0,-1)
dp2 = [0]*n
bfs(0)
for i in dp2:
    print(i)

Submission status: Accepted

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
    if len(ccache) == 0:
      ccache.append(1)
      inv_ccache.append(1)
      for i in range(210000):
        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)