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
sys.setrecursionlimit(10**6)
MOD = 10**9 + 7

m = 2*10**5+5
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


COMBinitialize(m)


def COMB(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


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

    def __iadd__(self, other):
        self.dp *= other.dp
        self.dp *= COMB(self.t+other.t, self.t)
        self.t += other.t
        return self

    def __sub__(self, other):
        res = DP(self.dp, self.t)
        res.t -= other.t
        res.dp /= COMB(res.t+other.t, res.t)
        res.dp /= other.dp
        return res

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


def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    dp = [DP() for _ in range(N+5)]

    def dfs(v, p=-1):
        for u in edge[v]:
            if u == p:
                continue
            dfs(u, v)
            dp[v] += dp[u].add_root()

    def bfs(v, p=-1):
        for u in edge[v]:
            if u == p:
                continue
            d = dp[v] - dp[u].add_root()
            dp[u] += d.add_root()
            bfs(u, v)

    dfs(0)
    bfs(0)
    for i in range(N):
        print(dp[i].add_root().dp)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

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

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

class ReRooting:
    """
    0-indexed
    """
    def __init__(self, size, root=0, identDp=1, identCum=1):
        """
        identDp: 木DP用 lift(a, identDp) = a
        identCum: 累積用 merge(a, identCum) = a
        """
        self.size = size
        self.edges = [[] for _ in range(self.size + 1)]
        self.root = root
        self.identDp = identDp
        self.identCum = identCum

    def addEdge(self, fr, to):
        self.edges[fr].append(to)
        self.edges[to].append(fr)

    # 根を固定したときの木DP(貰うDP)
    def lift(self, top, bottom):
        newSize = top[1] + bottom[1] + 1
        dp = top[0] * bottom[0] * comb.ncr(newSize, bottom[1] + 1)
        return (dp % MOD, newSize)

    # 親の左右の累積から子を根としたときの値を求める
    def merge(self, left, right):
        newSize = left[1] + right[1]
        dp = left[0] * right[0] * comb.ncr(newSize, right[1])
        return (dp % MOD, newSize)

    def sol(self):
        N = self.size
        edges = self.edges

        st = [self.root]
        parent = [-1] * (N + 1)
        child = [[] for _ in range(N + 1)]
        order = []
        while st:
            v = st.pop()
            order.append(v)
            for to in edges[v]:
                if parent[v] == to:
                    continue
                parent[to] = v
                child[v].append(to)
                st.append(to)

        dp = [self.identDp] * (N + 1)
        left = [self.identCum] * (N + 1)
        right = [self.identCum] * (N + 1)
        for v in order[::-1]:  # 貰うDPしつつ，累積をとる
            tmp = self.identCum
            for ch in child[v]:
                left[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            tmp = self.identCum
            for ch in reversed(child[v]):
                right[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            dp[v] = tmp

        fromParent = [self.identDp] * (N + 1)
        for v in order:
            if v == self.root:
                continue
            fromParent[v] = self.lift(self.merge(left[v], right[v]), fromParent[parent[v]])
            dp[v] = self.lift(dp[v], fromParent[v])  # 最後に親からの貰うDP

        return dp[:N]

N = int(input())
MOD = 10**9 + 7
tree = ReRooting(N, 0, (1, -1), (1, 0))
comb = Combination(N + 100)

for _ in range(N - 1):
    fr, to = map(int, input().split())
    tree.addEdge(fr - 1, to - 1)

ans = tree.sol()
print(*[dp for dp, _ in ans[:N]], sep='\n')

Submission status: Accepted

Solution code:
n = int(input())

mod = 10**9+7 #出力の制限
N = 10**6
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 )

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)

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

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

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

        dp[u] *= g2[c[u]-1]
        dp[u] *= g1[c[v]-1]
        dp[u] *= temp
        dp[u] *= g2[c[v]-c[u]]
        dp[u] %= mod
        c[u] += c[v]-c[u]

for i in range(n):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
mod = 7 + 10 ** 9
from collections import deque

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

def dfs1(i, pre, Edge, Dist, Son, fact, revfact):
    under = 0
    for ne in Edge[i]:
        if ne != pre:
            sonNum = dfs1(ne, i, Edge, Dist, Son, fact, revfact)
            under += sonNum
            Dist[i] *= (comb(under, sonNum, fact, revfact, mod) * Dist[ne]) % mod
            Dist[i] %= mod
    Son[i] = under
    return under + 1 

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)
    fact = [1] * (N + 1)
    for i in range(1, N + 1): fact[i] = (fact[i-1] * i) % mod
    revfact = [1] * (N + 1)
    revfact[N] = pow(fact[N], mod - 2, mod)
    for i in reversed(range(1, N)): revfact[i] = ((i + 1) * revfact[i+1]) % mod

    Dist = [1] * N
    Son = [0] * N
    dfs1(0, 0, Edge, Dist, Son, fact, revfact)
    q = deque()
    for ne in Edge[0]:
        q.append((ne, 0))
    while q:
        ne, pre = q.pop()
        upper = (Dist[pre] * pow(comb(N - 1, Son[ne] + 1 , fact, revfact, mod), mod - 2, mod)) % mod
        Dist[ne] = (upper * comb(N - 1, N - 1- Son[ne], fact, revfact, mod)) % mod
        for nextEdge in Edge[ne]:
            if nextEdge != pre: q.append((nextEdge, ne))
    print("\n".join(map(str, Dist)))

    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    if S[2]==S[3] and S[4]==S[5]:
        print("Yes")
    else:
        print("No")
    return

