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:
class Combination():
    def __init__(self, n, mod):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


class Rerooting(Combination):
    def __init__(self, adjacent, n, mod):
        super(Rerooting, self).__init__(n, mod)
        self.n = n
        self.adj = adjacent   # 0-indexedの配列で用意！
        # DFSで行きがけ順を記録
        self.order = []
        stack = [0]
        self.parent = [-1]*(n)
        while stack:
            node = stack.pop()
            self.order.append(node)
            for child in self.adj[node]:
                if self.parent[node] == child:
                    continue
                stack.append(child)
                self.parent[child] = node
    
    def merge(self, parent, child):
        # childの値をparentに統合する処理
        self.size[parent] += self.size[child]
        self.dp[parent] *= self.combination(self.size[parent]-1,self.size[child])
        self.dp[parent] %= self.mod
        self.dp[parent] *= self.dp[child]
        self.dp[parent] %= self.mod
        return self.dp[parent]

    def remerge(self, parent, child):
        # childの値が根となるときの統合処理
        self.dp[child] = self.size[child]*self.dp[parent]
        self.dp[child] *= pow(self.n-self.size[child], self.mod -2, self.mod)
        self.dp[child] %= self.mod
        return self.dp[child]

    def calc_subtree(self):
        # 帰りがけ順で木DPを行う
        # 根が0の時の値を算出
        self.dp = [1]*(self.n)
        self.size = [1]*(self.n)
        for node in self.order[::-1]:
            if self.parent[node] == -1:
                continue
            self.merge(self.parent[node], node)

    def root_subtree(self):
        # 行きがけ順で
        for node in self.order[1:]:
            p = self.parent[node]
            self.remerge(p, node)
        return self.dp
        

def main():
    import sys
    input = lambda: sys.stdin.buffer.readline().rstrip()
    n = int(input())
    mod = 10**9 + 7
    adj = [[] for i in range(n)]
    for i in range(n-1):
        a, b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)

    r = Rerooting(adj, n, mod)
    r.calc_subtree()
    dp = r.root_subtree()

    for ans in dp:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

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

F = Factorial(N + 2, MOD)

root = 1
stack = [root]
check = [False] * (N + 1)
check[root] = True
p = [0] * (N + 1) 

DAG = []

while stack:
    now_ = stack.pop()
    DAG.append(now_)
    for next_ in G[now_]:
        if check[next_]:
            continue
        stack.append(next_)
        check[next_] = True
        p[next_] = now_

size1 = [0] * (N + 1)
dp1 = [1] * (N + 1)

for now_ in DAG[::-1]:
    size1[now_] += 1
    size1[p[now_]] += size1[now_]
    dp1[now_] *= F.factorial(size1[now_] - 1)
    dp1[now_] %= MOD
    dp1[p[now_]] *= dp1[now_] * F.ifactorial(size1[now_])
    dp1[p[now_]] %= MOD

# print (size1)
# print (dp1)

size2 = [N - size1[i] + 1 for i in range(N + 1)]
dp2 = [1] * (N + 1)

for i in DAG:
    parent = i
    for now_ in G[i]:
        if now_ == p[i]:
            continue
        x = dp1[parent]
        x *= F.ifactorial(size1[parent] - 1)
        x *= F.factorial(size1[now_])
        x *= pow(dp1[now_], MOD - 2, MOD)
        x *= dp2[parent]
        x *= F.ifactorial(size2[parent] - 1)
        x *= F.factorial(size2[now_] - 2)
        dp2[now_] = x % MOD
 
# print (size2)
# print (dp2)

for i in range(1, N + 1):
    ans =  dp1[i] * F.ifactorial(size1[i] - 1) * dp2[i] * F.ifactorial(size2[i] - 1) * F.factorial(N - 1)
    print (ans % MOD)

Submission status: Accepted

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

MOD = 10 ** 9 + 7

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

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

F = Factorial(N + 2, MOD)

