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:
class Combination():
    def __init__(self, n, mod):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod
    
    def factorial(self, i):
        return self.fac[i]
    
    def invfactorial(self, i):
        return self.invfac[i]


class Rerooting(Combination):
    def __init__(self, adjacent, n, mod):
        super(Rerooting, self).__init__(n, mod)
        self.n = n
        self.adj = adjacent #0-indexedの配列で用意！
        # DFS
        self.order = []
        stack = [0]
        self.parent = [-1]*(n)
        while stack:
            node = stack.pop()
            self.order.append(node)
            for child in self.adj[node]:
                if self.parent[node] == child:
                    continue
                stack.append(child)
                self.parent[child] = node
    
    def merge(self, parent, child):
        # childの値をparentに統合する処理
        self.size[parent] += self.size[child]
        self.dp[parent] *= self.combination(self.size[parent]-1,self.size[child])
        self.dp[parent] %= self.mod
        self.dp[parent] *= self.dp[child]
        self.dp[parent] %= self.mod
        return self.dp[parent]

    def remerge(self, parent, child):
        # childの値が根となるときの統合処理
        self.dp[child] = self.size[child]*self.dp[parent]
        self.dp[child] //= self.n-self.size[child]
        self.dp[child] %= self.mod
        return self.dp[child]

    def calc_subtree(self):
        # 帰りがけ順で木DP
        #根が0の時の値を算出
        self.dp = [1]*(self.n)
        self.size = [1]*(self.n)
        for node in self.order[::-1]:
            if self.parent[node] == -1:
                continue
            self.merge(self.parent[node], node)

    def root_subtree(self):
        # 行きがけ順で
        for node in self.order[1:]:
            p = self.parent[node]
            self.remerge(p, node)
        return self.dp
        

def main():
    import sys
    input = lambda: sys.stdin.buffer.readline().rstrip()
    n = int(input())
    mod = 10**9 + 7
    adj = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)

    r = Rerooting(adj, n, mod)
    r.calc_subtree()
    dp = r.root_subtree()

    for ans in dp:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Combination():
    def __init__(self, n, mod):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod


class Rerooting(Combination):
    def __init__(self, adjacent, n, mod):
        super(Rerooting, self).__init__(n, mod)
        self.n = n
        self.adj = adjacent #0-indexedの配列で用意！
        # DFS
        self.order = []
        stack = [0]
        self.parent = [-1]*(n)
        while stack:
            node = stack.pop()
            self.order.append(node)
            for child in self.adj[node]:
                if self.parent[node] == child:
                    continue
                stack.append(child)
                self.parent[child] = node
    
    def merge(self, parent, child):
        # childの値をparentに統合する処理
        self.size[parent] += self.size[child]
        self.dp[parent] *= self.combination(self.size[parent]-1,self.size[child])
        self.dp[parent] %= self.mod
        self.dp[parent] *= self.dp[child]
        self.dp[parent] %= self.mod
        return self.dp[parent]

    def remerge(self, parent, child):
        # childの値が根となるときの統合処理
        self.dp[child] = self.size[child]*self.dp[parent]
        self.dp[child] //= self.n-self.size[child]
        self.dp[child] %= self.mod
        return self.dp[child]

    def sub(self):
        # 帰りがけ順で木DP
        self.dp = [1]*(self.n)
        self.size = [1]*(self.n)
        for node in self.order[:0:-1]:
            p = self.parent[node]
            self.merge(p, node)

    def resub(self):
        # 行きがけ順で
        for node in self.order[1:]:
            p = self.parent[node]
            self.remerge(p, node)
        return self.dp
        


def main():
    import sys
    input = lambda : sys.stdin.buffer.readline().rstrip()
    n = int(input())
    mod = 10**9 + 7
    adj = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)

    r = Rerooting(adj, n, mod)
    r.sub()
    dp = r.resub()

    for ans in dp:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class Combination():
    def __init__(self, n, mod):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod


