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:
from collections import deque
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
mod = 10**9+7
fact = [1]*(N+1)
fact_inv = [1]*(N+1)
for i in range(1,N+1):
  fact[i] = (fact[i-1]*i)%mod
  fact_inv[i] = pow(fact[i], mod-2, mod)

g = [deque([]) for _ in range(N+1)]
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  
parents = [0]*(N+1)
q = deque([])
s = deque([1])
while s:
  x = s.pop()
  q.append(x)
  for y in g[x]:
    if y==parents[x]:
      continue
    else:
      parents[y] = x
      s.append(y)
      
q = list(q)
size_forward = [0]*(N+1)
dp_forward = [1]*(N+1)
for i in q[::-1]:
  p = parents[i]
  s = size_forward[i] + 1
  size_forward[p] += s
  dp_forward[i] *= fact[size_forward[i]]
  dp_forward[i] %= mod
  dp_forward[p] *= dp_forward[i] * fact_inv[s]
  dp_forward[p] %= mod
  
size_back = [N-1-i for i in size_forward]
dp_back = [1]*(N+1)
for i in q[1:]:
  p = parents[i]
  x = dp_back[p]
  x *= fact_inv[size_back[p]]
  x %= mod
  x *= dp_forward[p]
  x *= fact_inv[size_forward[p]]
  x %= mod
  x *= fact[size_forward[i]+1]
  x *= pow(dp_forward[i],mod-2,mod)
  x %= mod
  x *= fact[size_back[i]-1]
  dp_back[i] = x % mod
  
for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
  ans = b * d * fact[a+c]
  ans %= mod
  ans *= fact_inv[a]
  ans %= mod
  ans *= fact_inv[c]
  ans %= mod
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
M = 10 ** 9 + 7
N = int(input())

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

cache = [{} for _ in range(N)]

facts = [1]
facts_i = [1]
def cache_facts(n, M):
	f = 1
	for i in range(1, n + 1):
		f = (f * i) % M
		facts.append(f)
		facts_i.append(calc_inverse(f, M))

# inverse
def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

cache_facts(N, M)

def calc(n):
	
	stack = []
	
	for v in e_table[n]:
		stack.append((v, n))
	
	while stack:
		cur, parent = stack[-1]
		edges = e_table[cur]
		if all(v == parent or cur in cache[v] for v in e_table[cur]):
			stack.pop()
			total_count = 0
			total_p_inv = 1
			total_patterns = 1
			for v in edges:
				if v != parent:
					count, patterns = cache[v][cur]
			
					total_count += count
					total_p_inv = total_p_inv * facts_i[count] % M
					total_patterns = total_patterns * patterns % M
			cache[cur][parent] = (total_count + 1, ((facts[total_count] * total_p_inv) % M) * total_patterns % M)
		else:
			for v in e_table[cur]:
				if not cur in cache[v]:
					stack.append((v, cur))
	
	total_count = 0
	total_p_inv = 1
	total_patterns = 1
	for v in e_table[n]:
		count, patterns = cache[v][n]

		total_count += count
		total_p_inv = total_p_inv * facts_i[count] % M
		total_patterns = total_patterns * patterns % M
	
	return ((facts[total_count] * total_p_inv) % M) * total_patterns % M

