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:
def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    g = [[] for _ in [0]*n]
    for _ in range(n-1):
        a, b = map(int, input().split())
        g[a-1].append(b-1)
        g[b-1].append(a-1)

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

    class rerooting():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # 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]
            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)

            # サイズの処理を先に行う
            # 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で問題ない）
                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(g, 1)


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 = [[] for _ in [0]*n]
    for a, b in ab:
        g[a-1].append(b-1)
        g[b-1].append(a-1)

    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)

    # サイズの処理を先に行う
    # 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で問題ない）
        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()

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]
    for a, b in ab:
        g[a-1].add(b-1)
        g[b-1].add(a-1)

    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():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # 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]
            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をリストに変換
            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で問題ない）
                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(g, 1)


main()

Submission status: Accepted

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, n+1):
        fact.append(fact[-1]*i % mod)

    def inv_n(n):
        return pow(n, mod-2, mod)

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

    class rerooting():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # 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_n(size[i]) % mod
            def adj_td(a, i, p): return a * inv_n(n-size[i]) % mod
            def adj_fin(a, i): return a * fact[n-1] % mod

            # トポロジカルソートをする
            # T:木の隣接グラフ表現をset化
            # P:親
            # q:キュー
            # order:トポソしたもの
            T = [set(i) for i in tree]
            P = [-1]*n
            q = [0]
            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をリストに変換
            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で問題ない）
                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(g, 1)


main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 28 22:56:10 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

N = int(input())
#X, Y = map(int,input().split())
#ab = [list(map(int,input().split())) for i in range(N-1)]

fact = [1, 1] # 元テーブル
fact_inv = [1, 1] # 逆元テーブル
tmp_inv = [0, 1] # 逆元テーブル計算用テーブル
for i in range(2, N+1):
    fact.append((fact[-1] * i) % mod)
    tmp_inv.append((-tmp_inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * tmp_inv[-1]) % mod)
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod
#逆元作成
def inv(a,mod):
    return pow(a,mod-2,mod)

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

dp = [1] * (N + 0)
size = [0] * (N + 0)
def dfs(par, v):
    for u in graph[v]:
        if par == u:
            continue
        dfs(v, u)
        size[v] += size[u]
        dp[v] = dp[v] * dp[u] * fact_inv[size[u]] % mod
    dp[v] = dp[v] * fact[size[v]] % mod
    size[v] += 1

ans = [0] * (N + 0)
def reroot(par, val_par, size_par, v):
    ans[v] = val_par * dp[v] * cmb(N-1, size_par, mod) % mod
    for u in graph[v]:
        if par == u:
            continue
        val = ans[v] * inv(dp[u] * cmb(N-1, size[u],mod),mod) % mod
        reroot(v, val, N - size[u], u)