class Rerooting(Combination):
    def __init__(self, adjacent, n, mod):
        super(Rerooting, self).__init__(n, mod)
        self.n = n
        self.adj = adjacent
        self.order = []
        stack = [0]
        self.parent = [-1]*(n)
        while stack:
            node = stack.pop()
            self.order.append(node)
            for child in self.adj[node]:
                if self.parent[node] == child:
                    continue
                stack.append(child)
                self.parent[child] = node
    
    def merge(self, parent, child):
        self.dp[parent] *= self.combination(self.size[parent]-1,self.size[child])*self.dp[child]%self.mod 
        return self.dp[parent]

    def remerge(self, parent, child):
        self.dp[child] = (self.size[child]*self.dp[parent])//(self.n-self.size[child])%self.mod
        return self.dp[child]

    def sub(self):
        self.dp = [1]*(self.n)
        self.size = [1]*(self.n)
        for node in self.order[:0:-1]:
            p = self.parent[node]
            self.size[p] += self.size[node]
            self.merge(p, node)

    def resub(self):
        for node in self.order[1:]:
            p = self.parent[node]
            self.remerge(p,node)
        return self.dp
        


def main():
    import sys
    input = lambda : sys.stdin.buffer.readline().rstrip()
    n = int(input())
    mod = 10**9 + 7
    adj = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)

    r = Rerooting(adj, n, mod)
    r.sub()
    dp = r.resub()

    for ans in dp:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class mod_comb():
    def __init__(self, n, mod):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod

def mod_inv(a,p):
    return pow(a,p-2,p)


def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    mod = 10**9 + 7
    adj = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)

    C = mod_comb(n,mod)

    order = []
    stack = [0]
    parent = [-1]*(n)
    while stack:
        node = stack.pop()
        order.append(node)
        for child in adj[node]:
            if parent[node] == child:
                continue
            stack.append(child)
            parent[child] = node
    dp = [1]*(n)
    size = [1]*(n)
    for node in order[:0:-1]:
        p = parent[node]
        size[p] += size[node]
        dp[p] *= C.combination(size[p]-1,size[node])*dp[node]%mod
    
    for node in order[1:]:
        p = parent[node]
        dp[node] = (size[node]*dp[p])//(n-size[node])%mod
    
    for ans in dp:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class mod_comb():
    def __init__(self, n, mod):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod

def mod_inv(a,p):
    return pow(a,p-2,p)


def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    mod = 10**9 + 7
    adj = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)

    C = mod_comb(n,mod)

    order = []
    stack = [0]
    parent = [-1]*(n)
    while stack:
        node = stack.pop()
        order.append(node)
        for child in adj[node]:
            if parent[node] == child:
                continue
            stack.append(child)
            parent[child] = node
    dp = [1]*(n)
    size = [1]*(n)
    for node in order[:0:-1]:
        p = parent[node]
        size[p] += size[node]
        dp[p] *= C.combination(size[p]-1,size[node])*dp[node]%mod
    
    for node in order[1:]:
        p = parent[node]
        dp[node] = ((size[node]*dp[p])//(n-size[node]))%mod
    
    for ans in dp:
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
class mod_comb():
    def __init__(self, n, mod):
        self.mod = mod
        self.fac = [1]*(n+1)
        for i in range(1,n+1):
            self.fac[i] = self.fac[i-1] * i % self.mod
        self.invfac = [1]*(n+1)
        self.invfac[n] = pow(self.fac[n], self.mod - 2, self.mod)
        for i in range(n-1, 0, -1):
            self.invfac[i] = self.invfac[i+1] * (i+1) % self.mod
    
    def combination(self, n, r):
        return self.fac[n] * self.invfac[r] % self.mod * self.invfac[n-r] % self.mod

def mod_inv(a,p):
    return pow(a,p-2,p)


def main():
    import sys
    input = sys.stdin.buffer.readline
    n = int(input())
    mod = 10**9 + 7
    adj = [[] for i in range(n)]
    for i in range(n-1):
        a,b = map(lambda x: int(x)-1, input().split())
        adj[a].append(b)
        adj[b].append(a)

    C = mod_comb(n,mod)

    order = []
    stack = [0]
    parent = [-1]*(n)
    while stack:
        node = stack.pop()
        order.append(node)
        for child in adj[node]:
            if parent[node] == child:
                continue
            stack.append(child)
            parent[child] = node
    dp = [1]*(n)
    size = [1]*(n)
    for node in order[:0:-1]:
        p = parent[node]
        size[p] += size[node]
        dp[p] *= C.combination(size[p]-1,size[node])*dp[node]%mod
    
    for node in order[1:]:
        p = parent[node]
        dp[node] = (size[node]*mod_inv(n-size[node],mod)%mod)*dp[p]%mod
    
    for ans in dp:
        print(ans)


    




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 全方位木DP、葉側と根側
N = ir()
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

MOD = 10 ** 9 + 7

fact = [1] * (N + 10)
for n in range(1, N + 10):
    fact[n] = n * fact[n - 1] % MOD
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

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    cur = stack.pop()
    order.append(cur)
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        stack.append(next)

size_down = [0] * (N+1)  # 1-indexed
dp_down = [1] * (N+1)  # 葉側の組み合わせ
for v in order[::-1]:
    dp_down[v] *= fact[size_down[v]]
    dp_down[v] %= MOD
    p = parent[v]
    s = size_down[v] + 1
    size_down[p] += s
    dp_down[p] *= fact_inv[s] * dp_down[v]
    dp_down[p] %= MOD

size_up = [N-x-1 for x in size_down]  # 自分含めない
dp_up = [1] * (N+1)  # 根側の組み合わせ
for v in order[2:]:
    p = parent[v]
    x = dp_down[p]
    x *= dp_up[p]
    x *= fact_inv[size_down[p]]
    x *= fact[size_down[v] + 1]
    x *= pow(dp_down[v], MOD-2, MOD)
    x %= MOD
    x *= fact[size_up[v]-1]
    x *= fact_inv[size_up[p]]
    dp_up[v] = x % MOD

for xd, xu, sd, su in zip(dp_down[1:], dp_up[1:], size_down[1:], size_up[1:]):
    answer = xd * xu * fact[sd+su] * fact_inv[sd] * fact_inv[su] % MOD
    print(answer % MOD)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(3*10**5)  # 繰り返し制限

# 組み合わせ
N = 2*10**5  # 問題サイズに合わせて変えておく
MOD = 10**9 + 7

def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n-r] % MOD

