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 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)]

tree = [[] for _ in range(N)]

for e in E:
    tree[e[0] - 1].append(e[1] - 1)
    tree[e[1] - 1].append(e[0] - 1)

visited = [0 for _ in range(N)]
visited[0] = 1

parent = [None for _ in range(N)]
parent[0] = -1

order = []
order.append(0)

stack = [0]

while stack:
    node = stack.pop()
    for adj in tree[node]:
        if not visited[adj]:
            visited[adj] = 1
            parent[adj] = node
            order.append(adj)
            stack.append(adj)

dp = [[1, 1] for _ in range(N)]
cum_l = [[1, 0] for _ in range(N)]
cum_r = [[1, 0] for _ in range(N)]

F = Factorial(N + 1, MOD)

for node in order[::-1]:
    dp_node = [1, 1]
    for adj in tree[node]:
        if parent[adj] == node:
            cum_l[adj][0] = dp_node[0]
            cum_l[adj][1] = dp_node[1]
            dp_node[1] += dp[adj][1]
            dp_node[0] *= dp[adj][0]
            dp_node[0] *= F.invfact(dp[adj][1])
            dp_node[0] *= F.fact(dp_node[1] - 1)
            dp_node[0] *= F.invfact(dp_node[1] - dp[adj][1] - 1)
            dp_node[0] %= MOD

    dp_node = [1, 1]
    for adj in tree[node][::-1]:
        if parent[adj] == node:
            cum_r[adj][0] = dp_node[0]
            cum_r[adj][1] = dp_node[1]
            dp_node[1] += dp[adj][1]
            dp_node[0] *= dp[adj][0]
            dp_node[0] *= F.invfact(dp[adj][1])
            dp_node[0] *= F.fact(dp_node[1] - 1)
            dp_node[0] *= F.invfact(dp_node[1] - dp[adj][1] - 1)
            dp_node[0] %= MOD

    dp[node][0] = dp_node[0]
    dp[node][1] = dp_node[1]

dp_inv = [[1, 0] for _ in range(N)]

for node in order:
    if node == 0:
        continue

    merged = [1, 0]
    merged[1] = cum_l[node][1] + cum_r[node][1] - 1
    merged[0] *= cum_l[node][0] * F.invfact(cum_l[node][1] - 1)
    merged[0] *= cum_r[node][0] * F.invfact(cum_r[node][1] - 1)
    merged[0] *= F.fact(merged[1] - 1)
    merged[0] %= MOD

    par = parent[node]
    dp_inv[node][0] = merged[0]
    dp_inv[node][1] = merged[1]
    dp_inv[node][1] += dp_inv[par][1]
    dp_inv[node][0] *= dp_inv[par][0]
    dp_inv[node][0] *= F.invfact(dp_inv[par][1])
    dp_inv[node][0] *= F.fact(dp_inv[node][1] - 1)
    dp_inv[node][0] *= F.invfact(dp_inv[node][1] - dp_inv[par][1] - 1)
    dp_inv[node][0] %= MOD

    dp_node = [1, 1]
    dp_node[0] = dp[node][0]
    dp_node[1] = dp[node][1]
    dp_node[1] += dp_inv[node][1]
    dp_node[0] *= dp_inv[node][0]
    dp_node[0] *= F.invfact(dp_inv[node][1])
    dp_node[0] *= F.fact(dp_node[1] - 1)
    dp_node[0] *= F.invfact(dp_node[1] - dp_inv[node][1] - 1)
    dp_node[0] %= MOD

    dp[node][0] = dp_node[0]
    dp[node][1] = dp_node[1]

res = []

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

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

Submission status: Accepted

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

def solve():
    MOD = 10**9 + 7

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

    def getFacts(n, MOD):
        facts = [1] * (n+1)
        for x in range(2, n+1):
            facts[x] = (facts[x-1] * x) % MOD
        return facts
    facts = getFacts(N, MOD)
    def getInvFacts(n, MOD):
        invFacts = [0] * (n+1)
        invFacts[n] = pow(facts[n], MOD-2, MOD)
        for x in reversed(range(n)):
            invFacts[x] = (invFacts[x+1] * (x+1)) % MOD
        return invFacts
    invFacts = getInvFacts(N, MOD)

    def getComb(n, k, MOD):
        if n < k:
            return 0
        return facts[n] * invFacts[k] * invFacts[n-k] % MOD

    dp = [1] * N
    sizes = [0] * N
    def dfsDP(v, vPar):
        sizes[v] = 0
        for v2 in adjL[v]:
            if v2 == vPar: continue
            dp[v] = dp[v] * dfsDP(v2, v) % MOD
            sizes[v] += sizes[v2]
            dp[v] = dp[v] * getComb(sizes[v], sizes[v2], MOD) % MOD
        sizes[v] += 1
        return dp[v]

    anss = [0] * N
    def dfsAns(v, vPar, resPar):
        anss[v] = dp[v] * resPar * getComb(N-1, sizes[v]-1, MOD) % MOD

        for v2 in adjL[v]:
            if v2 == vPar: continue
            coef = dp[v2] * getComb(N-1, sizes[v2], MOD) % MOD
            dfsAns(v2, v, anss[v] * pow(coef, MOD-2, MOD) % MOD)


    dfsDP(0, -1)
    dfsAns(0, -1, 1)

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


