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: Wrong Answer

Solution code:
# coding: utf-8
DATA = """
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = [int(i) for i in get_line().strip().split(" ")][0]

m = {i:[] for i in range(N)}

for _ in range(N-1):
	a, b = [int(i) for i in get_line().strip().split(" ")]
	a -= 1
	b -= 1

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

memo = {}
count = 0
# def Calc(f):
# 	mul = 1
# 	s = 0
# 	if (f, tuple(m[f])) in memo:
# 		return memo[f, tuple(m[f])]
# 	global count
# 	count += 1
# 	for t in m[f]:
# 		m[t].remove(f)
# 		dummy = Calc(t)
# 		s += dummy[0] + 1
# 		mul *= dummy[1] * (dummy[0] + 1)
# 		m[t].append(f)
# 	memo[f, tuple(m[f])] = (s, mul)
# 	return s, mul

def Calc(f):
	ret = [(f, m[f])]
	size = len(ret)
	for f, mm in ret:
		for t in mm:
			copy = m[t].copy()
			copy.remove(f)
			ret.append((t, copy))

	mm = [1] * N
	for i in range(len(ret)-1, -1, -1):
		a, b = ret[i]
		if len(b) == 0:
			mm[a] = 1
			continue
		
		for i in b:
			mm[a] += mm[i]
	mm.sort(reverse=True)

P = 1
MOD = 10 ** 9 + 7

for i in range(N):
	Calc(i)
	#print (P // mul, (P // mul) % 19, (P%19) // (mul%19))
	#print((P//mul) % MOD)
#print (count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
DATA = """
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = [int(i) for i in get_line().strip().split(" ")][0]

m = {i:[] for i in range(N)}

for _ in range(N-1):
	a, b = [int(i) for i in get_line().strip().split(" ")]
	a -= 1
	b -= 1

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

memo = {}
count = 0
def Calc(f):
	mul = 1
	s = 0
	if (f, tuple(m[f])) in memo:
		return memo[f, tuple(m[f])]
	global count
	count += 1
	for t in m[f]:
		m[t].remove(f)
		dummy = Calc(t)
		s += dummy[0] + 1
		mul *= dummy[1] * (dummy[0] + 1)
		m[t].append(f)
	memo[f, tuple(m[f])] = (s, mul)
	return s, mul

P = 1
for i in range(1,N):
	P *= i

MOD = 10 ** 9 + 7

# for i in range(N):
# 	sum, mul = Calc(i)
# 	#print (P // mul, (P // mul) % 19, (P%19) // (mul%19))
# 	print((P//mul) % MOD)
# #print (count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
DATA = """
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = [int(i) for i in get_line().strip().split(" ")][0]

m = {i:[] for i in range(N)}

for _ in range(N-1):
	a, b = [int(i) for i in get_line().strip().split(" ")]
	a -= 1
	b -= 1

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

memo = {}
count = 0
def Calc(f):
	mul = 1
	s = 0
	if (f, tuple(m[f])) in memo:
		return memo[f, tuple(m[f])]
	global count
	count += 1
	for t in m[f]:
		m[t].remove(f)
		dummy = Calc(t)
		s += dummy[0] + 1
		mul *= dummy[1] * (dummy[0] + 1)
		m[t].append(f)
	memo[f, tuple(m[f])] = (s, mul)
	return s, mul

import functools 
P = functools.reduce(lambda x, y: x * y, range(1, N), 1)

MOD = 10 ** 9 + 7

# for i in range(N):
# 	sum, mul = Calc(i)
# 	#print (P // mul, (P // mul) % 19, (P%19) // (mul%19))
# 	print((P//mul) % MOD)
# #print (count)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
DATA = """
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = [int(i) for i in get_line().strip().split(" ")][0]

m = {i:[] for i in range(N)}

for _ in range(N-1):
	a, b = [int(i) for i in get_line().strip().split(" ")]
	a -= 1
	b -= 1

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

memo = {}
count = 0
def Calc(f):
	mul = 1
	s = 0
	if (f, tuple(m[f])) in memo:
		return memo[f, tuple(m[f])]
	global count
	count += 1
	for t in m[f]:
		m[t].remove(f)
		dummy = Calc(t)
		s += dummy[0] + 1
		mul *= dummy[1] * (dummy[0] + 1)
		m[t].append(f)
	memo[f, tuple(m[f])] = (s, mul)
	return s, mul

import functools 
#P = functools.reduce(lambda x, y: x * y, range(1, N), 1)
P = 1
MOD = 10 ** 9 + 7