fac = [1, 1] # 元テーブル
facinv = [1, 1] #逆元テーブル
inv = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    fac.append( ( fac[-1] * i ) % MOD )
    inv.append( ( -inv[MOD % i] * (MOD//i) ) % MOD )
    facinv.append( (facinv[-1] * inv[-1]) % MOD )

# 部分木のDP値を求めていく
# u : 求める頂点
# 親（親側に辿らないように） p

def dfs(u, p = -1):

    # global DP, CN, E
    
    tmp_ans = 1
    tmp_cn = 0  # （自分を含む）部分木のノード数

    # u から出ている頂点 v
    for v in E[u]:
        if v != p:  # 親への辺以外について
            DP[v], CN[v] = dfs(v, u)
            tmp_cn += CN[v]
            tmp_ans *= DP[v] * cmb(tmp_cn, CN[v]) % MOD
    
    DP[u] = tmp_ans
    CN[u] = tmp_cn + 1
            
    return DP[u], CN[u]

# 各頂点の真のDP値を求めていく

def bfs(u, p=-1):
    
    tmp_ans = DP[u]
    tmp_cn = 1
    
    for v in E[u]:  # 各vに対して「真のDP値」を求めていく
        if v == p:
            continue
            
        # DP[u] と DP[v] から DP[v <- u] を求める
        tmp_cn = N - CN[v]  # v から見たときの u の部分木の要素数
        # print(v+1,tmp_cn)
        tmp_ans = DP[u] // DP[v] // cmb(N - 1, CN[v])
                
        # DP[u <- v] を使って、DP[v] を更新する
        DP[v] = DP[v] * tmp_ans * cmb(N-1, tmp_cn) % MOD
        bfs(v, u)
    
    return

# 入力処理
N = int(input())  # 頂点数
E = [[] for _ in range(N)]  # 辺の情報

for _ in range(N - 1):
    a, b = map(int, input().split())
    E[a-1].append(b-1)  # 双方向の情報
    E[b-1].append(a-1)

DP = [1] * N
CN = [0] * N
dfs(0)
bfs(0)

for i in DP:
    print(i)

Submission status: Wrong Answer

Solution code:
def hoge():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))

    from collections import defaultdict
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)


    M = 10**9+7 # 出力の制限
    N = n # 必要なテーブルサイズ

    g1 = [None] * (N+1) # 元テーブル
    g2 = [None] * (N+1) #逆元テーブル
    inverse = [None] * (N+1) #逆元テーブル計算用テーブル
    g1[0] = g1[1] = g2[0] = g2[1] = 1
    inverse[0], inverse[1] = [0, 1] 

    for i in range( 2, N + 1 ):
        g1[i] = ( g1[i-1] * i ) % M 
        inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
        g2[i] = (g2[i-1] * inverse[i]) % M 


    ans = {}
    prevs = {}
    out = [None] * n
    def sub(i, j, prev):
        prevs[i,j] = prev
        if (i,j) in ans:
            return ans[i,j]
        if len(ns[j])==1 and i in ns[j]:
            ans[i,j] = (1, 1)
            return (1, 1)

        count = 1
        sum_size = 0
        for k in ns[j]:
            if k==i:
                continue
            val, size = sub(j, k, i)
            count = (count * val) % M
            count = (count * g2[size]) % M
            sum_size += size
        count = (count * g1[sum_size]) % M
        ans[i,j] = (count, sum_size+1)
        return (count, sum_size+1)

    def sub2(i, j, q):
        for k in ns[j]:
            if k==i:
                continue
            if (k, j) in ans:
                continue
            tmp_count, tmp_size = ans[j, k]
            total_count, total_size = ans[prevs[j, k], j]
            prev_count, prev_size = ans[j, i]
            new_size = total_size - tmp_size + prev_size
            new_count = (total_count * g2[total_size-1] * g1[new_size-1]) % M
            new_count = (new_count * prev_count * pow(tmp_count, M-2, M)) % M
            new_count = (new_count * g2[prev_size] * g1[tmp_size]) % M
            ans[k, j] = (new_count, new_size)
            val = tmp_count
            val = (val * new_count * g1[new_size+tmp_size-1] * g2[tmp_size-1] * g2[new_size]) % M
            out[k] = val
            q.appendleft((j, k))
