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: Time Limit Exceeded

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
mod = 10**9+7
comb = lambda n, r :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] *= comb(size[v], size[u]) % 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')

Submission status: Time Limit Exceeded

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

def comb(n, r):
    if n < r or n < 0 or r < 0: return 0
    if n < 2*r: comb(n, n-r)
    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] *= comb(size[v], size[u]) % 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')

Submission status: Time Limit Exceeded

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
	ans = (r * s * t) % MOD
	print(ans)

Submission status: Time Limit Exceeded

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
	p = (des_case[u] * asc_case[u] * stair[des_size[v]] * stair[des_size[u]+asc_size[u]-des_size[v]-2]) % MOD
	q = (stairr[des_size[u]-1] * stairr[asc_size[u]-1] * pow(des_case[v], 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):
	ans = (stair[des_size[i] + asc_size[i] -2] * stairr[des_size[i]-1] * stairr[asc_size[i]-1] * des_case[i] * asc_case[i]) % MOD
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
#ABC160F

import sys
sys.setrecursionlimit(10**7)

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
	ans = (r * s * t) % MOD
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
def solve():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**9)
    mod = 10**9+7

    def comb(n, r):
        if 2*r > n: comb(n, n-r)
        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] *= comb(size[v], size[u]) % 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: Time Limit Exceeded

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

def comb(n, r):
    if 2*r > n: comb(n, n-r)
    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] *= comb(size[v], size[u]) % 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')

Submission status: Time Limit Exceeded

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

def comb(n, r):
    if 2*r > n: comb(n, n-r)
    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] *= comb(size[v], size[u]) % 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
        x = dp[u] * comb(n-1, size[u])
        val = ans[v] * pow(x, mod-2, mod) % mod
        bfs(u, v, val, n-size[u])

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

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

for i in range(2, n+1):
    fac[i] = fac[i-1] * i % mod
inv[n] = pow(fac[n], mod-2, mod)
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')

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict,deque
import copy
dic = defaultdict(int)
D = defaultdict(deque)

MOD = 10 ** 9 + 7

N = int(input())
MAP = [[int(i) for i in input().split()] for _ in range(N-1)]

for i,j in MAP:
    D[i].append(j)
    D[j].append(i)

MAP_d = copy.deepcopy(D)

stack = deque([1])
dfs_order = []
flg = [0] * N
#深さ優先探索
while stack:
    v = stack.pop()
    dfs_order.append(v)
    if bool(MAP_d[v]):
        w = MAP_d[v].pop()
        stack.append(w)
    else:
        if bool(stack):
            stack.pop()


MAP_b = copy.deepcopy(D)
stack = deque([1])
bfs_order = []
flg = [0] * (N+1)
BFS = defaultdict(deque)
while stack:
    v = stack.popleft()
    if flg[v] == 0:
        bfs_order.append(v)
    flg[v] = 1
    if bool(MAP_b[v]):
        for w in MAP_b[v]:
            if flg[w] == 1:
                continue
            stack.append(w)
            BFS[w].append(v)
    
    else:
        if bool(stack):
            stack.pop()

#累乗の計算
fact = [1] * (N + 10)
for n in range(1, N + 10):
    fact[n] = n * fact[n - 1] % MOD

#DP[root]の計算
dp = [1] * (N+1)
flg = [0] * (N+1)
size = [1] * (N+1)

for i,j in enumerate(bfs_order[::-1]):
    dp[j] *= fact[size[j]-1]
    dp[j] = int(dp[j])
    if i < len(bfs_order)-1:
        tar = BFS[j]
        size[tar[0]] += size[j]
        dp[tar[0]] *= (dp[j]/fact[size[j]])
        
root = bfs_order[0]
stack = deque([root])
MAP = copy.deepcopy(D)
flg = [0] * (N+1)
fact_inv = [1] * (N + 10)
fact_inv[-1] = pow(fact[-1], MOD - 2, MOD)
for n in range(N + 9, 0, -1):
    fact_inv[n - 1] = fact_inv[n] * n % MOD

for n in range(N+9,0,-1):
    a = fact_inv[n] * fact[n]

order = []
dp_p = [1] *(N+1)

size_p = [N+1 - i for i in size]


while stack:
    v = stack.popleft()
    flg[v] = 1
    if bool(MAP[v]):
        for w in MAP[v]:
            if flg[w] ==0:
                x = dp_p[v]
                x *= dp[v]
                x *= fact_inv[size[v]-1]
                x *= fact[size[w]]
                x *= pow(dp[w], MOD - 2, MOD)
                x *= fact_inv[size_p[v]-1]
                x *= fact[size_p[w]-2]
                dp_p[w] = x % MOD
                stack.append(w)
    else:
        stack.pop()
    
# print(size_p)
# print(size)
for s,sp,d,dd in zip(size[1::],size_p[1::],dp[1::],dp_p[1::]):
    sp -= 1
    s -= 1
    x = fact[s+sp] * fact_inv[s] * fact_inv[sp] * d * dd % MOD
    print(x)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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**6
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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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**6 * 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

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 *= inv[dp[nv]] * inv[comb(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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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**7
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

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 *= inv[dp[nv]] * inv[comb(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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
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')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
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**6
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 dfs(v, pv):
    res = 1
    size = 1
    for nv in g[v]:
        if nv == pv: continue
        nr, ns = dfs(nv, v)
        res *= nr * fact_inv[ns]
        res %= MOD
        size += ns
    res *= fact[size-1]
    return res % MOD, size

for i in range(n):
    print(dfs(i, -1)[0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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):
        size = top[1] + bottom[1]
        dp = top[0] * comb.factInv[top[1] - 1] * bottom[0] * comb.factInv[bottom[1]] * comb.fact[size - 1] % MOD
        return (dp, size)

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

    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.identDp
            for ch in child[v]:
                left[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            tmp = self.identDp
            for ch in reversed(child[v]):
                right[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            dp[v] = tmp

        fromParent = [self.identCum] * (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
comb = Combination(N + 100)

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

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