#for i in range(N):
#	sum, mul = Calc(i)
#	#print (P // mul, (P // mul) % 19, (P%19) // (mul%19))
#	print((P//mul) % MOD)
##print (count)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
class Tree:
  C, RL = {}, {}
  R, N, D, S, P, T = None, None, None, None, None, None
  TL = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N #各ノードのランク
    s.R[root] = 1
    s.RL[1] = [root] #各ランクのノード
    s.S = {} #各ノードの子ノード
    s.P = [-1] * s.N #各ノードの親ノード
    s.D = 1
    while s.RL[s.D] != []:
      s.D += 1
      s.RL[s.D] = []
      for i in s.RL[s.D - 1]:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            s.RL[s.D].append(j)
            if i not in s.S: s.S[i] = [j]
            else: s.S[i].append(j)
            s.P[j] = i      
  def bottomUpDP(s):
    print(s.RL)
    for i in range(s.D - 2, 0, -1):
      T = s.RL[i]
      for j in T:
        if j not in s.S: continue
        for k in s.S[j]:
          s.dp_sub_exe(j, k)
  def topDownDP(s):
    for i in range(2, s.D):
      T = s.RL[i]
      for j in T:
        s.dp_sub_exe_inv(j, s.P[j])
  def allDP(s):
    s.dp_init()
    s.bottomUpDP()
    s.topDownDP()
    return s.DP
  def dp_init(s): #単位元で初期化
    s.DP = [1] * N
    s.sDP = [1] * N
  def dp_sub_exe(s, x, y): #ボトムアップの処理
    s.sDP[x] += s.sDP[y]
    s.DP[x] = s.DP[x] * s.DP[y] * com.com(s.sDP[x] - 1, s.sDP[y]) % MOD
  def dp_sub_exe_inv(s, x, y): #トップダウンの処理
    t = com.com(s.sDP[y] - 1, s.sDP[x]) * s.DP[x] % MOD
    t = s.DP[y] * s.inv(t, MOD)
    k = s.sDP[y] - s.sDP[x]
    k = com.com(s.sDP[y] - 1, k) % MOD
    s.sDP[x] = s.sDP[y]
    s.DP[x] = s.DP[x] * t * k % MOD
  def inv(s, a, mod): #逆元
    return pow(a, mod - 2, mod)
  
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

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

MOD = 10 ** 9 + 7
com = comb(N, MOD)

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

T.makeRank(0)
DP = T.allDP()

for i in DP:
  print(i)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(200010)

mod = 1000000007

def pow_mod(x, y):
    res = 1
    while y > 0:
        if y % 2:
            res *= x
            res %= mod
        x *= x
        x %= mod
        y //= 2
    return res


def inverse(x):
    return pow_mod(x, mod-2)

N = int(input())
E = []
for i in range(N):
    E.append([])
for i in range(N-1):
    a, b = list(map(int, input().split()))
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)
kai = [1] * (N+1)
fkai = [1] * (N+1)

for i in range(N):
    kai[i+1] = kai[i] * (i+1) % mod

fkai[N] = inverse(kai[N])

for i in range(N-1, 0, -1):
    fkai[i] = fkai[i+1] * (i+1) % mod

child = [0] * N
dp = [0] * N
ans = [0] * N

def dfs1(now, par):
    res = 1
    for to in E[now]:
        if to == par:
            continue
        res += dfs1(to, now)
    child[now] = res
    return res

def dfs2(now, par):
    res = kai[child[now]-1]
    for to in E[now]:
        if to == par:
            continue
        res *= fkai[child[to]]
        res %= mod
        res *= dfs2(to, now)
        res %= mod
    dp[now] = res
    return res

def dfs3(now, par):
    print(now, par, dp)
    ans[now] = dp[now]
    seki = 1
    for to in E[now]:
        if to == par:
            continue
        seki *= dp[to]
        seki %= mod
    for to in E[now]:
        if to == par:
            continue
        m_now = dp[now]
        m_to = dp[to]
        m_c_now = child[now]
        m_c_to = child[to]
        dp[now] *= kai[N-1-child[to]] * kai[child[to]] % mod * fkai[N-1] % mod * inverse(dp[to]) % mod
        dp[now] %= mod
        dp[to] *= kai[N-1] * dp[now] % mod * fkai[N-child[to]] % mod * fkai[child[to]-1] % mod
        dp[to] %= mod
        child[now] -= child[to]
        child[to] = N
        dfs3(to, now)
        dp[now] = m_now
        dp[to] = m_to
        child[now] = m_c_now
        child[to] = m_c_to

dfs1(0, -1)
dfs2(0, -1)
dfs3(0, -1)

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

Submission status: Wrong Answer

Solution code:
n = int(input())
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

# 前準備
import sys
input = sys.stdin.readline
from collections import deque

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

def calc(a,b):
    p_a, e_a = a
    p_b, e_b = b
    e = e_a + e_b
    p = p_a * p_b * com(e,e_a) % mod
    return(p,e)