#             sub2(j, k)
    #         print("total: ", total_count, total_size)
    #         print("tmp: ", tmp_count, tmp_size)
    #         print("prev: ", prev_count, prev_size)
    #         new_count = total_count / g1[total_size-1] * g1[new_size-1] * prev_count / tmp_count / g1[prev_size] * g1[tmp_size]
    #         print(new_count)
    #         print("")

    # 0を始点として木DP
    sub(-1, 0, None)

    ans[0, -1] = (1,0)

    # 逆向きを求める
    from queue import deque
    q = deque()
    q.appendleft((-1, 0))
    while q:
        u, v = q.pop()
        sub2(u, v, q)
    
    u = 0
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] # sub(u, k, None)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    out[0] = count
    return out
hoge()

Submission status: Wrong Answer

Solution code:
def hoge():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))

    from collections import defaultdict
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)


    M = 10**9+7 # 出力の制限
    N = n # 必要なテーブルサイズ

    g1 = [None] * (N+1) # 元テーブル
    g2 = [None] * (N+1) #逆元テーブル
    inverse = [None] * (N+1) #逆元テーブル計算用テーブル
    g1[0] = g1[1] = g2[0] = g2[1] = 1
    inverse[0], inverse[1] = [0, 1] 

    for i in range( 2, N + 1 ):
        g1[i] = ( g1[i-1] * i ) % M 
        inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
        g2[i] = (g2[i-1] * inverse[i]) % M 


    ans = {}
    prevs = {}
    out = [None] * n
    def sub(i, j, prev):
        prevs[i,j] = prev
        if (i,j) in ans:
            return ans[i,j]
        if len(ns[j])==1 and i in ns[j]:
            ans[i,j] = (1, 1)
            return (1, 1)

        count = 1
        sum_size = 0
        for k in ns[j]:
            if k==i:
                continue
            val, size = sub(j, k, i)
            count = (count * val) % M
            count = (count * g2[size]) % M
            sum_size += size
        count = (count * g1[sum_size]) % M
        ans[i,j] = (count, sum_size+1)
        return (count, sum_size+1)

    def sub2(i, j, q):
        for k in ns[j]:
            if k==i:
                continue
            if (k, j) in ans:
                continue
            tmp_count, tmp_size = ans[j, k]
            total_count, total_size = ans[prevs[j, k], j]
            prev_count, prev_size = ans[j, i]
            new_size = total_size - tmp_size + prev_size
            new_count = (total_count * g2[total_size-1] * g1[new_size-1]) % M
            new_count = (new_count * prev_count * pow(tmp_count, M-2, M)) % M
            new_count = (new_count * g2[prev_size] * g1[tmp_size]) % M
            ans[k, j] = (new_count, new_size)
            val = tmp_count
            val = (val * new_count * g1[new_size+tmp_size-1] * g2[tmp_size-1] * g2[new_size]) % M
            out[k] = val
            q.appendleft((j, k))