def examB():
    X = I()
    ans = 0
    ans += (X//500) * 1000
    X %= 500
    ans += (X//5) * 5
    print(ans)
    return

def examC():
    K, N = LI()
    A = LI()
    L = [0]*N
    L[0] = K-A[-1] + A[0]
    for i in range(1,N):
        L[i] = A[i]-A[i-1]
    ans = sum(L) - max(L)
    #print(L)
    print(ans)
    return

def examD():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N, X, Y = LI()
    V = [[]for _ in range(N)]
    for i in range(N-1):
        V[i].append(i+1)
        V[i+1].append(i)
    V[X-1].append(Y-1)
    V[Y-1].append(X-1)
    #print(V)
    ans = [0]*(N-1)
    for i in range(N):
        L = bfs(N,i,V)
        for l in L:
            if l==0:
                continue
            ans[l-1] += 1
    for v in ans:
        print(v//2)
    return

def examE():
    X, Y, A, B, C = LI()
    P = LI()
    Q = LI()
    R = LI()
    P.sort(reverse=True)
    Q.sort(reverse=True)
    R.sort(reverse=True)
    cnt = sum(P[:X]) + sum(Q[:Y])
    #print(cnt)
    X -= 1; Y -= 1
    for c in range(C):
        if X>=0 and Y>=0:
            if P[X] <= Q[Y]:
                if P[X] >= R[c]:
                    break
                cnt += (R[c] - P[X])
                X -= 1
            else:
                if Q[Y] >= R[c]:
                    break
                cnt += (R[c] - Q[Y])
                Y -= 1
        elif X>=0:
            if P[X] >= R[c]:
                break
            cnt += (R[c] - P[X])
            X -= 1
        elif Y>=0:
            if Q[Y] >= R[c]:
                break
            cnt += (R[c] - Q[Y])
            Y -= 1
    ans = cnt
    print(ans)
    return

def examF():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r, mod):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

    N = I()
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    C = combination(N, mod)

    A = [0]*N
    children = [-1] * N
    ans = [0]*N

    # 子の数のカウント
    def dfs(n, s, edges):
        size = 1
        nowchild = []
        cur = 1
        children[s] = 0
        for i in edges[s]:
            if children[i] != -1:
                continue
            ns, nc = dfs(n, i, edges)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= mod
        children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= C.comb(rest, k, mod)
            rest -= k
            cur %= mod
        A[s] = cur
        return size, cur

    def dfs2(s,p):
        #print(children, A)
        rep = 1
        rest = N - 1
        for to in V[s]:
            rep *= A[to]
            rep %= mod
        for to in V[s]:
            rep *= C.comb(rest, children[to], mod)
            rest -= children[to]
            rep %= mod
        ans[s] = rep

        n = len(V[s])
        L = [0]*n; R = [0]*n
        L2 = [0]*n; R2 = [0]*n

        for i,ne in enumerate(V[s]):
            L[i] = R[i] = A[ne] * C.inv[children[ne]]
            L2[i] = R2[i] = children[ne]
        for i in range(1,n):
            L[i] *= L[i-1]
            L[i] %= mod
            L2[i] += L2[i-1]
        for i in range(1,n-1)[::-1]:
            R[i] *= R[i+1]
            R[i] %= mod
            R2[i] += R2[i+1]
        for i,ne in enumerate(V[s]):
            if ne==p:
                continue
            A[s] = 1
            children[s] = 1
            if i > 0:
                A[s] *= L[i - 1]
                A[s] %= mod
                children[s] += L2[i - 1]
            if i + 1 < n:
                A[s] *= R[i + 1]
                A[s] %= mod
                children[s] += R2[i + 1]
            A[s] *= C.fac[N-children[ne]-1]
            A[s] %= mod
            #print(A[s],s,L,R)
            dfs2(ne, s)
        return

    dfs(N, 0, V)
    dfs2(0,-1)
    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    examF()

"""

"""

Submission status: Accepted

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

def abc():
    global qqq
    for i in range(len(ppp)-1,0,-1):
        qqq=qqq*cmb(ppp[i],ppp[i-1])%mod
    return qqq

mod=10**9+7
MAX=2*10**5+100
g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
data=[[] for i in range(N+1)]
for A,B in AB:
    data[A].append(B)
    data[B].append(A)
parent=[0]*(N+1)
flag=[0]*(N+1)
child=[0]*(N+1)
parent[1]=-1
flag[1]=1
que=[1]
ddd=deque([])
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                h.append(v)
                parent[v]=u
                child[u]+=1
        if child[u]==0:
            ddd.append(u)
    que=h
#sizeは、子の数
size=[0]*(N+1)
#lstは、書く順番の総数
lst=[0]*(N+1)
while ddd:
    u=ddd.pop()
    size[u]=1
    qqq=1
    ppp=[]
    for v in data[u]:
        if v==parent[u]:
            child[v]-=1
            if child[v]==0:
                ddd.appendleft(v)
            continue
        else:
            size[u]+=size[v]
            if ppp:
                ppp.append(size[v]+ppp[-1])
            else:
                ppp.append(size[v])
            qqq=qqq*lst[v]%mod
    lst[u]=abc()
que=deque(data[1][:])
#iを根としたときの答え
ans=[0]*(N+1)
#lslsは親方向の場合の数
lsls=[0]*(N+1)
ans[1]=lst[1]
lsls[1]=1
while que:
    #uに対する場合の数を求める
    u=que.pop()
    par=parent[u]
    ppp=N-size[par]
    num=lst[u]*cmb(size[par]-1,size[u])
    qqq=lst[par]*pow(num,mod-2,mod)%mod
    qqq=qqq*lsls[par]*cmb(ppp+size[par]-size[u]-1,ppp)%mod
    lsls[u]=qqq
    ppp=N-size[u]
    qqq=qqq*cmb(N-1,size[u]-1)*lst[u]%mod
    ans[u]=qqq
    for v in data[u]:
        if v==par:
            continue
        else:
            que.appendleft(v)
for i in range(1,N+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(2*10**5+100)

MAX = 2*10**5+100
MOD = 10**9+7
fact = [0]*MAX #fact[i]: i!
inv = [0]*MAX #inv[i]: iの逆元
finv = [0]*MAX #finv[i]: i!の逆元
fact[0] = 1
fact[1] = 1
finv[0] = 1
finv[1] = 1
inv[1] = 1
    
for i in range(2, MAX):
    fact[i] = fact[i-1]*i%MOD
    inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
    finv[i] = finv[i-1]*inv[i]%MOD

def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD

def dfs1(v, pv):
    res = 1
    M = 0
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        num, res2 = dfs1(nv, v)
        res *= finv[num]*res2
        res %= MOD
        M += num
    
    res *= fact[M]
    res %= MOD
    st[v] = res
    chi[v] = M+1
    
    return M+1, res
    
def dfs2(v, pv):
    res = rt[pv]*fact[chi[v]]*fact[N-chi[v]-1]*pow(st[v], MOD-2, MOD)
    res *= finv[N-chi[v]]
    res %= MOD
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        res *= finv[chi[nv]]*st[nv]
        res %= MOD
    
    rt[v] = res
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        dfs2(nv, v)
    
N = int(input())
G = [[] for _ in range(N)]

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

st = [-1]*N
rt = [-1]*N
chi = [-1]*N
dfs1(0, -1)
rt[0] = st[0]

for nv in G[0]:
    dfs2(nv, 0)

for rt_i in rt:
    print(rt_i)

Submission status: Accepted

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

MAX = 2*10**5+100
fact = [0]*MAX
inv = [0]*MAX
finv = [0]*MAX
MOD = 10**9+7
 
def C_init():
    fact[0] = 1
    fact[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    
    for i in range(2, MAX):
        fact[i] = fact[i-1]*i%MOD
        inv[i] = MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i] = finv[i-1]*inv[i]%MOD
 
def C(n, r):
    if n<r:
        return 0
    if n<0 or r<0:
        return 0
    return fact[n]*(finv[r]*finv[n-r]%MOD)%MOD
    
def dfs1(v, pv):
    nums = []
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        num, chi_res = dfs1(nv, v)
        nums.append(num)
        res *= chi_res
        res %= MOD
    
    M = sum(nums)
    A1[v] = M+1
    
    for num in nums:
        res *= C(M, num)
        res %= MOD
        M -= num
    
    A2[v] = res
    
    return A1[v], A2[v]
    
def dfs2(v, pv):
    res = A3[pv]*pow(C(N-1, A1[v])*A2[v], MOD-2, MOD)%MOD
    M = N-1
    res *= C(M, N-A1[v])
    M -= N-A1[v]
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        res *= A2[nv]
        res *= C(M, A1[nv])
        M -= A1[nv]
        res %= MOD
    
    A3[v] = res
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        dfs2(nv, v)
    
N = int(input())
G = [[] for _ in range(N)]

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

C_init()
A1 = [-1]*N
A2 = [-1]*N
A3 = [-1]*N
dfs1(0, -1)
A3[0] = A2[0]

for nv in G[0]:
    dfs2(nv, 0)

for A3i in A3:
    print(A3i)

Submission status: Accepted

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

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

mod = 10 ** 9 + 7

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

inv = [pow(fac[-1], mod - 2, mod)]
for i in range(N, 0, -1) :
  inv.append(inv[-1] * i % mod)
inv = inv[::-1]

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

pattern = [1] * N
subtree = [0] * N

# DFS
stack = [(0, -1, 0)]
while stack :
  cur, pre, op = stack.pop()
  
  if op == 0 :
    stack.append((cur, pre, 1))
    for nex in vec[cur] :
      if nex == pre : continue
      stack.append((nex, cur, 0))
  else :
    for nex in vec[cur] :
      pattern[cur] *= pattern[nex] * comb(subtree[cur] + subtree[nex], subtree[nex]) % mod
      pattern[cur] %= mod
      subtree[cur] += subtree[nex]
    subtree[cur] += 1

# BFS
queue = [(0, -1)]
while queue :
  cur, pre = queue.pop()
  for nex in vec[cur] :
    if nex == pre : continue
    pattern[nex] = pattern[cur] * subtree[nex] * inv[N - subtree[nex]] * fac[N - subtree[nex] - 1] % mod
    queue.append((nex, cur))
  
for i in range(N) :
  print(pattern[i])

Submission status: Accepted

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

graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

parents = [-1] * n
children = [[] for _ in range(n)]
flags = [True] * n; flags[0] = False
stack = [0]
orders = []

while stack:
    index = stack.pop()
    orders.append(index)
    for child in graph[index]:
        if flags[child]:
            parents[child] = index
            children[index].append(child)
            flags[child] = False
            stack.append(child)

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

size = [1] * n
dp = [1] * n
for parent in orders[::-1]:
    for child in children[parent]:
        size[parent] += size[child]
        dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
    dp[parent] = dp[parent] * fac[size[parent]-1] % mod

size2 = [n-i+1 for i in size]
dp2 = [1] * n
for parent in orders[1:]:
    child = parents[parent]
    dp2[parent] = dp2[parent] * fac[size2[parent]-2] * dp[child] * dp2[child] * fac[size[parent]] * ifac[size2[child]-1] * ifac[size[child]-1] * pow(dp[parent], mod-2, mod) % mod
    
for i in range(n):
    print(fac[n-1] * ifac[size[i]-1] * ifac[size2[i]-1] * dp[i] * dp2[i] % mod)

Submission status: Accepted

Solution code:
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()



sys.setrecursionlimit(200005)


def main():
    N = iRaw()
    G = [[] for _ in range(N)]
    dp = [0]*N
    sizs = [0]*N
    CONV = CONV_TBL(N+1)

    for _ in range(N-1):
        a,b = isRaw()
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    
    def dfs(cur, pre):
        val = 1
        siz = 0
        for v in G[cur]:
            if v == pre:
                continue
            dfs(v, cur)
            siz += sizs[v]
            val = val * dp[v] * CONV.ncr(siz, sizs[v]) % DIV
        dp[cur] = val
        sizs[cur] = siz + 1
    
    def reroot(cur,pre):
        for v in G[cur]:
            if v == pre:
                continue
            val = dp[cur] * sizs[v]%DIV
            #val = val * CONV.fac[sizs[v]] * CONV.finv[sizs[v]-1]%DIV
            res = sizs[0]-sizs[v]
            dp[v] = val * CONV.finv[res] * CONV.fac[res-1] %DIV
            reroot(v,cur)
    
    dfs(0,-1)
    reroot(0,-1)
    return "\n".join([str(d) for d in dp])

if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)

    def rerooting(self, func, merge, ti, ei):
        dp = [ti for _ in range(self.n)]
        lt = [ei for _ in range(self.n)]
        rt = [ei for _ in range(self.n)]
        inv = [ei for _ in range(self.n)]
        self.setroot(0)
        for node in self.order[::-1]:
            tmp = ti
            for adj in self.tree[node]:
                if self.parent[adj] == node:
                    lt[adj] = tmp
                    tmp = func(tmp, dp[adj])
            tmp = ti
            for adj in self.tree[node][::-1]:
                if self.parent[adj] == node:
                    rt[adj] = tmp
                    tmp = func(tmp, dp[adj])
            dp[node] = tmp
        for node in self.order:
            if node == 0:
                continue
            merged = merge(lt[node], rt[node])
            par = self.parent[node]
            inv[node] = func(merged, inv[par])
            dp[node] = func(dp[node], inv[node])
        return dp

class Factorial():
    def __init__(self, n, mod):
        self.mod = mod
        self.factorial = [0 for _ in range(n + 1)]
        self.inv = [0 for _ in range(n + 1)]
        self.factorial[0] = 1
        self.inv[0] = 1
        for i in range(n):
            self.factorial[i + 1] = self.factorial[i] * (i + 1) % mod
        self.inv[n] = pow(self.factorial[n], mod - 2, mod)
        for i in range(n)[::-1]:
            self.inv[i] = self.inv[i + 1] * (i + 1) % mod

    def fact(self, m):
        return self.factorial[m]

    def invfact(self, m):
        return self.inv[m]

import sys
input = sys.stdin.readline

MOD = 1000000007

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N, E)
F = Factorial(N + 1, MOD)

def func(node, adj):
    size = node[1] + adj[1]
    count = node[0] * adj[0] * F.invfact(adj[1]) * F.fact(size - 1) * F.invfact(node[1] - 1)
    count %= MOD
    return count, size

def merge(lt, rt):
    size = lt[1] + rt[1] - 1
    count = lt[0] * rt[0] * F.invfact(lt[1] - 1) * F.invfact(rt[1] - 1) * F.fact(size - 1)
    count %= MOD
    return count, size

ti = (1, 1)
ei = (1, 0)

D = T.rerooting(func, merge, ti, ei)

res = []

for i in range(N):
    res.append(D[i][0])

print('\n'.join(map(str, res)))