solve()

Submission status: Accepted

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

def solve():
    MOD = 10**9 + 7

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

    def getInvs(n, MOD):
        invs = [1] * (n+1)
        for x in range(2, n+1):
            invs[x] = (-(MOD//x) * invs[MOD%x]) % MOD
        return invs
    invs = getInvs(N, MOD)

    dp = [[] for _ in range(N)]
    outdegs = [0] * N
    sizes = [0] * N
    iPars = [-1] * N
    def dfsDP(v, vPar):
        outdeg = outdegs[v] = len(adjL[v])
        dp[v] = [0] * outdeg
        res = 1
        sizes[v] = 1
        for i, v2 in enumerate(adjL[v]):
            if v2 == vPar:
                iPars[v] = i
                continue
            dp[v][i] = dfsDP(v2, v)
            res = res * dp[v][i] % MOD
            sizes[v] += sizes[v2]
        return res * invs[sizes[v]] % MOD

    anss = [0] * N
    def dfsAns(v, vPar, resPar):
        if vPar != -1:
            dp[v][iPars[v]] = resPar

        outdeg = outdegs[v]
        dpL = [1] * (outdeg+1)
        for i in range(outdeg):
            v2 = adjL[v][i]
            dpL[i+1] = dpL[i] * dp[v][i] % MOD
        dpR = [1] * (outdeg+1)
        for i in reversed(range(outdeg)):
            v2 = adjL[v][i]
            dpR[i] = dpR[i+1] * dp[v][i] % MOD
        anss[v] = dpL[-1] * invs[N]

        for i, v2 in enumerate(adjL[v]):
            if v2 == vPar: continue
            dfsAns(v2, v, dpL[i] * dpR[i+1] * invs[N-sizes[v2]] % MOD)


    dfsDP(0, -1)
    dfsAns(0, -1, 0)

    def getFact(n, MOD):
        fact = 1
        for i in range(1, n+1):
            fact = (fact * i) % MOD
        return fact
    factN = getFact(N, MOD)

    for v in range(N):
        anss[v] = anss[v] * factN % MOD
    print('\n'.join(map(str, anss)))


solve()

Submission status: Accepted

Solution code:
import sys

def solve():
    input = lambda: sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10 ** 7)
    mod = 10 ** 9 + 7

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

    def dfs(v, Pa=-1):
        for u in to[v]:
            if u == Pa: continue
            dfs(u, v)
            size[v] += size[u]
            dp[v] *= dp[u] % mod
            dp[v] *= inv[size[u]] % mod
        dp[v] *= fac[size[v]] % mod
        size[v] += 1

    def bfs(v, Pa=-1, P_val=1, P_sz=0):
        ans[v] = P_val * dp[v] * comb(n - 1, P_sz) % mod
        for u in to[v]:
            if u == Pa: continue
            val = ans[v] * INV(dp[u] * comb(n - 1, size[u])) % mod
            bfs(u, v, val, n - size[u])

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

    fac = [1] * (n + 2)
    inv = [1] * (n + 2)

    for i in range(2, n + 1):
        fac[i] = fac[i - 1] * i % mod
    INV = lambda x: pow(x, mod - 2, mod)
    inv[n] = INV(fac[n])
    for i in range(n - 1, 1, -1):
        inv[i] = inv[i + 1] * (i + 1) % mod

    dp = [1] * n
    size = [0] * n
    ans = [0] * n

    dfs(0)
    bfs(0)
    print(*ans, sep='\n')

if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
#ABC160F

import sys
sys.setrecursionlimit(10**7)

def input():
	return sys.stdin.buffer.readline()[:-1]

MOD = 10**9+7
n = int(input())
con = [[] for _ in range(n)]
for _ in range(n-1):
	a, b = map(int, input().split())
	con[a-1].append(b-1)
	con[b-1].append(a-1)
stair = [1] #階乗MOD
stairr = [1] #階乗逆数MOD
for i in range(n):
	stair.append((stair[i] * (i+1)) % MOD)
	stairr.append(pow((stair[i] * (i+1)) % MOD, MOD-2, MOD))
cnt = [1 for _ in range(n)]
des_size = [1 for _ in range(n)]
des_case = [1 for _ in range(n)]
def dfs1(v, u):
	totalsize = 1 #v自身も含んだsizeであることに注意
	totalcase = 1
	for w in con[v]:
		if w == u:
			continue
		dfs1(w, v)
		totalsize += des_size[w]
		totalcase = (totalcase * des_case[w] * stairr[des_size[w]]) % MOD
	totalcase = (totalcase * stair[totalsize-1]) % MOD
	des_size[v] = totalsize
	des_case[v] = totalcase
	#print(v, u, totalsize, totalcase)
	#print(des_size)
	#print(des_case)
	return

dfs1(0, -1)
#print(des_size) 
#print(des_case)
asc_size = [1 for _ in range(n)]
asc_case = [1 for _ in range(n)]
def dfs2(v, u):
	if u == -1:
		for w in con[v]:
			if w == u:
				continue 
			dfs2(w, v)
		return
	asc_size[v] = n - des_size[v] + 1
	x0 = des_size[u]
	y0 = des_case[u]
	x1 = des_size[v]
	y1 = des_case[v]
	x2 = asc_size[u]
	y2 = asc_case[u]
	p = (y0 * y2 * stair[x1] * stair[x0+x2-x1-2]) % MOD
	q = (stairr[x0-1] * stairr[x2-1] * pow(y1, MOD-2, MOD)) % MOD
	asc_case[v] = (p*q) % MOD
	#print(v, u, asc_size, asc_case, p, q)
	for w in con[v]:
		if w == u:
			continue 
		dfs2(w, v)
	return
dfs2(0, -1)
#print(asc_size) 
#print(asc_case)

for i in range(n):
	r = stair[des_size[i] + asc_size[i] -2]
	s = (stairr[des_size[i]-1] * stairr[asc_size[i]-1]) % MOD
	t = (des_case[i] * asc_case[i]) % MOD
	print((r * s * t) % MOD)

Submission status: Accepted

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

mod = 10 ** 9 + 7
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)