#             sub2(j, k)
    #         print("total: ", total_count, total_size)
    #         print("tmp: ", tmp_count, tmp_size)
    #         print("prev: ", prev_count, prev_size)
    #         new_count = total_count / g1[total_size-1] * g1[new_size-1] * prev_count / tmp_count / g1[prev_size] * g1[tmp_size]
    #         print(new_count)
    #         print("")

    # 0を始点として木DP
    sub(-1, 0, None)

    ans[0, -1] = (1,0)

    # 逆向きを求める
    from queue import deque
    q = deque()
    q.appendleft((-1, 0))
    while q:
        u, v = q.pop()
        sub2(u, v, q)
    
    u = 0
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] # sub(u, k, None)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    out[0] = count
    return out

Submission status: Wrong Answer

Solution code:
def main():
    from sys import stdin
    input=stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    for a, b in ab:
        g[a-1].add(b-1)
        g[b-1].add(a-1)

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    def rerooting(tree, ini):
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # merge:頂点aにbをマージするときのモノイド
            # adj_bu:ボトムアップ時の調整（a:値,i:頂点）
            # adj_td:トップダウン時の調整（a:値,i:頂点,p:親）
            # adj_fin:最終調整（a:値,i:頂点）
            def merge(a, b): return a * b % mod
            def adj_bu(a, i): return a * inv[size[i]] % mod
            def adj_td(a, i, p): return a * inv[n-size[i]] % mod
            def adj_fin(a, i): return a * fact[n-1] % mod

            # トポロジカルソートをする
            # T:木の隣接グラフ表現をset化
            # P:親
            # q:キュー
            # order:トポソしたもの
            T = g
            P = [-1]*n
            q = [0]
            order = []
            while q:
                i = q.pop()
                order.append(i)
                for a in T[i]:
                    if a != P[i]:
                        P[a] = i
                        T[a].remove(i)
                        q.append(a)

            # Tをリストに変換
            T = [list(i) for i in T]

            # サイズの処理を先に行う
            # size[i]:0を根とする根付き木における、iを根とする部分木の大きさ
            size = [1]*n
            for i in order[1:][::-1]:
                size[P[i]] += size[i]

            # ボトムアップ処理をする
            # ME:マージした値を一時保存
            # DP:DP値、MEを調整したもの
            ME = [ini]*n
            DP = [0]*n
            for i in order[1:][::-1]:
                DP[i] = adj_bu(ME[i], i)
                p = P[i]
                ME[p] = merge(ME[p], DP[i])
            DP[order[0]] = adj_fin(ME[order[0]], order[0])
            TD = [ini]*n

            # トップダウン処理をする
            for i in order:
                # 左からDP（結果はTDに入れている）
                ac = TD[i]
                for j in T[i]:
                    TD[j] = ac
                    ac = merge(ac, DP[j])
                # 右からDP（結果はacに入れている、一度しか使わないのでacで問題ない）
                ac = ini
                for j in T[i][::-1]:
                    TD[j] = adj_td(merge(TD[j], ac), j, i)
                    ac = merge(ac, DP[j])
                    DP[j] = adj_fin(merge(ME[j], TD[j]), j)
            for i in DP:
                print(i)

    rerooting(g, 1)


main()

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
from math import factorial

setrecursionlimit(2 * 10 ** 5)