# calc1 の定義
def calc1(c,p):
    p_num, e_num = 1,0
    for i in graph[c]:
        if i == p:
            continue
        p_num,e_num = calc((p_num, e_num) , dp1[i] )
    e_num += 1
    dp1[c] = (p_num, e_num)

# calc2 の定義
def calc2(p):
    # if(len(graph[p])==1):
    #     neigh = graph[p][0]
    #     p_tmp,e_tmp = dp2[p]
    #     if( neigh != parent[p]):
    #         dp2[neigh] = (p_tmp,e_tmp+1)
    #     return None

    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [(1,0)]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [(1,0)]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        p_tmp,e_tmp = calc(a,b)
        prod.append( (p_tmp, e_tmp) )


    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            p_tmp,e_tmp = x
            dp2[c] = (p_tmp,e_tmp+1)



# 根から探索して親と探索順を記録
root = 1
order = []
parent = [0] * (n+1)
stack = deque()
stack.append(root)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        stack.append(y)
        parent[y] = x

# 親→子の値を算出
dp1 = [None] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])

print(dp1)

# 子→親の値を算出　累積和チックにすることでうに対策。
dp2 = [None] * (n+1)
dp2[root] = (1,0)
for i in order:
    calc2(i)

for i in range(1,n+1):
    p1,e1 = dp1[i]
    p2,e2 = dp2[i]
    e1 -= 1
    ans = calc((p1,e1), (p2,e2))[0]
    print(ans)

Submission status: Wrong Answer

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

Q = 10**9+7

def subtrees(N, E, v):
    # N: vertex
    # E: edges
    # v: one vertex
    # return: directed edges adopted to tree dp
    from collections import deque
    ret_first = deque()
    ret_second = deque()
    V = [False]*N
    d = deque([v])
    while d:
        t = d.popleft()
        if V[t]:
            continue
        else:
            V[t] = True
        for e in E[t]:
            if not V[e]:
                d.append(e)
                ret_first.appendleft((t,e))
                ret_second.append((e,t))
    return list(ret_first) + list(ret_second)

# def get_number_of_vertex_with_subtrees(E, subtrees):
#     # E: edges
#     # subtrees: directed edges adopted to tree dp
#     from collections import defaultdict
#     d = defaultdict( lambda: 1)
#     for s, t in subtrees:
#         for v in E[t]:
#             if v == s:
#                 continue
#             d[(s,t)] += d[(t,v)]
#     return d

def getInv(N):
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

def factorials(N):
    invs = getInv(N)
    factorials = [1]
    inv_factorials = [1]
    for i in range(N):
        factorials.append( factorials[-1]*(i+1)%Q)
        inv_factorials.append( inv_factorials[-1]*invs[i+1]%Q)
    return factorials, inv_factorials

def main():
    from collections import defaultdict
    N = int( input())
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map( lambda x: int(x)-1, input().split())
        E[a].append(b)
        E[b].append(a)
    subtree = subtrees(N,E,0)
    # num_subtree = get_number_of_vertex_with_subtrees(E, subtree)
    num_subtree = defaultdict( lambda: 1)
    F, G = factorials(N)
    d = defaultdict( int)
    for s, t in subtree:
        z = 1
        count = 0
        for v in E[t]:
            if v == s:
                continue
            d[(s,t)] += d[(t,v)]
            count += num_subtree[(t,v)]
            z *= G[num_subtree[(t,v)]]
            z %= Q
            z *= d[(t,v)]
            z %= Q
        z *= F[count]
        z %= Q
        d[(s,t)] = z
    ANS = []
    for v in range(N):
        z = 1
        count = 0
        for e in E[v]:
            count += num_subtree[(v,e)]
            z *= G[num_subtree[(v,e)]]
            z %= Q
            z *= d[(v,e)]
            z %= Q
        z *= F[count]
        z %= Q
        ANS.append(z)

    print( "\n".join( map( str, ANS)))
    
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

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

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

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

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

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

Submission status: Wrong Answer

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

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

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

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

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

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

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

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

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

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

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

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

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

    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

if False:
    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])

AX = [1] * N
prep = -1
for i in R[1:]:
    p = P[i]
    if p != prep:
        ac = unit
    AX[i] = ac
    ac = f(ac, BU[i])

    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: Wrong Answer

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] = 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: Wrong Answer

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[k] = ac
        ac = f(ac, BU[j])
    ac = unit
    for k in range(c-1, 0, -1):
        j = X[i][k]
        AX[k] = f(AX[k], ac)
        ac = f(ac, BU[j])
    for k, j in enumerate(X[i]):
        TD[j] = g_td(f(TD[i], AX[k]), j)

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

Submission status: Wrong Answer

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] * N
dat = [zero] * N
rev_data = [zero] * 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()