##### Settings
unit = 1
merge = lambda a, b: a * b % mod
adj_bu = lambda a, i: a * inv(SIZE[i]) % mod
adj_td = lambda a, i, p: a * inv(N-SIZE[i]) % mod
adj_butd = lambda a, i: a * inv(N) % mod
#####

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

inv = lambda i: fainv[i] * fa[i-1] % mod

SIZE = [1] * N
for i in R[1:][::-1]:
    SIZE[P[i]] += SIZE[i]

ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_bu(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])
    ac = unit
    for j in X[i][::-1]:
        TD[j] = adj_td(merge(TD[j], ac), j, i)
        ac = merge(ac, XX[j])
        XX[j] = adj_butd(merge(ME[j], TD[j]), j)

XX = [x * fa[N] % mod for x in XX]
print(*XX, sep = "\n")

Submission status: Accepted

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

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)

lim = 10**5*2
fact = [1, 1] + [0] * (lim-1)
fact_inv = [1, 1] + [0] * (lim-1)
inv = [0, 1] + [0] * (lim-1)
for i in range(2, lim+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
def comb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact[n] * (fact_inv[m] * fact_inv[n-m] % MOD) % MOD
def icomb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact_inv[n] * (fact[m] * fact[n-m] % MOD) % MOD

dp = [1] * n
size = [0] * n

def dfs(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        dfs(nv, v)
        ns = size[nv]+1
        size[v] += ns
        dp[v] *= dp[nv] * comb(size[v], ns) % MOD
        dp[v] %= MOD

def dfs2(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        d, sz = dp[v], size[v]
        d *= pow(dp[nv], MOD-2, MOD) * icomb(sz, size[nv]+1) % MOD
        d %= MOD
        sz -= size[nv]+1

        size[nv] += sz+1
        dp[nv] *= d * comb(size[nv], sz+1) % MOD
        dp[nv] %= MOD
        dfs2(nv, v)

dfs(0, -1)
dfs2(0, -1)
print(*dp, sep="\n")

Submission status: Accepted

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

def solve():
    N = int(input())
    AB = [tuple(map(int,input().split())) for i in range(N-1)]
    es = [[] for i in range(N)]
    for i,(a,b) in enumerate(AB):
        a,b = a-1,b-1
        es[a].append((b,i))
        es[b].append((a,i))
    MOD = 10**9+7

    size = [-1] * N
    def calc_size(v,p=-1):
        ret = 1
        for to,_ in es[v]:
            if to==p: continue
            ret += calc_size(to,v)
        size[v] = ret
        return ret
    calc_size(0)

    MAXN = N+5
    fac = [1,1] + [0]*MAXN
    finv = [1,1] + [0]*MAXN
    inv = [0,1] + [0]*MAXN
    for i in range(2,MAXN+2):
        fac[i] = fac[i-1] * i % MOD
        inv[i] = -inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i-1] * inv[i] % MOD

    dpdn = [0] * (N-1)
    dn = set()
    def dfs(v,p=-1):
        ret = fac[size[v]-1]
        for to,i in es[v]:
            if to==p: continue
            dn.add((v,to))
            dpdn[i] = dfs(to,v)
            ret *= finv[size[to]] * dpdn[i]
        ret %= MOD
        return ret
    dfs(0)

    dpup = [0] * (N-1)
    from collections import deque
    q = deque([(0,-1)])
    while q:
        v,p = q.popleft()
        whole = 1
        for to,i in es[v]:
            if to != p:
                whole *= finv[size[to]] * dpdn[i]
            else:
                whole *= finv[N-size[v]] * dpup[i]
        whole %= MOD
        for to,i in es[v]:
            if to==p: continue
            dpup[i] = (whole * fac[N-size[to]-1] * fac[size[to]] * pow(dpdn[i], MOD-2, MOD)) % MOD
            q.append((to,v))

    ans = []
    for v in range(N):
        a = 1
        s = 0
        for to,i in es[v]:
            if (v,to) in dn:
                s += size[to]
                a *= finv[size[to]] * dpdn[i]
            else:
                s += N-size[v]
                a *= finv[N-size[v]] * dpup[i]
            a %= MOD
        a *= fac[s]
        ans.append(a%MOD)
    print(*ans, sep='\n')

solve()

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

inv = lambda i: fainv[i] * fa[i-1] % mod

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)

##### Settings
unit = 1
merge = lambda a, b: a * b % mod
adj_bu = lambda a, i=-1: a * fainv[SI[i]] % mod * fa[SI[i]-1] % mod
adj_td = lambda a, i=-1: a * fainv[N - SI[i]] % mod * fa[N - SI[i] - 1] % mod
calc = lambda i: merge(BU[i], TD[i]) * SI[i] % mod * fa[N - 1] % mod
#####

SI = [1] * N
for i in R[1:][::-1]:
    SI[P[i]] += SI[i]

BU = [unit] * N
TD = [unit] * N
for i in R[1:][::-1]:
    BU[i] = adj_bu(BU[i], i)
    p = P[i]
    BU[p] = merge(BU[p], BU[i])
BU[R[0]] = adj_bu(BU[R[0]], R[0])

AX = [0] * N
for i in R:
    ac = unit
    for j in X[i]:
        AX[j] = ac
        ac = merge(ac, BU[j])
    ac = unit
    for j in X[i][::-1]:
        AX[j] = merge(AX[j], ac)
        TD[j] = adj_td(merge(TD[i], AX[j]), j)
        ac = merge(ac, BU[j])

ANS = [calc(i) for i in range(N)]
print(*ANS, sep = "\n")

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

inv = lambda i: fainv[i] * fa[i-1] % mod

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)