dfs(-1,1)
reroot(-1,1,0,1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 28 22:56:10 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

N = int(input())
#X, Y = map(int,input().split())
#ab = [list(map(int,input().split())) for i in range(N-1)]

fact = [1, 1] # 元テーブル
fact_inv = [1, 1] # 逆元テーブル
tmp_inv = [0, 1] # 逆元テーブル計算用テーブル
for i in range(2, N+1):
    fact.append((fact[-1] * i) % mod)
    tmp_inv.append((-tmp_inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * tmp_inv[-1]) % mod)
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod
#逆元作成
def inv(a,mod):
    return pow(a,mod-2,mod)

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

dp = [1] * (N + 0)
size = [0] * (N + 0)
def dfs(par, v):
    for u in graph[v]:
        if par == u:
            continue
        dfs(v, u)
        size[v] += size[u]
        dp[v] = dp[v] * dp[u] * fact_inv[size[u]] % mod
    dp[v] = dp[v] * fact[size[v]] % mod
    size[v] += 1

ans = [0] * (N + 0)
def reroot(par, val_par, size_par, v):
    ans[v] = val_par * dp[v] * cmb(N-1, size_par, mod) % mod
    for u in graph[v]:
        if par == u:
            continue
        val = ans[v] * inv(dp[u] * cmb(N-1, size[u],mod),mod) % mod
        reroot(v, val, N - size[u], u)

dfs(-1,1)
reroot(-1,1,0,1)
for i in range(N):
    print(ans[i])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 28 22:56:10 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

N = int(input())
#X, Y = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]

fact = [1, 1] # 元テーブル
fact_inv = [1, 1] # 逆元テーブル
tmp_inv = [0, 1] # 逆元テーブル計算用テーブル
for i in range(2, N+1):
    fact.append((fact[-1] * i) % mod)
    tmp_inv.append((-tmp_inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * tmp_inv[-1]) % mod)
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod
#逆元作成
def inv(a,mod):
    return pow(a,mod-2,mod)

graph = [[] for _ in range(N+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)
    
root = 1
parent = [0] * (N + 1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)

size_d = [0] * (N + 1)
dp_d = [1] * (N + 1)
for v in order[::-1]:
    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 - x - 1 for x in size_d]
dp_u = [1] * (N + 1)
for v in order[1:]:
    p = parent[v]
    x = dp_d[p] * inv(dp_d[v],mod)
    x *= fact_inv[size_d[p]] * fact[size_d[v] + 1]
    x *= fact[size_u[v] - 1] * fact_inv[size_u[p]]
    x *= dp_u[p]
    dp_u[v] = x % mod

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

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()

class modfact(object):
    def __init__(self,n):
        fact=[1]*(n+1); invfact=[1]*(n+1)
        for i in range(1,n+1): fact[i]=i*fact[i-1]%MOD
        invfact[n]=pow(fact[n],MOD-2,MOD)
        for i in range(n-1,-1,-1): invfact[i]=invfact[i+1]*(i+1)%MOD
        self.__fact=fact; self.__invfact=invfact

    def inv(self,n):
        assert(n>0)
        return self.__fact[n-1]*self.__invfact[n]%MOD

    def fact(self,n):
        return self.__fact[n]

    def invfact(self,n):
        return self.__invfact[n]

    def comb(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[k]*self.__invfact[n-k]%MOD

    def perm(self,n,k):
        if(k<0 or n<k): return 0
        return self.__fact[n]*self.__invfact[n-k]%MOD

def resolve():
    n = int(input())
    mf = modfact(n)
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1
        E[u].append(v)
        E[v].append(u)

    # dp on Tree
    dp = [1] * n
    size = [1] * n
    stack = [(~0, -1), (0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            # v を確定させる
            v = ~v
            for nv in E[v]:
                if nv == p:
                    continue
                size[v] += size[nv]
                dp[v] *= dp[nv] * mf.invfact(size[nv])
                dp[v] %= MOD
            dp[v] *= mf.fact(size[v] - 1)
            dp[v] %= MOD


    def rerooting(v, p):
        if p == -1:
            return

        # dp[p] を v-rooted にする
        dp[p] *= mf.fact(size[p] - size[v] - 1) * mf.invfact(size[p] - 1) * mf.fact(size[v]) * pow(dp[v], MOD-2, MOD)
        dp[p] %= MOD
        size[p] -= size[v]

        # dp[v] を v-rooted にする
        size[v] += size[p]
        dp[v] *= mf.fact(size[v] - 1) * mf.invfact(size[v] - size[p] - 1) * dp[p] * mf.invfact(size[p])
        dp[v] %= MOD

    ans = [None] * n
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            ans[v] = dp[v]
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(*ans, sep = '\n')
resolve()

Submission status: Accepted

Solution code:
# 全方位DP
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**6)
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 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(num, par=-1):
    res = 1
    for node in edges[num]:
        if node == par:
            continue
        else:
            res += dfs1(node, num)
    res %= MOD
    size[num] = 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)]
inv_1 = fact.fact_inv(fact.fact[n-1])
def dfs3(num, par=-1):
    if par != -1:
        res = dp[num] * fact.fact_inv(fact.fact[size[num] - 1]) * \
            fact.fact[n-1] * ans[par] * inv_1 * \
            fact.fact[n-size[num]-1] * fact.fact[size[num]] * \
            fact.fact_inv(dp[num]) * \
            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:]))))

Submission status: Accepted