root = 1
stack = [root]
check = [False] * (N + 1)
check[root] = True
p = [0] * (N + 1) 

DAG = []

while stack:
    now_ = stack.pop()
    DAG.append(now_)
    for next_ in G[now_]:
        if check[next_]:
            continue
        stack.append(next_)
        check[next_] = True
        p[next_] = now_

size1 = [0] * (N + 1)
dp1 = [1] * (N + 1)

for now_ in DAG[::-1]:
    size1[now_] += 1
    size1[p[now_]] += size1[now_]
    dp1[now_] *= F.factorial(size1[now_] - 1)
    dp1[now_] %= MOD
    dp1[p[now_]] *= dp1[now_] * F.ifactorial(size1[now_])
    dp1[p[now_]] %= MOD

# print (size1)
# print (dp1)

size2 = [N - size1[i] + 1 for i in range(N + 1)]
dp2 = [1] * (N + 1)

for now_ in DAG[1::]:
    parent = p[now_]
    x = dp1[parent]
    x *= F.ifactorial(size1[parent] - 1)
    x *= F.factorial(size1[now_])
    x *= pow(dp1[now_], MOD - 2, MOD)
    x *= dp2[parent]
    x *= F.ifactorial(size2[parent] - 1)
    x *= F.factorial(size2[now_] - 2)
    dp2[now_] = x % MOD
 
# print (size2)
# print (dp2)

for i in range(1, N + 1):
    ans =  dp1[i] * F.ifactorial(size1[i] - 1) * dp2[i] * F.ifactorial(size2[i] - 1) * F.factorial(N - 1)
    print (ans % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 全方位木DP、葉側と根側
N = ir()
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

MOD = 10 ** 9 + 7

fact = [1] * (N + 10)
for n in range(1, N + 10):
    fact[n] = n * fact[n - 1] % MOD
fact_inv = [1] * (N + 10)
fact_inv[-1] = pow(fact[-1], MOD - 2, MOD)
for n in range(N + 9, 0, -1):
    fact_inv[n - 1] = fact_inv[n] * n % MOD

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    cur = stack.pop()
    order.append(cur)
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        stack.append(next)

size_down = [0] * (N+1)  # 1-indexed
dp_down = [1] * (N+1)  # 葉側の組み合わせ
for v in order[::-1]:
    dp_down[v] *= fact[size_down[v]]
    dp_down[v] %= MOD
    p = parent[v]
    s = size_down[v] + 1
    size_down[p] += s
    dp_down[p] *= fact_inv[s] * dp_down[v]
    dp_down[p] %= MOD

size_up = [N-x-1 for x in size_down]  # 自分含めない
dp_up = [1] * (N+1)  # 根側の組み合わせ
for v in order[1:]:
    p = parent[v]
    x = dp_down[p]
    x *= dp_up[p]
    x *= fact_inv[size_down[p]]
    x *= fact[size_down[v] + 1]
    x *= pow(dp_down[v], MOD-2, MOD)
    x %= MOD
    x *= fact[size_up[v]-1]
    x *= fact_inv[size_up[p]]
    dp_up[v] = x % MOD

for xd, xu, sd, su in zip(dp_down[1:], dp_up[1:], size_down[1:], size_up[1:]):
    answer = xd * xu * fact[sd+su] * fact_inv[sd] * fact_inv[su] % MOD
    print(answer % MOD)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 全方位木DP、葉側と根側
N = ir()
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

MOD = 10 ** 9 + 7

fact = [1] * (N + 10)
for n in range(1, N + 10):
    fact[n] = n * fact[n - 1] % MOD
fact_inv = [1] * (N + 10)
fact_inv[-1] = pow(fact[-1], MOD - 2, MOD)
for n in range(N + 9, 0, -1):
    fact_inv[n - 1] = fact_inv[n] * n % MOD

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    cur = stack.pop()
    order.append(cur)
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        stack.append(next)

size_down = [0] * (N+1)  # 1-indexed
dp_down = [1] * (N+1)  # 葉側の組み合わせ
for v in order[::-1]:
    dp_down[v] *= fact[size_down[v]]
    dp_down[v] %= MOD
    p = parent[v]
    s = size_down[v] + 1
    size_down[p] += s
    dp_down[p] *= fact_inv[s] * dp_down[v]
    dp_down[p] %= MOD

size_up = [N-x-1 for x in size_down]  # 自分含めない
dp_up = [1] * (N+1)  # 根側の組み合わせ
for v in order[1:]:
    p = parent[v]
    x = dp_down[p]
    x *= dp_up[p]
    x *= fact_inv[size_down[p]]
    x *= fact[size_down[v] + 1]
    x *= pow(dp_down[v], MOD-2, MOD)
    x %= MOD
    x *= fact[size_up[v]-1]
    x *= fact_inv[size_up[p]]
    dp_up[v] = x % MOD

size_up[1] = 0; dp_up[1] = 1
for xd, xu, sd, su in zip(dp_down[1:], dp_up[1:], size_down[1:], size_up[1:]):
    answer = xd * xu * fact[sd+su] * fact_inv[sd] * fact_inv[su] % MOD
    print(answer % MOD)

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] * N
dat = [zero] * N
rev_data = [zero] * 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(dat[i].num)