unit = 1
f = lambda a, b: a * b % mod
g_bu = lambda a, i=-1: a * inv(SI[i]) % mod
g_td = lambda a, i=-1: a * inv(N - SI[i]) % mod

SI = [1] * N
for i in R[1:][::-1]:
    SI[P[i]] += SI[i]

BU = [unit] * N
TD = [unit] * N
for i in R[1:][::-1]:
    BU[i] = g_bu(BU[i], i)
    p = P[i]
    BU[p] = f(BU[p], BU[i])
BU[R[0]] = g_bu(BU[R[0]], R[0])

AX = [1] * N
for i in R:
    ac = unit
    for j in X[i]:
        AX[j] = ac
        ac = f(ac, BU[j])
    ac = unit
    for j in X[i][::-1]:
        AX[j] = f(AX[j], ac)
        TD[j] = g_td(f(TD[i], AX[j]), j)
        ac = f(ac, BU[j])

print(*[BU[i] * SI[i] % mod * TD[i] % mod * fa[N - 1] % mod for i in range(N)], sep = "\n")

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]

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)

unit = 1
f = lambda a, b: a * b % mod
g_bu = lambda a, i=-1: a * inv[SI[i]] % mod
g_td = lambda a, i=-1: a * inv[N - SI[i]] % mod

SI = [1] * N
for i in R[1:][::-1]:
    SI[P[i]] += SI[i]