Solution code:
n=int(input())
F = n+5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

#invnum[0] cant be used
invnum=[fact[i-1]*inv[i] for i in range(n)]

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

stack=[0]
order=[0]
parent=[-1]*n
comb=[0]*n
size=[1]*n

# BFS order
while stack:
    node = stack.pop()
    for neib in graph[node]:
        if neib!=parent[node]:
            stack.append(neib)
            order.append(neib)
            parent[neib]=node

#calc size including self
for node in order[n-1:0:-1]:
    size[parent[node]]+=size[node]

#calc root comb
comb[0]=fact[n-1]
for node in range(1,n):
    comb[0]*=invnum[size[node]]
    comb[0]%=mod

#calc all comb
for node in order[1:]:
    comb[node]=comb[parent[node]]*size[node]*invnum[n-size[node]]%mod

print(*comb,sep="\n")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 * 2 + 10)

MOD = 10 ** 9 + 7
inv = [None, 1]
for i in range(2, 10 ** 5 * 2 + 1):
    inv.append(MOD - MOD // i * inv[MOD % i] % MOD)

fact = [1]
ifact = [1]
for i in range(1, 10 ** 5 * 2 + 1):
    fact.append((i * fact[-1]) % MOD)
    ifact.append((inv[i] * ifact[-1]) % MOD)


class Node:
    def __init__(self, ind):
        self.ind = ind
        self.val = 1
        self.ndesc = 1
        self.neighs = []

    def calc(self, fro):
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.calc(self.ind)
            self.val = self.val * neigh.val * ifact[neigh.ndesc] % MOD
            self.ndesc += neigh.ndesc
        self.val = self.val * fact[self.ndesc - 1] % MOD

    def comp(self, fro, carry):
        self.val = carry * self.ndesc * inv[max(1, N - self.ndesc)] % MOD
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.comp(self.ind, self.val)


N = int(input())
nodes = [Node(i) for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].neighs.append(nodes[b - 1])
    nodes[b - 1].neighs.append(nodes[a - 1])
nodes[0].calc(0)
nodes[0].comp(0, (nodes[0].val * inv[N]) % MOD)
for i in range(N):
    print(nodes[i].val)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
inv = [None, 1]
for i in range(2, 10 ** 5 * 2 + 1):
    inv.append(MOD - MOD // i * inv[MOD % i] % MOD)

fact = [1]
ifact = [1]
for i in range(1, 10 ** 5 * 2 + 1):
    fact.append((i * fact[-1]) % MOD)
    ifact.append((inv[i] * ifact[-1]) % MOD)


class Node:
    def __init__(self, ind):
        self.ind = ind
        self.val = 1
        self.ndesc = 1
        self.neighs = []


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

stack = [(-1, nodes[0])]
for i in range(N):
    fro, node = stack[i]
    for neigh in node.neighs:
        if neigh.ind == fro:
            continue
        stack.append((node.ind, neigh))

for i in range(N - 1, -1, -1):
    fro, node = stack[i]
    node.val = node.val * fact[node.ndesc - 1] % MOD
    if fro == -1:
        continue
    nodes[fro].ndesc += node.ndesc
    nodes[fro].val = nodes[fro].val * node.val * ifact[node.ndesc] % MOD

stack = [(-1, node, nodes[0].val * inv[N] % MOD)]
for i in range(N):
    fro, node, val = stack[i]
    node.val = val * node.ndesc * inv[max(1, N - node.ndesc)] % MOD
    for neigh in node.neighs:
        if neigh.ind == fro:
            continue
        stack.append((node.ind, neigh, node.val))

for i in range(N):
    print(nodes[i].val)

Submission status: Accepted

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
mod = 10 ** 9 + 7

MAX = n

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

inv = [1] * (MAX + 1)
for i in range(2, MAX + 1):
    inv[i] = inv[mod % i] * (mod - mod // i) % mod

fact_inv = [1] * (MAX + 1)
for i in range(1, MAX + 1):
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


adj = [[] for _ in range(n + 1)]
for a, b in ab:
    adj[a].append(b)
    adj[b].append(a)

root = 1
stack = [root]
par = [0] * (n + 1)
order = []
while stack:
    u = stack.pop()
    order.append(u)
    for v in adj[u]:
        if v == par[u]:
            continue
        par[v] = u
        stack.append(v)

size_d = [0] * (n + 1)
dp_d = [1] * (n + 1)
for v in order[::-1]:
    dp_d[v] *= fact[size_d[v]]
    dp_d[v] %= mod
    
    s = size_d[v] + 1
    p = par[v]
    size_d[p] += s
    dp_d[p] *= fact_inv[s] * dp_d[v]
    dp_d[p] %= mod

size_u = [n - 2 - e for e in size_d]
dp_u = [1] * (n + 1)
for v in order[1:]:
    p = par[v]
    x = dp_d[p]
    x *= fact_inv[size_d[p]]
    x *= fact[size_d[v] + 1]
    x *= pow(dp_d[v], mod - 2, mod)
    x *= fact[size_u[v]]
    x *= fact_inv[size_u[p] + 1]
    x *= dp_u[p]
    dp_u[v] = x % mod

for eu, su, ed, sd in zip(dp_u[1:], size_u[1:], dp_d[1:], size_d[1:]):
    su += 1
    ans = eu * ed * fact[su + sd] * fact_inv[su] * fact_inv[sd] % mod
    print(ans)

Submission status: Accepted

Solution code:
class ReRooting(object):
    """ 全方位木DP (オリジナル)"""
    def processing(self, in_:list, v:int):
        """ 単項演算(加工) """
        cnt = in_[0] * factinv[in_[1]] % MOD
        size = in_[1]
        return [cnt, size]
    
    def merge(self, in1:list, in2:list):
        """ 二項演算(マージ) """
        cnt = in1[0] * in2[0] % MOD
        size = in1[1] + in2[1]
        return [cnt, size]

    def adjustment(self, in_:list, v:int):
        """ 単項演算(調整) """
        cnt = in_[0] * fact[in_[1]] % MOD
        size = in_[1] + 1
        return [cnt, size]
    
    def solve(self):
        """ 結果を返す """
        return [cnt for cnt,_ in self.calc()]

    def __init__(self, V:int, e:list):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
    
    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self, e:list):
        """ Bottom-Up DP """
        accBU = [e for _ in range(self.V)]
        resBU = [None] * self.V
        for v in reversed(self.order):
            for c in self.edge[v]:
                accBU[v] = self.merge(accBU[v], self.processing(resBU[c], c))
            resBU[v] = self.adjustment(accBU[v], v)
        return accBU, resBU
    
    def top_down(self, resBU:list, e:list):
        """ Top-Down DP """
        accTD = [e for _ in range(self.V)]
        resTD = [e for _ in range(self.V)]

        for p in self.order:
            ac = self.processing(resTD[p], p)
            for v in self.edge[p]:
                accTD[v] = ac[:]
                ac = self.merge(ac, self.processing(resBU[v], v))
            
            ac = e
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                resTD[v] = self.adjustment(accTD[v], v)
                ac = self.merge(ac, self.processing(resBU[v], v))
        return resTD
    
    def calc(self):
        """ 開始条件: 木を構築済み """
        self.topological_sort()
        accBU, resBU = self.bottom_up(self.e)
        resTD = self.top_down(resBU, self.e)

        res = [None] * self.V
        for v in range(self.V):
            res[v] = self.processing(resTD[v], v)
            res[v] = self.merge(accBU[v], res[v])
            res[v] = self.adjustment(res[v], v)
        return res

#########################################################################################
import sys
input = sys.stdin.readline

N = int(input())
MOD = 10 ** 9 + 7

fact = [1] * (N + 1) # fact[n]: n!
factinv = [1] * (N + 1) # n!の逆元
for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % MOD
factinv[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(N - 1, -1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % MOD
 
def main():
    RR = ReRooting(N, [1, 0])
    for _ in range(N - 1):
        a, b = map(int, input().split())
        RR.add_edge(a - 1, b- 1)
    print(*RR.solve(), sep="\n")

 
if __name__ == "__main__":
    main()