if __name__ == "__main__": main()

Submission status: Accepted

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

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0

MOD = 10 ** 9 + 7

F = Factorial(2 * 10 ** 5 + 10, MOD)

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


root = 1

DAG = []
parent = [-1] * (N + 1)
parent[root] = 0
stack = [root]
while stack:
    now_ = stack.pop()
    DAG.append(now_)
    for next_ in G[now_]:
        if parent[next_] == -1:
            stack.append(next_)
            parent[next_] = now_

# print ('parent', parent)

size1 = [1] * (N + 1)
dp1 = [1] * (N + 1)

for i in DAG[::-1]:
    size1[parent[i]] += size1[i]

for i in DAG[::-1]:
    dp1[i] *= F.factorial(size1[i] - 1)
    dp1[i] %= MOD
    dp1[parent[i]] *= (dp1[i] * F.ifactorial(size1[i])) % MOD
    dp1[parent[i]] %= MOD

# print (dp1)
# print (size1)

size2 = [1] * (N + 1)
dp2 = [1] * (N + 1)

for i in DAG[::]:
    for j in G[i]:
        if parent[i] == j:
            continue
        size2[j] = size2[i] + size1[i] - size1[j]  

for i in DAG[1::]:
    x = 1
    x *= dp1[parent[i]]
    x *= F.ifactorial(size1[parent[i]] - 1)
    x *= F.factorial(size1[i])
    x *= pow(dp1[i], MOD - 2, MOD)
    x *= dp2[parent[i]]
    x *= F.ifactorial(size2[parent[i]] - 1)
    x *= F.factorial(size2[i] - 2)
    dp2[i] = x % MOD

# print ('size1', size1)
# print ('size2', size2)
# print ('dp1', dp1)
# print ('dp2', dp2)
# print (G)

fact = F.factorial(N - 1)
for x in range(1, N + 1):
    ans = fact * dp1[x] * F.ifactorial(size1[x] - 1) * dp2[x] * F.ifactorial(size2[x] - 1)
    print (ans % MOD)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

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

factorial = [1]
for i in range(1, N + 1):
    factorial.append(factorial[-1] * i % MOD)

inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

deg = [0] * N
parent = [0] * N
dp = [0] * N
ans = [0] * N
cnt_leaf = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]*pow(N - cnt_leaf[e] - 1,MOD - 2,MOD)%MOD,v)
    
dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    class Rerooting():
        def __init__(self):
            # merge:頂点aにbをマージするときのモノイド
            # adj_bu:ボトムアップ時の調整（a:値,i:頂点）
            # adj_td:トップダウン時の調整（a:値,i:頂点,p:親）
            # （根方向への調整と考えるとわかりやすい）
            # adj_fin:最終調整（a:値,i:頂点）
            def merge(a, b): return a * b % mod
            def adj_bu(a, i): return a * inv[size[i]] % mod
            def adj_td(a, i, p): return a * inv[n-size[i]] % mod
            def adj_fin(a, i): return a * fact[n-1] % mod

            # トポロジカルソートをする
            # T:木の隣接グラフ表現をset化
            # P:親
            # q:キュー
            # order:トポソしたもの
            T = g
            P = [-1]*n
            q = [0]
            ini = 1
            order = []
            while q:
                i = q.pop()
                order.append(i)
                for a in T[i]:
                    if a != P[i]:
                        P[a] = i
                        T[a].remove(i)
                        q.append(a)

            T = [list(i) for i in T]

            # サイズの処理を先に行う
            # size[i]:0を根とする根付き木における、iを根とする部分木の大きさ
            size = [1]*n
            for i in order[1:][::-1]:
                size[P[i]] += size[i]

            # ボトムアップ処理をする
            # ME:マージした値を一時保存
            # DP:DP値、MEを調整したもの
            ME = [ini]*n
            DP = [0]*n
            for i in order[1:][::-1]:
                DP[i] = adj_bu(ME[i], i)
                p = P[i]
                ME[p] = merge(ME[p], DP[i])
            DP[order[0]] = adj_fin(ME[order[0]], order[0])
            TD = [ini]*n

            # トップダウン処理をする
            for i in order:
                # 左からDP（結果はTDに入れている）
                ac = TD[i]
                for j in T[i]:
                    TD[j] = ac
                    ac = merge(ac, DP[j])
                # 右からDP（結果はacに入れている、一度しか使わないのでacで問題ない）
                # 例えばjが1から4だったとすると、TD[j]にはそれぞれ
                # TD[1] = 無、TD[2] = DP[1]、TD[3] = DP[1]*DP[2]、TD[4] = DP[1]*DP[2]*DP[3]
                # が入っている。
                # ここでacにそれぞれ無、DP[4]、DP[3]*DP[4]、DP[2]*DP[3]*DP[4]を
                # 順に入れていくといい感じになることがわかる。
                # 最後にTDに欠けているのは本来の根方向への補正なので、
                # jの部分木以外のサイズの逆数を掛けてやる必要がある。
                # これで、TDには根方向、MEにはそれ以外の方向のDP値が入っている状態になっているので
                # あとは掛けてやるだけでよい。
                ac = ini
                for j in T[i][::-1]:
                    TD[j] = adj_td(merge(TD[j], ac), j, i)
                    ac = merge(ac, DP[j])
                    DP[j] = adj_fin(merge(ME[j], TD[j]), j)
            for i in DP:
                print(i)
    Rerooting()


main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline


class Tree:
    def __init__(self, crdinal, adjgrph, root):
        self.n = crdinal
        self.g = adjgrph
        self.root = root
        self.parent = [-1]*self.n
        self.depth = [-1]*self.n
        self.subsize = [1]*self.n
        self.dp = [1]*self.n  # 0 : additive, 1 : multiplicative

        s = [self.root]
        while s:
            v = s.pop()
            if self.depth[v] == -1:
                if v == self.root:
                    self.depth[v] = 0
                else:
                    self.depth[v] = self.depth[self.parent[v]] + 1
                    s.append(v)
                for w in self.g[v]:
                    if self.depth[w] == -1:
                        self.parent[w] = v
                        s.append(w)
            else:
                self.subsize[self.parent[v]] += self.subsize[v]
                self.calc(v)

        for i in range(n):
            self.dp[i] *= fact[self.subsize[i]-1]
            self.dp[i] %= mod

    def calc(self, v):
        # The following formula is calculated by bottom-up:
        self.dp[self.parent[v]] *= fact[self.subsize[v]-1] * self.dp[v] * ifact[self.subsize[v]]
        self.dp[self.parent[v]] %= mod
        return None

    def wanted(self):
        # Edit the item you want by using self.depth, self.subsize, etc..
        # Default : self.parent
        return self.parent

    def rerooting(self) -> list:
        # Modify below if you want to use rerooting
        ans = [0]*n
        ans[self.root] = self.dp[self.root]

        FromParent = [0]*n

        s = [self.root]
        while s:
            v = s.pop()
            cum = 1

            for w in self.g[v]:
                if w != self.parent[v]:
                    cum *= self.dp[w]*ifact[self.subsize[w]]
                    cum %= mod
                    s.append(w)
                else:
                    cum *= FromParent[v]*ifact[n-self.subsize[v]]
                    cum %= mod

            # calculate the sub-result for parent's subtree when you see the child as root.
            # get the answer for each child.
            for i, w in enumerate(self.g[v]):
                if w != self.parent[v]:
                    FromParent[w] = fact[n-self.subsize[w]-1] * cum * inv(self.dp[w] * ifact[self.subsize[w]] , mod)
                    ans[w] = fact[n-1] * (FromParent[w] * ifact[n-self.subsize[w]]) * (self.dp[w] * ifact[self.subsize[w]-1])
                    ans[w] %= mod
        return ans


mod = 10**9+7


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


max_num = 2*10**5+1
fact = [0 for _ in range(max_num)]
ifact = [0 for _ in range(max_num)]

fact[0] = fact[1] = 1
ifact[0] = ifact[1] = 1

for i in range(2, max_num):
    fact[i] = fact[i-1] * i % mod

ifact[max_num-1] = inv(fact[max_num-1], mod)

for i in range(2, max_num):
    ifact[max_num-i] = (ifact[max_num-i+1] * (max_num-i+1)) % mod


n = int(input())
g = [[] for _ in range(n)]

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

T1 = Tree(n, g, 0)

for x in T1.rerooting():
    print(x)

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    def Reroot():
        # merge:頂点aにbをマージするときのモノイド
        # adj_bu:ボトムアップ時の調整（a:値,i:頂点）
        # adj_td:トップダウン時の調整（a:値,i:頂点,p:親）
        # （根方向への調整と考えるとわかりやすい）
        # adj_fin:最終調整（a:値,i:頂点）
        def merge(a, b): return a * b % mod
        def adj_bu(a, i): return a * inv[size[i]] % mod
        def adj_td(a, i, p): return a * inv[n-size[i]] % mod
        def adj_fin(a, i): return a * fact[n-1] % mod

        # トポロジカルソートをする
        # T:木の隣接グラフ表現をset化
        # P:親
        # q:キュー
        # order:トポソしたもの
        T = g
        P = [-1]*n
        q = [0]
        ini = 1
        order = []
        while q:
            i = q.pop()
            order.append(i)
            for a in T[i]:
                if a != P[i]:
                    P[a] = i
                    T[a].remove(i)
                    q.append(a)

        T = [list(i) for i in T]

        # サイズの処理を先に行う
        # size[i]:0を根とする根付き木における、iを根とする部分木の大きさ
        size = [1]*n
        for i in order[1:][::-1]:
            size[P[i]] += size[i]

        # ボトムアップ処理をする
        # ME:マージした値を一時保存
        # DP:DP値、MEを調整したもの
        ME = [ini]*n
        DP = [0]*n
        for i in order[1:][::-1]:
            DP[i] = adj_bu(ME[i], i)
            p = P[i]
            ME[p] = merge(ME[p], DP[i])
        DP[order[0]] = adj_fin(ME[order[0]], order[0])
        TD = [ini]*n

        # トップダウン処理をする
        for i in order:
            # 左からDP（結果はTDに入れている）
            ac = TD[i]
            for j in T[i]:
                TD[j] = ac
                ac = merge(ac, DP[j])
            # 右からDP（結果はacに入れている、一度しか使わないのでacで問題ない）
            # 例えばjが1から4だったとすると、TD[j]にはそれぞれ
            # TD[1] = 無、TD[2] = DP[1]、TD[3] = DP[1]*DP[2]、TD[4] = DP[1]*DP[2]*DP[3]
            # が入っている。
            # ここでacにそれぞれ無、DP[4]、DP[3]*DP[4]、DP[2]*DP[3]*DP[4]を
            # 順に入れていくといい感じになることがわかる。
            # 最後にTDに欠けているのは本来の根方向への補正なので、
            # jの部分木以外のサイズの逆数を掛けてやる必要がある。
            # これで、TDには根方向、MEにはそれ以外の方向のDP値が入っている状態になっているので
            # あとは掛けてやるだけでよい。
            ac = ini
            for j in T[i][::-1]:
                TD[j] = adj_td(merge(TD[j], ac), j, i)
                ac = merge(ac, DP[j])
                DP[j] = adj_fin(merge(ME[j], TD[j]), j)
        for i in DP:
            print(i)
    Reroot()