BU = [unit] * N
TD = [unit] * N
for i in R[1:][::-1]:
    BU[i] = g_bu(BU[i], i)
    p = P[i]
    BU[p] = f(BU[p], BU[i])
BU[0] = g_bu(BU[0], 0)

AX = [1] * N
for i in R:
    ac = unit
    for j in X[i]:
        AX[j] = ac
        ac = f(ac, BU[j])
    ac = unit
    for j in X[i][::-1]:
        AX[j] = f(AX[j], ac)
        TD[j] = g_td(f(TD[i], AX[j]), j)
        ac = f(ac, BU[j])

print(*[BU[i] * SI[i] % mod * TD[i] % mod * fa[N - 1] % mod for i in range(N)], sep = "\n")

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]

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)

unit = 1
f = lambda a, b: a * b % mod
g_bu = lambda a, i=-1: a * inv[SI[i]] % mod
g_td = lambda a, i=-1: a * inv[N - SI[i]] % mod

SI = [1] * N
for i in R[::-1]:
    for j in X[i]:
        SI[i] += SI[j]

BU = [unit] * N
TD = [unit] * N
for i in R[::-1]:
    a = 1
    for j in X[i]:
        a = f(a, BU[j])
    BU[i] = g_bu(a, i)

AX = [1] * N
for i in R:
    ac = unit
    for j in X[i]:
        AX[j] = ac
        ac = f(ac, BU[j])
    ac = unit
    for j in X[i][::-1]:
        AX[j] = f(AX[j], ac)
        TD[j] = g_td(f(TD[i], AX[j]), j)
        ac = f(ac, BU[j])

print(*[BU[i] * SI[i] % mod * TD[i] % mod * fa[N - 1] % mod for i in range(N)], sep = "\n")

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)

unit = 1
f = lambda a, b: a * b % mod
g_bu = lambda a, i=-1: a * inv[SI[i]] % mod
g_td = lambda a, i=-1: a * inv[N - SI[i]] % mod

SI = [1] * N
for i in R[::-1]:
    for j in X[i]:
        SI[i] += SI[j]

BU = [unit] * N
TD = [unit] * N
for i in R[::-1]:
    a = 1
    for j in X[i]:
        a = f(a, BU[j])
    BU[i] = g_bu(a, i)

AX = [1] * N
for i in R:
    c = len(X[i])
    ac = unit
    for k, j in enumerate(X[i]):
        AX[j] = ac
        ac = f(ac, BU[j])
    ac = unit
    for k in range(c-1, -1, -1):
        j = X[i][k]
        AX[j] = f(AX[j], ac)
        ac = f(ac, BU[j])
    for k, j in enumerate(X[i]):
        TD[j] = g_td(f(TD[i], AX[j]), j)

print(*[BU[i] * SI[i] % mod * TD[i] % mod * fa[N - 1] % mod for i in range(N)], sep = "\n")

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)

f = lambda a, b: a * b % mod
g_bu = lambda a, i=-1: a * inv[SI[i]] % mod
g_td = lambda a, i=-1: a * inv[N - SI[i]] % mod

SI = [1] * N
for i in R[::-1]:
    for j in X[i]:
        SI[i] += SI[j]

BU = [1] * N
TD = [1] * N
for i in R[::-1]:
    a = 1
    for j in X[i]:
        a = f(a, BU[j])
    BU[i] = g_bu(a, i)

for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for k, j in enumerate(X[i]):
        AL[k+1] = f(AL[k], BU[j])
    for k in range(c-1, 0, -1):
        j = X[i][k]
        AR[k] = f(AR[k+1], BU[j])
    for k, j in enumerate(X[i]):
        TD[j] = g_td(f(TD[i], f(AL[k], AR[k+1])), j)

print(*[BU[i] * SI[i] % mod * TD[i] % mod * fa[N - 1] % mod for i in range(N)], sep = "\n")

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 k, j in enumerate(X[i]):
        AL[k+1] = AL[k] * BU[j] % mod
    for k in range(c-1, 0, -1):
        j = X[i][k]
        AR[k] = AR[k+1] * BU[j] % mod
    for k, j in enumerate(X[i]):
        TD[j] = TD[i] * AL[k] % mod * AR[k+1] % mod * inv[N - SI[j]] % mod

print(*[BU[i] * fa[SI[i]] % mod * TD[i] % mod * fa[N - SI[i]] % mod * C(N-1, SI[i] - 1) % mod for i in range(N)], sep = "\n")

Submission status: Accepted

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

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

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

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

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

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

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

class p:
    num = -1
    parent = -1

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

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

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()