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:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input().strip())
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = [int(s) for s in input().strip().split()]
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)

    sys.setrecursionlimit(10 ** 6)
    
    M = 10 ** 9 + 7
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = (fact[i - 1] * i) % M
    
    def inv(x):
        return pow(x, M - 2, M)

    def comb(m, k):
        return (((fact[m] * inv(fact[k])) % M) * inv(fact[m - k])) % M

    result = [0] * n
    size = [1] * n
    low = [1] * n

    def dfs1(u, parent=-1):
        for v in adj[u]:
            if v == parent:
                continue
            dfs1(v, u)
            size[u] += size[v]
        remain = size[u] - 1
        for v in adj[u]:
            if v == parent:
                continue
            low[u] = (low[u] * comb(remain, size[v]) * low[v]) % M
            remain -= size[v]
    
    def dfs2(u, parent=-1, up=1):
        result[u] = (comb(n - 1, size[u] - 1) * low[u] * up) % M
        for v in adj[u]:
            if v == parent:
                continue
            dfs2(v, u, (result[u] * inv(comb(n - 1, size[v])) * inv(low[v])) % M)
    
    dfs1(0)
    # print(size)
    # print(low)
    dfs2(0)
    for x in result:
        print(x)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

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

nn = 200200
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
inv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % mod
fainv[-1] = pow(fa[-1], mod-2, mod)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % mod
for i in range(1, nn)[::-1]:
    inv[i] = fainv[i] * fa[i-1]

C = lambda a, b: fa[a] * fainv[b] % mod * fainv[a-b] % mod if 0 <= b <= a else 0

N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 1
    for j in X[i]:
        a = a * BU[j] % mod
        s += SI[j]
    SI[i] = s
    BU[i] = inv[s] * a % mod

for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for j in range(c):
        AL[j+1] = AL[j] * BU[X[i][j]] % mod
    for j in range(c)[::-1]:
        AR[j] = AR[j+1] * BU[X[i][j]] % mod
    for j in range(c):
        TD[X[i][j]] = TD[i] * AL[j] % mod * AR[j+1] % mod * inv[N - SI[X[i][j]]] % mod

for i in range(N):
    print(BU[i] * fa[SI[i]] % mod * TD[i] % mod * fa[N - SI[i]] % mod * C(N-1, SI[i] - 1) % mod)

Submission status: Accepted

Solution code:
from collections import deque
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)

mod = 10**9 + 7
queue = deque()
queue.append(0)
parent = [-1]*n
parent[0] = 0
while queue:
    now = queue.popleft()
    for to in G[now]:
        if parent[to] == -1:
            parent[to] = now
            queue.append(to)

data1 = [[0,0] for i in range(n)]
def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact

fact,rfact = factorial(2*10**5,mod)
def com(l):
    res = 1
    s = 0
    for x in l:
        res *= rfact[x]
        res %= mod
        s += x
    res *= fact[s]
    res %= mod
    return res
def dfs(now,pre):
    if data1[now] != [0,0]:
        return
    if len(G[now]) == 1 and G[now][0] == pre:
        data1[now] = [1,1]
        return
    x,y = 0,1
    child = []
    for to in G[now]:
        if pre == to:
            continue
        dfs(to,now)
        child.append(data1[to][1])
        y *= data1[to][0]
        y %= mod
    res = y * com(child)
    res %= mod
    data1[now] = [res,sum(child)+1]
    return

dfs(0,-1)

ans = [data1[i][0] for i in range(n)]

que = deque()
que.append([0,0])
while que:
    now,pre = que.popleft()
    for to in G[now]:
        if to == pre:continue
        ans[to] = ans[now]*data1[to][1]*pow(n-data1[to][1],mod-2,mod)
        ans[to] %= mod
        que.append([to,now])