main()

Submission status: Accepted

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    # merge:頂点aにbをマージするときのモノイド
    # adj_bu:ボトムアップ時の調整（a:値,i:頂点）
    # adj_td:トップダウン時の調整（a:値,i:頂点,p:親）
    # （根方向への調整と考えるとわかりやすい）
    # adj_fin:最終調整（a:値,i:頂点）
    def merge(a, b): return a * b % mod
    def adj_bu(a, i): return a * inv[size[i]] % mod
    def adj_td(a, i, p): return a * inv[n-size[i]] % mod
    def adj_fin(a, i): return a * fact[n-1] % mod

    # トポロジカルソートをする
    # T:木の隣接グラフ表現をset化
    # P:親
    # q:キュー
    # order:トポソしたもの
    T = g
    P = [-1]*n
    q = [0]
    ini = 1
    order = []
    while q:
        i = q.pop()
        order.append(i)
        for a in T[i]:
            if a != P[i]:
                P[a] = i
                T[a].remove(i)
                q.append(a)

    T = [list(i) for i in T]

    # サイズの処理を先に行う
    # size[i]:0を根とする根付き木における、iを根とする部分木の大きさ
    size = [1]*n
    for i in order[1:][::-1]:
        size[P[i]] += size[i]

    # ボトムアップ処理をする
    # ME:マージした値を一時保存
    # DP:DP値、MEを調整したもの
    ME = [ini]*n
    DP = [0]*n
    for i in order[1:][::-1]:
        DP[i] = adj_bu(ME[i], i)
        p = P[i]
        ME[p] = merge(ME[p], DP[i])
    DP[order[0]] = adj_fin(ME[order[0]], order[0])
    TD = [ini]*n

    # トップダウン処理をする
    for i in order:
        # 左からDP（結果はTDに入れている）
        ac = TD[i]
        for j in T[i]:
            TD[j] = ac
            ac = merge(ac, DP[j])
        # 右からDP（結果はacに入れている、一度しか使わないのでacで問題ない）
        # 例えばjが1から4だったとすると、TD[j]にはそれぞれ
        # TD[1] = 無、TD[2] = DP[1]、TD[3] = DP[1]*DP[2]、TD[4] = DP[1]*DP[2]*DP[3]
        # が入っている。
        # ここでacにそれぞれ無、DP[4]、DP[3]*DP[4]、DP[2]*DP[3]*DP[4]を
        # 順に入れていくといい感じになることがわかる。
        # 最後にTDに欠けているのは本来の根方向への補正なので、
        # jの部分木以外のサイズの逆数を掛けてやる必要がある。
        # これで、TDには根方向、MEにはそれ以外の方向のDP値が入っている状態になっているので
        # あとは掛けてやるだけでよい。
        ac = ini
        for j in T[i][::-1]:
            TD[j] = adj_td(merge(TD[j], ac), j, i)
            ac = merge(ac, DP[j])
            DP[j] = adj_fin(merge(ME[j], TD[j]), j)
    for i in DP:
        print(i)


main()