# This cmb func is from https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E3%83%A1%E3%83%AA%E3%83%83%E3%83%88-5
def cmb(n, r):
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n

  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]

  for p in range(2,r+1):
    pivot = denominator[p - 1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p-1,r,p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot

  result = 1
  for k in range(r):
    if numerator[k] > 1:
      result *= int(numerator[k])

  return result

class Node:
  def __init__(self, node_id):
    self.id = node_id
    self.children = []
    self.size = 1

  def add_child(self, node):
    self.children.append(node)

  @staticmethod
  def prepare_nodes(n):
    nodes = tuple([Node(i) for i in range(n)])
    for _ in range(n - 1):
      a, b = sorted(map(lambda x: int(x) - 1, input().split()))
      nodes[a].add_child(nodes[b])

    return nodes


def main():
  n = int(input())
  nodes = Node.prepare_nodes(n)

  dp = [1] * n

  def f(node):
    for child in node.children:
      f(child)
      dp[node.id] *= dp[child.id] * cmb(node.size - 1 + child.size, child.size)
      node.size += child.size

  f(nodes[0])

  def g(node, parent):
    if parent:
      parent_dp = dp[parent.id] // (dp[node.id] * cmb(n - 1, node.size))
      dp[node.id] = dp[node.id] * parent_dp * cmb(n - 1, n - node.size)

    for child in node.children:
      g(child, node)

  g(nodes[0], None)

  print(*map(lambda ans: ans % (10**9 + 7), dp), sep="\n")


main()

Submission status: Wrong Answer

Solution code:
from sys import setrecursionlimit
from math import factorial

setrecursionlimit(2 * 10 ** 5)

# This cmb func is from https://qiita.com/derodero24/items/91b6468e66923a87f39f#%E3%83%A1%E3%83%AA%E3%83%83%E3%83%88-5
def cmb(n, r):
  if n - r < r: r = n - r
  if r == 0: return 1
  if r == 1: return n

  numerator = [n - r + k + 1 for k in range(r)]
  denominator = [k + 1 for k in range(r)]

  for p in range(2,r+1):
    pivot = denominator[p - 1]
    if pivot > 1:
      offset = (n - r) % p
      for k in range(p-1,r,p):
        numerator[k - offset] /= pivot
        denominator[k] /= pivot

  result = 1
  for k in range(r):
    if numerator[k] > 1:
      result *= int(numerator[k])

  return result

class Node:
  def __init__(self, node_id):
    self.id = node_id
    self.children = []
    self.size = 1

  def add_child(self, node):
    self.children.append(node)

  @staticmethod
  def prepare_nodes(n):
    nodes = tuple([Node(i) for i in range(n)])
    for _ in range(n - 1):
      a, b = sorted(map(lambda x: int(x) - 1, input().split()))
      nodes[a].add_child(nodes[b])

    return nodes


def main():
  n = int(input())
  nodes = Node.prepare_nodes(n)

  dp = [1] * n

  def f(node):
    for child in node.children:
      f(child)
      dp[node.id] *= dp[child.id] * cmb(node.size - 1 + child.size, child.size)
      node.size += child.size

  f(nodes[0])

  def g(node, parent):
    if parent:
      parent_dp = dp[parent.id]
      parent_dp = parent_dp // (dp[node.id] * cmb(n - 1, node.size))

      dp[node.id] *= parent_dp * cmb(n - 1, n - node.size)

    for child in node.children:
      g(child, node)

  g(nodes[0], None)

  for ans in dp:
    print(ans % (10**9 + 7))


main()

Submission status: Wrong Answer

Solution code:
import sys

F = 2*10**5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

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

stack=[0]
order=[0]
parent=[0]*n
while stack:
    node = stack.pop()
    for child in neighbers[node]:
        if child==parent[node]:
            continue
        stack.append(child)
        order.append(child)
        parent[child]=node

# (size,combination)
upinfo=[(0,1)]*n
downinfo=[(0,1)]*n

for node in order[::-1]:
    if len(neighbers[node])==1:
        downinfo[node]=(1,1)
    else:
        totalsize=0
        totalcomb=1
        for child in neighbers[node]:
            if child == parent[node]:
                continue
            size,comb=downinfo[child]
            totalsize+=size
            totalcomb=(totalcomb*comb)%mod
            totalcomb=(totalcomb*inv[size])%mod
        totalcomb=(totalcomb*fact[totalsize])%mod
        downinfo[node]=(totalsize+1,totalcomb)
for node in order[1:]:
    totalsize=0
    totalcomb=1
    for brother in neighbers[parent[node]]:
        if brother == node:
            continue
        size,comb=upinfo[parent[node]] if brother == parent[parent[node]] else downinfo[brother]
        totalsize+=size
        totalcomb=(totalcomb*comb)%mod
        totalcomb=(totalcomb*inv[size])%mod
    totalcomb=(totalcomb*fact[totalsize])%mod
    upinfo[node]=(totalsize+1,totalcomb)
for node in order:
    totalsize=0
    totalcomb=1
    for child in neighbers[node]:
        size,comb=upinfo[node] if child==parent[node] else downinfo[child]
        totalsize+=size
        totalcomb=(totalcomb*comb)%mod
        totalcomb=(totalcomb*inv[size])%mod
    totalcomb=(totalcomb*fact[totalsize])%mod
    print(totalcomb)