for i in range(N):
	print(calc(i))

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2*10**5 + 10
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(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

comInit(max)

####

n = int(input())
neigh = {}
degree = [0]*(n+1)

neigh[0] = {}
for i in range(1,n+1):
    neigh[i] = {0:[-1,-1]}
    neigh[0][i] = [-1,-1]

for _ in range(n-1):
    a,b = map(int, input().split())
    neigh[a][b] = [-1,-1] # 0:num 1:conb
    neigh[b][a] = [-1,-1]
    degree[a] += 1
    degree[b] += 1

# キュー
from collections import deque

remains = set(range(1,n+1))
stack = deque()
stack2 = deque()
tmp = -1
while(len(remains) > 0):
    for i in remains:
        if(degree[i] == 1):
            tmp = i
            break
    remains.remove(i)

    for i in neigh[i].keys():
        if(i in remains):
            stack.appendleft([i, tmp])
            stack2.append([tmp, i])
            degree[i] -= 1
            degree[tmp] -= 1
            break

while(len(stack2) > 0):
    i,j = stack2.pop()
    stack.appendleft([i,j])

for i in range(1,n+1):
    stack.appendleft([0,i])

while(len(stack) > 0):
    parent, child = stack.pop()
    tmp = neigh[parent][child]
    if(tmp[0] != -1):
        continue

    tmp_0 = neigh[0][child]
    tmp_rev = neigh[child][parent]
    if(tmp_0[0] != -1)&(tmp_rev[0] != -1):
        sum_n = tmp_0[0] - tmp_rev[0]
        sum_conb = tmp_0[1] * fac[tmp_rev[0]] % mod
        sum_conb = sum_conb * finv[tmp_0[0] - 1] % mod
        sum_conb = sum_conb * fac[ tmp_0[0] - 1 - tmp_rev[0]] % mod
        sum_conb = sum_conb * pow(tmp_rev[1] ,mod-2,mod) % mod

        neigh[parent][child] = [sum_n, sum_conb]
        continue

    num = []
    conb = 1
    for j in neigh[child].keys():
        if(j == parent)|(j == 0):
            continue

        next = neigh[child][j]
        num.append(next[0])
        conb =  conb * next[1] % mod

    if(len(num)==0):
        neigh[parent][child] = [1,1]
        continue

    sum_n = sum(num)
    conb_next = conb * fac[sum_n] % mod
    for j in num:
        conb_next = conb_next * finv[j] % mod

    neigh[parent][child] = [sum_n + 1, conb_next]
    if(tmp_rev[0] != -1)&(parent != 0):
        sum_0 = sum_n + tmp_rev[0]
        conb_0 = fac[sum_0] * finv[sum_n] * finv[tmp_rev[0]] % mod
        conb_0 = conb_0 * conb_next * tmp_rev[1] % mod
        neigh[0][child] = [sum_0 + 1, conb_0]

for i in range(1,n+1):
    print(neigh[0][i][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def dfs(pv, v):
    global MOD
    for e in edge[v]:
        if e != pv and e not in V[v].keys():
            nc, nvar = dfs(v, e)
            V[v][e] = (nc, nvar)
    childs = 0
    var = 1
    for key in [i for i in V[v].keys() if i != pv]:
        cn, cvar = V[v][key]
        childs += cn
        var *= cvar
        var %= MOD
        var *= invs[cn]
        var %= MOD
    var *= modFacts[childs]
    var %= MOD
    return childs + 1, var


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

modFacts, invs = prepare(N)

V = [{} for _ in range(N)]
for i in range(N):
    dfs(-1, i)


for i in range(N):
    ans = 1
    cnt = 0
    for n, var in V[i].values():
        ans *= var
        ans %= MOD
        ans *= invs[n]
        ans %= MOD
        cnt += n
    ans *= modFacts[cnt]
    print(ans % MOD)

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2*10**5 + 10
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(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

comInit(max)

####

n = int(input())
neigh = {}
degree = [0]*(n+1)

neigh[0] = {}
for i in range(1,n+1):
    neigh[i] = {0:[-1,-1]}
    neigh[0][i] = [-1,-1]

for _ in range(n-1):
    a,b = map(int, input().split())
    neigh[a][b] = [-1,-1] # 0:num 1:conb
    neigh[b][a] = [-1,-1]
    degree[a] += 1
    degree[b] += 1

# キュー
from collections import deque

for i in range(1,n+1):
    stack = deque()
    check = deque()
    check.append([0,i])
    while(len(check) > 0):
        tmp = check.pop()
        stack.append(tmp)
        for j in neigh[tmp[1]].keys():
            if(j!=0)&(j!=tmp[0]):
                check.append([ tmp[1] , j])

    while(len(stack) > 0):
        parent, child = stack.pop()
        tmp = neigh[parent][child]
        if(tmp[0] != -1):
            continue

        tmp_0 = neigh[0][child]
        tmp_rev = neigh[child][parent]
        if(tmp_0[0] != -1)&(tmp_rev[0] != -1):
            sum_n = tmp_0[0] - tmp_rev[0]
            sum_conb = tmp_0[1] * fac[tmp_rev[0]] % mod
            sum_conb = sum_conb * finv[tmp_0[0] - 1] % mod
            sum_conb = sum_conb * fac[ tmp_0[0] - 1 - tmp_rev[0]] % mod
            sum_conb = sum_conb * pow(tmp_rev[1] ,mod-2,mod) % mod

            neigh[parent][child] = [sum_n, sum_conb]
            continue

        num = []
        conb = 1
        for j in neigh[child].keys():
            if(j == parent)|(j == 0):
                continue

            next = neigh[child][j]
            num.append(next[0])
            conb =  conb * next[1] % mod

        if(len(num)==0):
            neigh[parent][child] = [1,1]
            continue

        sum_n = sum(num)
        conb_next = conb * fac[sum_n] % mod
        for j in num:
            conb_next = conb_next * finv[j] % mod

        neigh[parent][child] = [sum_n + 1, conb_next]
        if(tmp_rev[0] != -1)&(parent != 0):
            sum_0 = sum_n + tmp_rev[0]
            conb_0 = fac[sum_0] * finv[sum_n] * finv[tmp_rev[0]] % mod
            conb_0 = conb_0 * conb_next * tmp_rev[1] % mod
            neigh[0][child] = [sum_0 + 1, conb_0]

    print(neigh[0][i][1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

mod = 10 ** 9 + 7
N = 1000000

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

n = int(input())

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

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre):
    if E[cur] == [pre]:
        memo[cur] = [1, 1]
        return 1, 1
    ns = []
    cnt = 1
    for e in E[cur]:
        if e != pre:
            ni, cnti = dfs(e, cur)
            ns.append(ni)
            cnt = cnt * cnti % mod
    s = sum(ns)
    S = s
    for ni in ns:
        cnt = cnt * cmb(s, ni) % mod
        s -= ni
    memo[cur] = [S+1, cnt]
    return S+1, cnt

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

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(2 * 10 ** 5 + 1)

MOD = 10**9 + 7

N, = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(N - 1)]

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)


@lru_cache(maxsize=None)
def fact(n):
    if n <= 1:
        return 1
    return n * fact(n - 1) % MOD


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


@lru_cache(maxsize=None)
def brute(node, parent=None):
    counts = []
    ways = 1
    for nbr in graph[node]:
        if nbr != parent:
            childCount, childWays = brute(nbr, node)
            counts.append(childCount)
            ways *= childWays

    ways *= fact(sum(counts))
    for c in counts:
        ways *= modInverse(fact(c), MOD)

    return 1 + sum(counts), ways % MOD


for i in range(1, N + 1):
    print(brute(i)[1])

Submission status: Time Limit Exceeded

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

N = int(input())
G = [[] for _ in range(N)]
for _ 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
fact = [1] * N
fact_inv = [1] * N
inv = lambda x : pow(x, mod-2, mod)
for i in range(1, N):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = inv(fact[i])
comb = lambda n, k : fact[n] * fact_inv[k] * fact_inv[n-k] % mod

value = [1] * N
count = [0] * N
def dfs(par, v):
    for u in G[v]:
        if par == u:
            continue
        dfs(v, u)
        count[v] += count[u]
        value[v] = value[v] * value[u] * comb(count[v], count[u]) % mod
    count[v] += 1

ans = [0] * N
def reroot(par, val_par, cnt_par, v):
    ans[v] = val_par * value[v] * comb(N-1, cnt_par) % mod
    for u in G[v]:
        if par == u:
            continue
        val = ans[v] * inv(value[u] * comb(N-1, count[u])) % mod
        reroot(v, val, N-count[u],  u)

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

Submission status: Time Limit Exceeded

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 = (2*10**5)
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)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

vs = set([1])
stack = [1]
vs_bfs = list()
parents = [0] * (N+1)
while stack:
    v = stack.pop()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        stack.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 d[v]:
        if u == parents[v]:
            continue
        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

for v in vs_bfs:
    if v == 1:
        continue
    p = parents[v]
    dp1[v] = mul(
            div(dp1[p], cmb(N-1, sss[v], mod)),
            cmb(N-1, N-sss[v], mod))

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

Submission status: Time Limit Exceeded

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

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

mod = 10**9+7
fact = [1] * (N+1)
fact_inv = [1] * (N+1)
inv = lambda x : pow(x, mod-2, mod)
for i in range(1, N+1):
    fact[i] = i * fact[i-1] % mod
    fact_inv[i] = inv(fact[i])
comb = lambda n, k : fact[n] * fact_inv[k] * fact_inv[n-k] % mod

value = [0] * (N+1)
count = [0] * (N+1)
def dfs1(par, v):
    value[v] = 1
    count[v] = 0
    for u in G[v]:
        if par == u:
            continue
        dfs1(v, u)
        count[v] += count[u]
        value[v] = value[v] * value[u] * comb(count[v], count[u]) % mod
    count[v] += 1

ans = [0] * (N+1)
def dfs2(par, val_par, cnt_par, v):
    val = val_par * value[v] * comb(N-1, cnt_par) % mod
    ans[v] = val
    for u in G[v]:
        if par == u:
            continue
        val2 = val * inv(value[u]) * inv(comb(N-1, count[u])) % mod
        dfs2(v, val2, N-count[u],  u)

dfs1(0, 1)
dfs2(0, 1, 0, 1)

print(*ans[1:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
edges = []
for i in range(N-1):
    edges.append(list(map(int, input().split())))

# 各頂点と隣接する頂点を予めdictにいれておく
dic = {i:set() for i in range(1,N+1)}
for edge in edges:
    i = edge[0]
    j = edge[1]
    dic[i].add(j)
    dic[j].add(i)

def calc(black, white, can_black):
    if len(can_black) == 0:
        return 1
    ret = 0
    for c in can_black:
        # 塗りつぶしたのでblackに加える
        next_black = set(black)
        next_black.add(c)
        # 塗りつぶすので、whiteから除く
        next_white = set(white)
        next_white.remove(c)
        # 塗りつぶしたので、can_blackから除く
        next_can_black = set(can_black)
        next_can_black.remove(c)
        # 増えた塗りつぶし候補点を追加
        next_can_black |= dic[c]
        next_can_black -= black
        
        ret += calc(next_black, next_white, next_can_black)
    return ret




for i in range(1,N+1):
    black = set() # 現在の黒点
    white = {i for i in range(1,N+1)} # 現在の白点
    can_black = set() # 黒く塗りつぶせる点
    can_black.add(i)
    print(calc(black, white, can_black))

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc160/tasks/abc160_f

全方位木dpの実装はどうしよう？
まず0について求め、必要な値を取っておいて、親に近い方から親の値を使って求める
がよさそう


かけるべきは、 N-1 C (N-小部分木に含まれる頂点数) * 親の答え // (小部分木のmu* N-1C小部分木の頂点数)
"""
import sys
sys.setrecursionlimit(10 ** 6)

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)



#modのn!と、n!の逆元を格納したリストを返す(拾いもの)
#factorialsには[1, 1!%mod , 2!%mod , 6!%mod… , n!%mod] が入っている
#invsには↑の逆元が入っている

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv
    return factorials, invs


def modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod


N = int(input())
mod = 10**9+7
fac,inv = modfac(N,mod)

lis = [ [] for i in range(N)]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

plis = [i for i in range(N)]
chnum = [0] * N
mulis = [0] * N

def dfs(v,p):

    rch = 1
    rmu = 1
    chlis = []

    for nex in lis[v]:

        if nex != p:

            ch,mu = dfs(nex,v)
            rch += ch
            rmu *= mu
            rmu %= mod
            chlis.append(ch)

    nsum = sum(chlis)

    for i in range(len(chlis)):

        rmu *= modnCr(nsum,chlis[i],mod,fac,inv)
        rmu %= mod
        nsum -= chlis[i]

    plis[v] = p
    chnum[v] = rch
    mulis[v] = rmu

    return rch,rmu

ans = [None] * N

temp,ans[0] = dfs(0,0)

#print (plis,chnum,mulis)


def dfs2(v,p):

    #print (v,p)

    if v != 0:
        vn = chnum[v]
        mn = mulis[v]

        ans[v] = ans[p] * modnCr(N-1,N-vn,mod,fac,inv) * inverse( modnCr(N-1,vn,mod,fac,inv) ,mod) % mod
    for nex in lis[v]:
        if nex != p:
            dfs2(nex,v)

dfs2(0,0)
print ("\n".join(map(str,ans)))

Submission status: Time Limit Exceeded

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

mod = 10**9 + 7

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2*10**5 + 10
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(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

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

####

n = int(input())
neigh = {}
degree = [0]*(n+1)

neigh[0] = {}
for i in range(1,n+1):
    neigh[i] = {0:[-1,-1]}
    neigh[0][i] = [-1,-1]

for _ in range(n-1):
    a,b = map(int, input().split())
    neigh[a][b] = [-1,-1] # 0:num 1:conb
    neigh[b][a] = [-1,-1]
    degree[a] += 1
    degree[b] += 1

def calc(parent,child):
    tmp = neigh[parent][child]
    if(tmp[0] != -1):
        return tmp[::]

    tmp_0 = neigh[0][child]
    tmp_rev = neigh[child][parent]
    if(tmp_0[0] != -1)&(tmp_rev[0] != -1):
        # print('hoge2')
        sum_n = tmp_0[0] - tmp_rev[0]
        sum_conb = tmp_0[1] * fac[tmp_rev[0]] % mod
        sum_conb = sum_conb * finv[tmp_0[0] - 1] % mod
        sum_conb = sum_conb * fac[ tmp_0[0] - 1 - tmp_rev[0]] % mod
        sum_conb = sum_conb * pow(tmp_rev[1] ,mod-2,mod) % mod

        neigh[parent][child] = [sum_n, sum_conb]
        return [sum_n, sum_conb]

    num = []
    conb = 1
    for i in neigh[child].keys():
        if(i == parent)|(i == 0):
            continue

        next = calc(child, i)
        num.append(next[0])
        conb =  conb * next[1] % mod


    if(len(num)==0):
        # print('hoge0')
        neigh[parent][child] = [1,1]
        return [1,1]

    sum_n = sum(num)
    conb_next = conb * fac[sum_n] % mod
    for i in num:
        conb_next = conb_next * finv[i] % mod

    neigh[parent][child] = [sum_n + 1, conb_next]
    if(tmp_rev[0] != -1)&(parent != 0):
        # print('hoge3 {} {}'.format(parent, child))
        sum_0 = sum_n + tmp_rev[0]
        conb_0 = fac[sum_0] * finv[sum_n] * finv[tmp_rev[0]] % mod
        conb_0 = conb_0 * conb_next * tmp_rev[1] % mod
        neigh[0][child] = [sum_0 + 1, conb_0]
        # print([sum_0 + 1, conb_0])

    # print('hoge {} {}'.format(parent, child))
    # print(neigh[parent][child][::])
    return neigh[parent][child][::]

for i in range(1,n+1):
    for j in neigh[i].keys():
        if(j != 0):
            # print('ij {} {}'.format(i,j))
            # print(calc(i,j))
            calc(i,j)
    calc(0,i)
    print(neigh[0][i][1])

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys


sys.setrecursionlimit(200000)
LARGE = 10 ** 9 + 7


def solve(n, edge_list):
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        a, b = edge_list[i]
        g[a].append(b)
        g[b].append(a)

    # root 0
    parent = [-1] * n
    parent[0] = 0
    children = [[] for _ in range(n)]
    queue = deque([0])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if parent[q] == -1:
                parent[q] = p
                children[p].append(q)
                queue.append(q)

    # n_children
    count_children_res = [-1] * n

    def count_children(x):
        if count_children_res[x] != -1:
            return count_children_res[x]
        elif len(children[x]) == 0:
            count_children_res[x] = 0
            return 0
        else:
            r = len(children[x]) + sum([count_children(y) for y in children[x]])
            count_children_res[x] = r
            return r

    r0 = count_children(0)

    factorial = [1] * n
    for i in range(1, n):
        factorial[i] = (factorial[i - 1] * i) % LARGE
    factorial_inv = [1] * n
    factorial_inv[-1] = pow(factorial[-1], LARGE - 2, LARGE)
    for i in range(n - 2, 0, -1):
        factorial_inv[i] = (factorial_inv[i + 1] * (i + 1)) % LARGE

    assign_children_res = [-1] * n

    def assign_children(x):
        if assign_children_res[x] != -1:
            return assign_children_res[x]
        elif len(children[x]) == 0:
            assign_children_res[x] = 1
            return 1
        else:
            r = factorial[count_children_res[x]]
            for y in children[x]:
                r *= assign_children(y)
                r *= factorial_inv[count_children_res[y] + 1]
                r %= LARGE
            assign_children_res[x] = r
            return r

    r0 = assign_children(0)

    # all direction
    assign_parents_res = [-1] * n
    assign_parents_res[0] = 1

    def assign_parents(x):
        if assign_parents_res[x] != -1:
            return assign_parents_res[x]
        else:
            r = factorial[n - 2 - count_children_res[x]]
            for y in children[parent[x]]:
                if y == x:
                    continue
                r *= assign_children_res[y]
                r *= factorial_inv[count_children_res[y] + 1]
                r %= LARGE
            # parent
            r *= assign_parents(parent[x])
            r *= factorial_inv[n - count_children_res[parent[x]] - 1]
            r %= LARGE
            assign_parents_res[x] = r
            return r

    for i in range(n):
        r1 = assign_parents(i)
    res_list = [0] * n
    res_list[0] = r0

    for i in range(1, n):
        res = factorial[n - 1]
        # children
        for j in children[i]:
            res *= assign_children_res[j]
            res *= factorial_inv[count_children_res[j] + 1]
            res %= LARGE
        # parent
        res *= assign_parents_res[i]
        res *= factorial_inv[n - 1 - count_children_res[i]]
        res %= LARGE
        res_list[i] = res
    # print(res_list)
    return res_list


def main():
    n = int(input())
    edge_list = []
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge_list.append((a - 1, b - 1))
    res_list = solve(n, edge_list)
    for res in res_list:
        print(res)


def test():
    assert solve(3, [(0, 1), (0, 2)]) == [2, 1, 1]
    assert solve(2, [(0, 1)]) == [1, 1]
    assert solve(5, [(0, 1), (1, 2), (2, 3), (2, 4)]) == [2, 8, 12, 3, 3]
    assert solve(8, [(0, 1), (1, 2), (2, 3), (2, 4), (2, 5), (5, 6), (5, 7)]) == [40, 280, 840, 120, 120, 504, 72, 72]


if __name__ == "__main__":
    # test()
    # solve(10000, [(i, i + 1) for i in range(9999)])
    main()

Submission status: Time Limit Exceeded

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def mkfact(n,R):
    global factary
    factary = [1]*(n+1)
    for i in range(2,n+1):
        factary[i] = (factary[i-1]*i)%R

def comb2(n,a,R):
    return (factary[n] * modinv2(factary[n-a]*factary[a],R))%R

def comb(n,a,R):
    dend = 1
    for i in range(a):
        dend = (dend*(n-i))%R
    sor = 1
    for i in range(2,a+1):
        sor = (sor*i)%R
    return (dend*modinv2(sor,R))%R

import sys,resource
def setrlim():
  sys.setrecursionlimit(250000)
  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
  resource.setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(v,f):
    if f in dp[v]:
        return dp[v][f]
    a = 1
    ms = []
    for u in dst[v]:
        if u==f:
            continue
        mm,z = dfs(u,v)
        a = (a*z)%R
        ms.append(mm)
    k = len(dst[v])
    c = 1
    if len(ms)>1:
        t = sum(ms)
        for m in ms[1:]:
            c = (c*comb2(t,m,R))%R
            t -= m
    ret = (sum(ms)+1, (a*c)%R)
    if f>=0:
        dp[v][f] = ret
    return ret

# # # #
setrlim()
n = inn()
mkfact(2*n+9,R)
dst = [{} for i in range(n)]
for i in range(n-1):
    a,b = inm()
    dst[a-1][b-1] = 1
    dst[b-1][a-1] = 1
dp = [{} for i in range(n)]
for i in range(n):
    z = dfs(i,-1)
    print(z[1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def dfs(v):
    global MOD
    childs = 0
    var = 1
    for e in edge[v]:
        if path[e] == 0:
            path[e] = 1
            nc, nvar = dfs(e)
            childs += nc
            V[v][e] = (nc, nvar)
            var *= nvar
            var %= MOD
            var *= invs[nc]
            var %= MOD
    var *= modFacts[childs]
    var %= MOD
    return childs + 1, var


def dfs2(v, pv, pn, pvar):
    global MOD
    V[v][pv] = (pn, pvar)

    for e in edge[v]:
        if path[e] == 0:
            totalN = 0
            totalVar = 1
            for k in [i for i in V[v].keys() if i != e]:
                n, var = V[v][k]
                totalN += n
                totalVar *= var
                totalVar %= MOD
                totalVar *= invs[n]
                totalVar %= MOD
            totalVar *= modFacts[totalN]
            totalVar %= MOD
            path[e] = 1
            dfs2(e, v, totalN + 1, totalVar)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

modFacts, invs = prepare(N)

V = [{} for _ in range(N)]
path = [0] * N
path[0] = 1
dfs(0)

path = [0] * N
path[0] = 1
dfs2(0, 0, 0, 1)


for i in range(N):
    ans = 1
    cnt = 0
    for n, var in V[i].values():
        ans *= var
        ans %= MOD
        ans *= invs[n]
        ans %= MOD
        cnt += n
    ans *= modFacts[cnt]
    print(ans % MOD)