for x in ans:
    print(x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
mod = 10**9+7
fact = [1]*(2*10**5+1)
for n in range(1,2*10**5+1):
    fact[n] = n*fact[n-1]%mod
factinv = [1]*(2*10**5+1)
inv = [1]*(2*10**5+1)
for n in range(1,2*10**5+1):
    factinv[n] = pow(fact[n],mod-2,mod)
    inv[n] = pow(n,mod-2,mod)
def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod

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

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

p = [-1]*N
p[0] = 0
q = [0]
while q:
    i = q.pop()
    for j in g[i]:
        if p[j]==-1:
            p[j] = i
            q.append(j)

c = [[] for _ in range(N)]
for i in range(1,N):
    c[p[i]].append(i)

cn = [-1]*N
def rec(n):
    if cn[n] != -1:
        return cn[n]
    res = 0
    for i in c[n]:
        res += rec(i)+1
    cn[n] = res
    return res

cn[0] = rec(0)    

ans = [0]*N

def dfs(n):
    res = fact[cn[n]]
    for c in g[n]:
        if c==p[n]:
            continue
        res *= factinv[cn[c]+1]*dfs(c)
        res %= mod
    return res

ans[0] = dfs(0)

q = [0]
while q:
    i = q.pop()
    for j in g[i]:
        if ans[j]==0:
            ans[j] = ans[i]*(cn[j]+1)*inv[N-1-cn[j]]%mod
            q.append(j)

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

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    # comb init
    mod = 1000000007
    nmax = 2*10 ** 5 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

    def comb(n, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

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


    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    dp = [1] * (N+1)
    size = [1] * (N+1)
    for v in seq:
        for u in child[v]:
            size[v] += size[u]
        L = size[v] - 1
        for u in child[v]:
            dp[v] = (dp[v] * (dp[u] * comb(L, size[u]))%mod)%mod
            L -= size[u]

    seq.reverse()
    dp2 = [0] * (N+1)
    for v in seq:
        if v == 1:
            dp2[1] = dp[1]
            continue
        p = par[v]
        dp2[v] = dp[v]
        PP = (dp2[p] * pow((dp[v] * comb(N-1, size[v]))%mod, mod-2, mod))%mod
        dp2[v] = (dp2[v] * PP * comb(N-1, size[v]-1))%mod
    for v in range(1, N+1):
        print(dp2[v])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

mod = 10**9+7

class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

n = int(input())
G = [[] for i 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)
PCM = PERM_COMB_MOD(2*n)
root = n//2

tmp = [[] for i in range(n)]
cost = [1]*n
size = [1]*n
def bfs1(root):
    rev = [(root, -1)]
    for i in range(n):
        cur, par = rev[i]
        for to in G[cur]:
            if to != par:
                rev.append((to, cur))
    for i in reversed(range(1,n)):
        cur, par = rev[i]
        size[par] += size[cur]
        if len(tmp[cur]) == 0:
            pass
        elif len(tmp[cur]) == 1:
            cost[cur] = tmp[cur][0]
        else:
            size_sum = 0
            inv_sum = 1
            count_sum = 1
            for to in G[cur]:
                if to != par:
                    size_sum += size[to]
                    inv_sum *= PCM.finv[size[to]]
                    inv_sum %= mod
                    count_sum *= cost[to]
                    count_sum %= mod
            cost[cur] = PCM.fac[size_sum] * inv_sum * count_sum % mod
        tmp[par].append(cost[cur])

bfs1(root)

ans = [0]*n
def bfs2(root):
    rev = [(root, -1, 1)]
    for i in range(n):
        cur, par, d_par = rev[i]
        size_par = n - size[cur]
        size_sum = 0
        inv_sum = 1
        count_sum = 1
        for to in G[cur]:
            if to != par:
                size_sum += size[to]
                inv_sum *= PCM.finv[size[to]]
                count_sum *= cost[to]
            else:
                size_sum += size_par
                inv_sum *= PCM.finv[size_par]
                count_sum *= d_par
            inv_sum %= mod
            count_sum %= mod
        ans_i = PCM.fac[size_sum]*inv_sum*count_sum % mod
        ans[cur] = ans_i
        for to in G[cur]:
            if to == par:
                continue
            b = size[to]
            bb = cost[to]
            d_nxt = ans_i * PCM.fac[b] * pow(bb, mod-2, mod) * PCM.fac[size_sum-b] * PCM.finv[size_sum] % mod
            rev.append((to, cur, d_nxt))
bfs2(root)
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
    import sys
    mod = pow(10, 9) + 7
    sys.setrecursionlimit(pow(10, 8))

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

from collections import deque
N, = map(int, input().split())
d = [list() for _ in range(N+1)]
d2 = [list() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

queue=deque([1])
vs = set([1])
vs_bfs = list()
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)
        d2[v].append(u)

dp1 = [0 for _ in range(N+1)]
sss = [0 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    ts = []
    for u in d2[v]:
        t = mul(dp1[u], t)
        ts.append(sss[u])
    st = sum(ts)
    sss[v] = st + 1
    for tt in ts:
        t = mul(cmb(st, tt, mod), t)
        st -= tt
    dp1[v] = t
#print(dp1)

dp2 = [0]*(N+1)
for v in vs_bfs:
    if v == 1:
        dp2[v] = dp1[v]
        continue
    p = parents[v]
#    print(dp2[p])
    t = div2(dp2[p], mul(dp1[v], cmb(N-1, sss[v], mod)))
    dp2[v] = mul(mul(dp1[v], t), cmb(N-1, N-sss[v], mod))

#print(dp2)

for x in dp2[1:]:
    print(x)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
fac = [1] * (2 * 10 ** 5 + 10)
for i in range(len(fac) - 1):
    fac[i + 1] = fac[i] * (i + 1) % MOD


def euler_tour(G, root=0):
    n = len(G)
    euler = []
    dq = [root]
    visited = [0] * n
    while dq:
        u = dq.pop()
        euler += [u]
        if visited[u]:
            continue
        dq += [u]
        for v in G[u]:
            if visited[v]:
                continue
            # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
            else:
                dq += [v]
        visited[u] = 1
    return euler


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)
e = euler_tour(g)
pr = [-1] * n
d = [0] * n
for i, x in enumerate(e):
    if pr[x] == -1:
        pr[x] = i
    else:
        d[x] = (i - pr[x]) // 2
s = [0]
p = [0] * n
v = [0] * n
for node in e:
    if v[node]:
        for t in g[node]:
            if d[t] <= d[node]:
                p[node] = p[node] * \
                    pow(fac[d[t] + 1], MOD - 2, MOD) * p[t] % MOD
    else:
        v[node] = 1
        p[node] = fac[d[node]]
s = [0]
ans = [0] * n
ans[0] = p[0]
while s:
    p = s.pop()
    for node in g[p]:
        if not ans[node]:
            ans[node] = ans[p] * (d[node] + 1) * \
                pow(n - d[node] - 1, MOD - 2, MOD) % MOD
            s.append(node)
for row in ans:
    print(row)

Submission status: Accepted

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

nn = 200200
mod = 10**9+7
fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % mod
fainv[-1] = pow(fa[-1], mod-2, mod)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % mod

C = lambda a, b: fa[a] * fainv[b] % mod * fainv[a-b] % mod if 0 <= b <= a else 0

N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 0
    for j in X[i]:
        a = a * BU[j] * fainv[SI[j]] % mod
        s += SI[j]
    SI[i] = s + 1
    BU[i] = fa[s] * a % mod

for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for j in range(c):
        AL[j+1] = AL[j] * BU[X[i][j]] % mod * fainv[SI[X[i][j]]] % mod
    for j in range(c)[::-1]:
        AR[j] = AR[j+1] * BU[X[i][j]] % mod * fainv[SI[X[i][j]]] % mod
    for j in range(c):
        TD[X[i][j]] = TD[i] * fainv[N - SI[i]] % mod * AL[j] % mod * AR[j+1] % mod * fa[N - 1 - SI[X[i][j]]] % mod

for i in range(N):
    print(BU[i] * TD[i] % mod * C(N-1, SI[i] - 1) % mod)

Submission status: Accepted

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


class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


def solve(tree, root):
    def dfs1():
        st1 = deque([root])
        st2 = deque([root])
        # 行きがけ順を記録
        while st1:
            v = st1.pop()
            for nxt_v in tree[v]:
                if nxt_v in par:
                    continue
                else:
                    par[nxt_v] = v
                    st1.append(nxt_v)
                    st2.append(nxt_v)
        # 帰りがけ順で処理
        while st2:
            v = st2.pop()
            res = 1
            c = 1
            for nxt_v in tree[v]:
                if nxt_v == par[v]:
                    continue
                else:
                    res *= dist1[nxt_v]
                    res *= comb.inv_fact[cnt[nxt_v]]
                    res %= MOD
                    c += cnt[nxt_v]
            cnt[v] = c
            dist1[v] = res * comb.fact[c - 1] % MOD
    def dfs2():
        q = deque([(root, 0, 0)])
        while q:
            v, par_val, par_cnt = q.pop()
            tmp_val = {}
            tmp_cnt = {}
            for nxt_v in tree[v]:
                if nxt_v == par[v]:
                    tmp_val[nxt_v] = par_val
                    tmp_cnt[nxt_v] = par_cnt
                else:
                    tmp_val[nxt_v] = dist1[nxt_v]
                    tmp_cnt[nxt_v] = cnt[nxt_v]
            res = 1
            c = 1
            for nxt_v in tmp_val:
                    res *= tmp_val[nxt_v]
                    res *= comb.inv_fact[tmp_cnt[nxt_v]]
                    res %= MOD
                    c += tmp_cnt[nxt_v]
            tmp_cnt[v] = c
            dist2[v] = res * comb.fact[c - 1] % MOD
            for nxt_v in tree[v]:
                if nxt_v == par[v]:
                    continue
                else:
                    tmp = dist2[v]\
                            * pow(tmp_val[nxt_v], MOD - 2, MOD) * comb.fact[tmp_cnt[nxt_v]] \
                            * comb.inv_fact[tmp_cnt[v] - 1] \
                            * comb.fact[tmp_cnt[v] - 1 - tmp_cnt[nxt_v]] % MOD
                    q.append((nxt_v, tmp, c - cnt[nxt_v]))

    par = {root: -1}
    dist1 = [0] * n
    cnt = [0] * n
    dist2 = [0] * n
    dfs1()
    dfs2()
    return dist2


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
MOD = 10 ** 9 + 7

tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

comb = Combination(10 ** 6, MOD)
for i in solve(tree, 0):
    print(i % MOD)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        fx = ans[x]
        nf = fx*inv[s[x]-1]%mod
        sx = s[x]
        for y in v[x]:
            sy = s[y]
            nsx = sx-sy
            nsy = s[x]
            if ans[y] == None:
                fy = nf*s[y]*f[nsy-1]*p[nsx]%mod
                ans[y] = fy
                s[x] = nsx
                s[y] = nsy
                dfs(y)
                s[x] = sx
                s[y] = sy

    n = I()
    f = [1]
    for i in range(1,n+1):
        f.append(f[-1]*i%mod)
    inv = [None]*(n+1)
    inv[n] = pow(f[n],mod-2,mod)
    for i in range(n)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod

    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    m = d[V[0]]
    s = [0]*n
    res = 1
    for i in V:
        j = p[i]
        s[i] += 1
        if j != None:
            s[j] += s[i]
            res *= inv[s[i]]
        if d[i] == m:
            continue
        res *= f[s[i]-1]
        res %= mod
    ans = [None]*n
    ans[0] = res
    p = [pow(i,mod-2,mod) for i in range(n+1)]
    dfs(0)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
n = int(input())
big = 1
mod = 10 ** 9 + 7
for i in range(1,n):
  big *= i
  big %= mod
def inv(x):
  y = 1
  while x != 1:
    y *= mod // x + 1
    y %= mod
    x -= mod % x
  return y
tribe = [1 for _ in range(n)]
we = [1 for _ in range(n)]
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
seen = [0 for _ in range(n)]
pre = [0 for _ in range(n)]
seen[0] = 1
rank = []
now = [0]
while now:
  rank.append(now)
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        now.append(y)
        pre[y] = x
#print(seen)
#print(pre)
#print(rank)
pre[0] = 10**6
rank.reverse()
for z in rank:
  if z == [0]:
    continue
  for w in z:
    tribe[pre[w]] += tribe[w]
    we[pre[w]] *= tribe[w] * we[w]
    we[pre[w]] %= mod
#print(tribe)
#print(we)
rank.reverse()
for z in rank:
  if z == [0]:
    continue
  for w in z:
    tmp = we[pre[w]]
    tmp *= inv(we[w]*tribe[w]%mod)
    tmp *= n - tribe[w]
    we[w] *= tmp
    we[w] %= mod
#print(we)
for i in range(n):
  print(big*inv(we[i])%mod)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
mod = 10**9+7
rng = 200100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
deg[1] += 1
stack = [1]
cnt = [0]*(n+1)
for i in range(2,n+1):
  if deg[i] == 1:
    stack.append(i)
    cnt[i] = 1
dp = [[] for i in range(n+1)]
while stack:
  x = stack.pop()
  if dp[x]:
    cnt[x] = sum(dp[x])+1
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(cnt[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
def euler_tour(G, root=1):
  n = len(G)
  euler = []
  dq = deque([root])
  dq2 = deque()
  visited = [0]*(n+1)
  while dq:
    u = dq.pop()
    euler += [u]
    if visited[u]:
      continue
    for v in G[u]:
      if visited[v]:
        dq += [v]
    # [親頂点、子頂点、子頂点、。。。]と入れていく.その後連結
      else:
        dq2 += [v]
    dq.extend(dq2)
    dq2 = deque()
    visited[u] = 1
  return euler
order = euler_tour(graph)
ans1 = fctr[n]
for i in range(1,n+1):
  ans1 = (ans1*pow(cnt[i],mod-2,mod))%mod
ans = [0]*(n+1)
ans[1] = ans1
for i in range(1,len(order)):
  prv = order[i-1]
  now = order[i]
  no = cnt[now]
  cnt[prv] -= cnt[now]
  cnt[now] += cnt[prv]
  pr = cnt[prv]
  if ans[now]:
    continue
  ans[now] = ans[prv]*pow(pr,mod-2,mod)*no%mod
ans = ans[1:]
print(*ans,sep="\n")

Submission status: Accepted

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

nn = 202020
mod = 10 ** 9 + 7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % mod
fainv[-1] = pow(fa[-1], mod-2, mod)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % mod

C = lambda a, b: fa[a] * fainv[b] * fainv[a-b] % mod if 0 <= b <= a else 0

N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 0
    for j in X[i]:
        a = a * BU[j] * fainv[SI[j]] % mod
        s += SI[j]
    SI[i] = s + 1
    BU[i] = fa[s] * a % mod

for i in R:
    a = TD[i] * fainv[N - SI[i]]
    for j in X[i]:
        a = a * BU[j] * fainv[SI[j]] % mod
    for j in X[i]:
        TD[j] = a * pow(BU[j], mod-2, mod) % mod * fa[SI[j]] % mod * fa[N - 1 - SI[j]] % mod

for i in range(N):
    print(BU[i] * TD[i] % mod * C(N-1, SI[i] - 1) % mod)