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:
n = int(input()); arr = [list(map(int,input().split())) for _ in range(n-1)]
graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1);graph[b-1].append(a-1)

mod = 10**9+7
fac = [1]*(n+1)
inv = [1]*(n+1)
ifac = [1]*(n+1)
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = (- (mod//i)*inv[(mod%i)]) % mod
    ifac[i] = ifac[i-1] * inv[i] % mod

parents = [-1]*n
children = [[] for _ in range(n)]
orders = []
stack = [0]
flags = [True] * n; flags[0] = False
while stack:
    tmp = stack.pop()
    orders.append(tmp)
    for node in graph[tmp]:
        if flags[node]:
            flags[node] = False
            children[tmp].append(node)
            stack.append(node)
            parents[node] = tmp

size = [1] * (n+1)
dp = [1] * (n+1)    
for child in orders[::-1]:
    parent = parents[child]
    size[parent] += size[child]
    dp[child] = dp[child] * fac[size[child]-1] % mod
    dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
_ = size.pop();_ = dp.pop()

size2 = [n-i+1 for i in size]
dp2 = [1] * n
for parent in orders[1:]:
    child = parents[parent]
    dp2[parent] = dp2[parent] * fac[size2[parent]-2] * dp2[child] * ifac[size2[child]-1] * dp[child] * ifac[size[child]-1] * pow(dp[parent], mod-2, mod) * fac[size[parent]] % mod

for i in range(n):
    print(fac[n-1]*dp[i]*ifac[size[i]-1]*dp2[i]*ifac[size2[i]-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
class treedp_rerooting():
    def __init__(self, N, V, MOD):
        self.N = N
        self.V = V
        self.mod = MOD
        self.rep = [0] * N
        self.children = [-1] * N
        self.A = [0] * N
        self.C = combination(N, MOD)
        return

    # 子の数のカウント
    def dfs(self, s):
        size = 1
        nowchild = []
        cur = 1
        self.children[s] = 0
        for i in self.V[s]:
            if self.children[i] != -1:
                continue
            ns, nc = self.dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= self.mod
        self.children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= self.C.comb(rest, k)
            rest -= k
            cur %= self.mod
        self.A[s] = cur
        return size, cur

    def dfs2(self, s, p=-1):
        cur = 1
        rest = self.N - 1
        for to in self.V[s]:
            cur *= self.A[to]
            cur %= self.mod
        for to in self.V[s]:
            cur *= self.C.comb(rest, self.children[to])
            rest -= self.children[to]
            cur %= self.mod
        self.rep[s] = cur

        n = len(self.V[s])
        L = [0] * n; R = [0] * n
        L2 = [0] * n; R2 = [0] * n

        for i, ne in enumerate(self.V[s]):
            L[i] = R[i] = self.A[ne] * self.C.inv[self.children[ne]] % self.mod
            L2[i] = R2[i] = self.children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= self.mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= self.mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(self.V[s]):
            if ne == p:
                continue
            self.A[s] = 1
            self.children[s] = 1
            if i > 0:
                self.A[s] *= L[i - 1]
                self.A[s] %= self.mod
                self.children[s] += L2[i - 1]
            if i + 1 < n:
                self.A[s] *= R[i + 1]
                self.A[s] %= self.mod
                self.children[s] += R2[i + 1]
            self.A[s] *= self.C.fac[self.N - self.children[ne] - 1]
            self.A[s] %= self.mod
            self.dfs2(ne, s)
        return

class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

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

def ABC160():
    N = I()
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    dp_r = treedp_rerooting(N,V,mod)
    dp_r.dfs(0)
    dp_r.dfs2(0)

    ans = dp_r.rep

    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160()

"""
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
"""

# 40
# 280
# 840
# 120
# 120
# 504
# 72
# 72

Submission status: Time Limit Exceeded

Solution code:
def ABC67_B():
    N, K = LI()
    L = LI()
    L.sort(reverse=True)
    ans = sum(L[:K])
    print(ans)
    return

def ABC100_C():
    def factorization_2(n):
        arr = defaultdict(int)
        temp = n
        i = 2
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr[2]
    N = I()
    A = LI()
    ans = 0
    for a in A:
        ans += factorization_2(a)
    print(ans)
    return

def ARC68_C():
    X = I()
    ans = 0
    ans += 2*(X//11)
    rest = X%11
    if rest>0:
        ans += 1
    if rest>=7:
        ans += 1
    print(ans)
    return

def ABC49_C():
    S = SI()
    T = {"maerd","remaerd","esare","resare"}
    stack = ""
    for s in S[::-1]:
        stack += s
        if stack in T:
            stack = ""
    if stack:
        print("NO")
    else:
        print("YES")
    return

def ABC142_E():
    N, M = LI()
    A = [0]*M
    C = [[]for _ in range(M)]
    for i in range(M):
        A[i], b = LI()
        C[i] = LI()
    mask = 2**N
    dp = [[inf]*mask for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        key = 0
        for j in C[i]:
            key += 2**(j-1)
        #print(key)
        for now in range(mask):
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][now])
            if key|now==now:
                continue
            dp[i+1][now|key] = min(dp[i+1][now|key],dp[i][now]+A[i])
    if dp[M][mask-1]==inf:
        print(-1)
    else:
        ans = dp[M][mask-1]
        print(ans)
    #print(dp)
    return

def ABC160_F():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

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

    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    C = combination(N,mod)
    children = [-1] * N
    A = [0] * N
    rep = [0] * N
    
    def dfs(s):
        size = 1
        nowchild = []
        cur = 1
        children[s] = 0
        for i in V[s]:
            if children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= mod
        children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= C.comb(rest, k)
            rest -= k
            cur %= mod
        A[s] = cur
        return size, cur

    def dfs2(s, p=-1):
        cur = 1
        rest = N - 1
        for to in V[s]:
            cur *= A[to]
            cur %= mod
        for to in V[s]:
            cur *= C.comb(rest, children[to])
            rest -= children[to]
            cur %= mod
        rep[s] = cur

        n = len(V[s])
        L = [0] * n; R = [0] * n
        L2 = [0] * n; R2 = [0] * n

        for i, ne in enumerate(V[s]):
            L[i] = R[i] = A[ne] * C.inv[children[ne]] % mod
            L2[i] = R2[i] = children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(V[s]):
            if ne == p:
                continue
            A[s] = 1
            children[s] = 1
            if i > 0:
                A[s] *= L[i - 1]
                A[s] %= mod
                children[s] += L2[i - 1]
            if i + 1 < n:
                A[s] *= R[i + 1]
                A[s] %= mod
                children[s] += R2[i + 1]
            A[s] *= C.fac[N - children[ne] - 1]
            A[s] %= mod
            dfs2(ne, s)
        return

    dfs(0)
    dfs2(0)

    for ans in rep:
        print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160_F()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(int(2e5))

MOD = 10**9 + 7
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD

memo = {}


def query(adj, pos, prev):
    # returns (pattern, count)
    # print("q", pos, prev)
    if (pos, prev) in memo:
        return memo[(pos, prev)]
    if len(adj[pos]) == 1 and prev in adj[pos]:
        memo[(pos, prev)] = (1, 1)
    else:
        pattern = 1
        count = 0
        for nxt in adj[pos]:
            if nxt == prev:
                continue
            ptn, cnt = query(adj, nxt, pos)
            count += cnt
            pattern = (pattern * ptn) % MOD
            pattern = (((pattern * FACT[count]) % MOD)
                       * ((INV[cnt] * INV[count-cnt]) % MOD)) % MOD
        count += 1
        memo[(pos, prev)] = (pattern, count)
    return memo[(pos, prev)]


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    for i in range(N):
        pattern, count = query(adj, i, -1)
        print(pattern)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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
            num_subtree[(s,t)] += num_subtree[(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: Time Limit Exceeded

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

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

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

class ReRooting:
    """
    0-indexed
    """
    def __init__(self, size, root=0, identDp=1, identCum=1):
        """
        identDp: 木DP用 lift(a, identDp) = a
        identCum: 累積用 merge(a, identCum) = a
        """
        self.size = size
        self.edges = [[] for _ in range(self.size + 1)]
        self.root = root
        self.identDp = identDp
        self.identCum = identCum

    def addEdge(self, fr, to):
        self.edges[fr].append(to)
        self.edges[to].append(fr)

    # 根を固定したときの木DP(貰うDP)
    def lift(self, top, bottom):
        newSize = top[1] + bottom[1] + 1
        dp = top[0] * bottom[0] * comb.ncr(newSize, bottom[1] + 1)
        return (dp, newSize)

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

    def sol(self):
        N = self.size
        edges = self.edges

        st = [self.root]
        parent = [-1] * (N + 1)
        child = [[] for _ in range(N + 1)]
        order = []
        while st:
            v = st.pop()
            order.append(v)
            for to in edges[v]:
                if parent[v] == to:
                    continue
                parent[to] = v
                child[v].append(to)
                st.append(to)

        dp = [self.identDp] * (N + 1)
        left = [self.identCum] * (N + 1)
        right = [self.identCum] * (N + 1)
        for v in order[::-1]:  # 貰うDPしつつ，累積をとる
            tmp = self.identCum
            for ch in child[v]:
                left[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            tmp = self.identCum
            for ch in reversed(child[v]):
                right[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            dp[v] = tmp

        fromParent = [self.identDp] * (N + 1)
        for v in order:
            if v == self.root:
                continue
            fromParent[v] = self.lift(self.merge(left[v], right[v]), fromParent[parent[v]])
            dp[v] = self.lift(dp[v], fromParent[v])  # 最後に親からの貰うDP

        return dp[:N]

N = int(input())
tree = ReRooting(N, 0, (1, -1), (1, 0))
comb = Combination(N + 100)

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

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

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

class ReRooting:
    """
    0-indexed
    """
    def __init__(self, size, root=0, identDp=1, identCum=1):
        """
        identDp: 木DP用 lift(a, identDp) = a
        identCum: 累積用 merge(a, identCum) = a
        """
        self.size = size
        self.edges = [[] for _ in range(self.size + 1)]
        self.root = root
        self.identDp = identDp
        self.identCum = identCum

    def addEdge(self, fr, to):
        self.edges[fr].append(to)
        self.edges[to].append(fr)

    # 根を固定したときの木DP(貰うDP)
    def lift(self, top, bottom):
        newSize = top[1] + bottom[1] + 1
        dp = top[0] * bottom[0] * comb.ncr(newSize, bottom[1] + 1)
        return (dp, newSize)

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

    def sol(self):
        N = self.size
        edges = self.edges

        st = [self.root]
        parent = [-1] * (N + 1)
        child = [[] for _ in range(N + 1)]
        order = []
        while st:
            v = st.pop()
            order.append(v)
            for to in edges[v]:
                if parent[v] == to:
                    continue
                parent[to] = v
                child[v].append(to)
                st.append(to)

        dp = [self.identDp] * (N + 1)
        left = [self.identCum] * (N + 1)
        right = [self.identCum] * (N + 1)
        for v in order[::-1]:  # 貰うDPしつつ，累積をとる
            tmp = self.identCum
            for ch in child[v]:
                left[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            tmp = self.identCum
            for ch in reversed(child[v]):
                right[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            dp[v] = tmp

        fromParent = [self.identDp] * (N + 1)
        for v in order:
            if v == self.root:
                continue
            fromParent[v] = self.lift(self.merge(left[v], right[v]), fromParent[parent[v]])
            dp[v] = self.lift(dp[v], fromParent[v])  # 最後に親からの貰うDP

        return dp[:N]

N = int(input())
tree = ReRooting(N, 0, (1, -1), (1, 0))
comb = Combination(N * 2 + 100)

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

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