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:
class ReRooting(object):
    """ 全方位木DP (オリジナル)"""
    def processing(self, in_:list, v:int):
        """ 単項演算(加工) """
        cnt = in_[0] * factinv[in_[1]] % MOD
        size = in_[1]
        return [cnt, size]
    
    def merge(self, in1:list, in2:list):
        """ 二項演算(マージ) """
        cnt = in1[0] * in2[0] % MOD
        size = in1[1] + in2[1]
        return [cnt, size]

    def adjustment(self, in_:list, v:int):
        """ 単項演算(調整) """
        cnt = in_[0] * fact[in_[1]] % MOD
        size = in_[1] + 1
        return [cnt, size]
    
    def solve(self):
        """ 結果を返す """
        return [cnt for cnt,_ in self.calc()]

    def __init__(self, V:int, e:list):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
    
    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self, e:list):
        """ Bottom-Up DP """
        accBU = [e for _ in range(self.V)]
        resBU = [None] * self.V
        for v in reversed(self.order):
            for c in self.edge[v]:
                accBU[v] = self.merge(accBU[v], self.processing(resBU[c], c))
            resBU[v] = self.adjustment(accBU[v], v)
        return accBU, resBU
    
    def top_down(self, resBU:list, e:list):
        """ Top-Down DP """
        accTD = [e for _ in range(self.V)]
        resTD = [e for _ in range(self.V)]

        for p in self.order:
            ac = self.processing(resTD[p], p)
            for v in self.edge[p]:
                accTD[v] = ac.copy()
                ac = self.merge(ac, self.processing(resBU[v], v))
            
            ac = e
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                resTD[v] = self.adjustment(accTD[v], v)
                ac = self.merge(ac, self.processing(resBU[v], v))
        return resTD
    
    def calc(self):
        """ 開始条件: 木を構築済み """
        self.topological_sort()
        accBU, resBU = self.bottom_up(self.e)
        resTD = self.top_down(resBU, self.e)

        res = [None] * self.V
        for v in range(self.V):
            res[v] = self.processing(resTD[v], v)
            res[v] = self.merge(accBU[v], res[v])
            res[v] = self.adjustment(res[v], v)
        return res

#########################################################################################
import sys
input = sys.stdin.readline

N = int(input())
MOD = 10 ** 9 + 7

fact = [1] * (N + 1) # fact[n]: n!
factinv = [1] * (N + 1) # n!の逆元
for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % MOD
factinv[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(N - 1, -1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % MOD
 
def main():
    RR = ReRooting(N, [1, 0])
    for _ in range(N - 1):
        a, b = map(int, input().split())
        RR.add_edge(a - 1, b- 1)
    print(*RR.solve(), sep="\n")

 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class ReRooting(object):
    """ 全方位木DP (オリジナル)"""
    def processing(self, in_:dict, v:int):
        """ 単項演算(加工) """
        cnt = in_["cnt"] * factinv[in_["size"]] % MOD
        size = in_["size"]
        return {"cnt":cnt, "size":size}
    
    def merge(self, in1:dict, in2:dict):
        """ 二項演算(マージ) """
        cnt = in1["cnt"] * in2["cnt"] % MOD
        size = in1["size"] + in2["size"]
        return {"cnt":cnt, "size":size}

    def adjustment(self, in_:dict, v:int):
        """ 単項演算(調整) """
        cnt = in_["cnt"] * fact[in_["size"]] % MOD
        size = in_["size"] + 1
        return {"cnt":cnt, "size":size}
    
    def solve(self):
        """ 結果を返す """
        ans = self.calc()
        for v in range(self.V):
            ans[v] = ans[v]["cnt"]
        return ans

    def __init__(self, V:int, e:dict):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
    
    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self, e:dict):
        """ Bottom-Up DP """
        accBU = [e for _ in range(self.V)]
        resBU = [None] * self.V
        for v in reversed(self.order):
            for c in self.edge[v]:
                accBU[v] = self.merge(accBU[v], self.processing(resBU[c], c))
            resBU[v] = self.adjustment(accBU[v], v)
        return accBU, resBU
    
    def top_down(self, resBU:dict, e:dict):
        """ Top-Down DP """
        accTD = [e for _ in range(self.V)]
        resTD = [e for _ in range(self.V)]

        for p in self.order:
            ac = self.processing(resTD[p], p)
            for v in self.edge[p]:
                accTD[v] = ac.copy()
                ac = self.merge(ac, self.processing(resBU[v], v))
            
            ac = self.e.copy()
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                resTD[v] = self.adjustment(accTD[v], v)
                ac = self.merge(ac, self.processing(resBU[v], v))
        return resTD
    
    def calc(self):
        """ 開始条件: 木を構築済み """
        self.topological_sort()
        accBU, resBU = self.bottom_up(self.e)
        resTD = self.top_down(resBU, self.e)

        res = [None] * self.V
        for v in range(self.V):
            res[v] = self.processing(resTD[v], v)
            res[v] = self.merge(accBU[v], res[v])
            res[v] = self.adjustment(res[v], v)
        return res

#########################################################################################
import sys
input = sys.stdin.readline

N = int(input())
MOD = 10 ** 9 + 7

fact = [1] * (N + 1) # fact[n]: n!
factinv = [1] * (N + 1) # n!の逆元
for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % MOD
factinv[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(N - 1, -1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % MOD
 
def main():
    RR = ReRooting(N, {"cnt":1, "size":0})
    for _ in range(N - 1):
        a, b = map(int, input().split())
        RR.add_edge(a - 1, b- 1)
    print(*RR.solve(), sep="\n")

 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class ReRooting(object):
    """ 全方位木DP (オリジナル)"""
    def processing(self, in_:dict, v:int):
        """ 単項演算(加工) """
        cnt = in_["cnt"] * factinv[in_["size"]] % MOD
        size = in_["size"]
        return {"cnt":cnt, "size":size}
    
    def merge(self, in1:dict, in2:dict):
        """ 二項演算(マージ) """
        cnt = in1["cnt"] * in2["cnt"] % MOD
        size = in1["size"] + in2["size"]
        return {"cnt":cnt, "size":size}

    def adjustment(self, in_:dict, v:int):
        """ 単項演算(調整) """
        cnt = in_["cnt"] * fact[in_["size"]] % MOD
        size = in_["size"] + 1
        return {"cnt":cnt, "size":size}
    
    def solve(self):
        """ 結果を返す """
        ans = self.calc()
        for v in range(self.V):
            ans[v] = ans[v]["cnt"]
        return ans

    def __init__(self, V:int, e:dict):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
    
    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self):
        """ Bottom-Up DP """
        accBU = [self.e.copy() for _ in range(self.V)]
        resBU = [None] * self.V
        for v in reversed(self.order):
            for c in self.edge[v]:
                accBU[v] = self.merge(accBU[v], self.processing(resBU[c], c))
            resBU[v] = self.adjustment(accBU[v], v)
        return accBU, resBU
    
    def top_down(self, resBU:dict):
        """ Top-Down DP """
        accTD = [self.e.copy() for _ in range(self.V)]
        resTD = [self.e.copy() for _ in range(self.V)]

        for p in self.order:
            ac = self.processing(resTD[p], p)
            for v in self.edge[p]:
                accTD[v] = ac.copy()
                ac = self.merge(ac, self.processing(resBU[v], v))
            
            ac = self.e.copy()
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                resTD[v] = self.adjustment(accTD[v], v)
                ac = self.merge(ac, self.processing(resBU[v], v))
        return resTD
    
    def calc(self):
        """ 開始条件: 木を構築済み """
        self.topological_sort()
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)

        res = [None] * self.V
        for v in range(self.V):
            res[v] = self.processing(resTD[v], v)
            res[v] = self.merge(accBU[v], res[v])
            res[v] = self.adjustment(res[v], v)
        return res

#########################################################################################
N = int(input())
MOD = 10 ** 9 + 7
 
fact = [1] * (N + 1) # fact[n]: n!
factinv = [1] * (N + 1) # n!の逆元
for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % MOD
factinv[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(N - 1, -1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % MOD
 
def main():
    RR = ReRooting(N, {"cnt":1, "size":0})
    for _ in range(N - 1):
        a, b = map(int, input().split())
        RR.add_edge(a - 1, b- 1)
    print(*RR.solve(), sep="\n")

 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class ReRooting(object):
    """ 全方位木DP (オリジナル)"""
    def processing(self, in_:dict, v:int):
        """ 単項演算(加工) """
        out = self.e.copy()
        out["cnt"] = in_["cnt"] * factinv[in_["size"]] % MOD
        out["size"] = in_["size"]
        return out
    
    def merge(self, in1:dict, in2:dict):
        """ 二項演算(マージ) """
        out = self.e.copy()
        out["cnt"] = in1["cnt"] * in2["cnt"] % MOD
        out["size"] = in1["size"] + in2["size"]
        return out

    def adjustment(self, in_:dict, v:int):
        """ 単項演算(調整) """
        out = self.e.copy()
        out["cnt"] = in_["cnt"] * fact[in_["size"]] % MOD
        out["size"] = in_["size"] + 1
        return out
    
    def solve(self):
        """ 結果を返す """
        ans = self.calc()
        for v in range(self.V):
            ans[v] = ans[v]["cnt"]
        return ans

    def __init__(self, V:int, e:dict):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
    
    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self):
        """ Bottom-Up DP """
        accBU = [self.e.copy() for _ in range(self.V)]
        resBU = [None] * self.V
        for v in reversed(self.order):
            for c in self.edge[v]:
                accBU[v] = self.merge(accBU[v], self.processing(resBU[c], c))
            resBU[v] = self.adjustment(accBU[v], v)
        return accBU, resBU
    
    def top_down(self, resBU:dict):
        """ Top-Down DP """
        accTD = [self.e.copy() for _ in range(self.V)]
        resTD = [self.e.copy() for _ in range(self.V)]

        for p in self.order:
            ac = self.processing(resTD[p], p)
            for v in self.edge[p]:
                accTD[v] = ac.copy()
                ac = self.merge(ac, self.processing(resBU[v], v))
            
            ac = self.e.copy()
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                resTD[v] = self.adjustment(accTD[v], v)
                ac = self.merge(ac, self.processing(resBU[v], v))
        return resTD
    
    def calc(self):
        """ 開始条件: 木を構築済み """
        self.topological_sort()
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)

        res = [None] * self.V
        for v in range(self.V):
            res[v] = self.processing(resTD[v], v)
            res[v] = self.merge(accBU[v], res[v])
            res[v] = self.adjustment(res[v], v)
        return res

#########################################################################################
N = int(input())
MOD = 10 ** 9 + 7
 
fact = [1] * (N + 1) # fact[n]: n!
factinv = [1] * (N + 1) # n!の逆元
for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % MOD
factinv[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(N - 1, -1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % MOD
 
def main():
    RR = ReRooting(N, {"cnt":1, "size":0})
    for _ in range(N - 1):
        a, b = map(int, input().split())
        RR.add_edge(a - 1, b- 1)
    print(*RR.solve(), sep="\n")

 
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

mod = 10**9+7

kkai = [1]
for i in range(1, 2*10 ** 5):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    if b == 0:
        return 1
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


child = [0] * n


def dfs1(i=0, r=-1):
    s = 1
    for j in e[i]:
        if j == r:
            continue
        s += dfs1(j, i)
    child[i] = s
    return s


dfs1()

a = [0] * n


def dfs2(i=0, r=-1):
    s = 1
    t = 0
    for j in e[i]:
        if j == r:
            continue
        t += child[j]
        s *= dfs2(j, i)
        s %= mod
        s *= comb(t, child[j])
        s %= mod
    a[i] = s
    return s


dfs2()

b = [0] * n


def dfs3(i=0, r=-1):
    if r == -1:
        b[i] = a[i]
    else:
        s = b[r] * comb(n-1, child[i]-1) % mod
        re = comb(n-1, child[i])
        s *= pow(re, mod - 2, mod)
        s %= mod
        b[i] = s

    for j in e[i]:
        if j == r:
            continue
        dfs3(j, i)


dfs3()

print("\n".join(map(str, b)))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

mod = 10**9+7

kkai = [1]
for i in range(1, 10 ** 6):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    if b == 0:
        return 1
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


child = [0] * n


def dfs1(i=0, r=-1):
    s = 1
    for j in e[i]:
        if j == r:
            continue
        s += dfs1(j, i)
    child[i] = s
    return s


dfs1()

a = [0] * n


def dfs2(i=0, r=-1):
    s = 1
    t = 0
    for j in e[i]:
        if j == r:
            continue
        t += child[j]
        s *= dfs2(j, i)
        s %= mod
        s *= comb(t, child[j])
        s %= mod
    a[i] = s
    return s


dfs2()

b = [0] * n


def dfs3(i=0, r=-1):
    if r == -1:
        b[i] = a[i]
    else:
        s = b[r] * comb(n-1, child[i]-1) % mod
        re = comb(n-1, child[i])
        s *= pow(re, mod - 2, mod)
        s %= mod
        b[i] = s

    for j in e[i]:
        if j == r:
            continue
        dfs3(j, i)


dfs3()

print("\n".join(map(str, b)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n =I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

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

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

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

v_num = [-1] * n
par = [-1] * n
def f(u):
    ret = 1
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        ret += f(v)
    v_num[u] = ret
    if u: return ret

f(0)
dp = [0] * n

def tree_dp(x):
    c = 1
    remain_v = v_num[x] - 1
    for y in G[x]:
        if y == par[x]:
            continue
        c = c * tree_dp(y) * comb(remain_v, v_num[y]) % mod
        remain_v -= v_num[y]
    dp[x] = c
    if x: return c

tree_dp(0)
ans = [0] * n

def dfs(d):
    e = 1
    inv_e = pow(comb(n - 1, v_num[d]) * dp[d], mod - 2, mod)
    ans[d] = dp[d] * ans[par[d]] * comb(n - 1, v_num[d] - 1) * inv_e % mod

q = deque([0])
ans[0] = dp[0]
while q:
    g = q.pop()
    for h in G[g]:
        if h == par[g]:
            continue
        dfs(h)
        q += [h]

for j in ans:
    print(j)

Submission status: Time Limit Exceeded

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

Solution code:
#!/usr/bin/env python3
import sys
import resource
sys.setrecursionlimit(2 * 10**5)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))


MOD = 1000000007  # type: int

def solve(N: int, a: "List[int]", b: "List[int]"):
    mf = ModFactorial(MOD, N)
    edges = [[] for _ in range(N)]
    for aa, bb in zip(a, b):
        edges[aa-1].append(bb-1)
        edges[bb-1].append(aa-1)
        
    sizes = [0] * N
    par = [None] * N
    def f(pre, cur):
        par[cur] = pre
        for n in edges[cur]:
            if pre == n:
                continue
            sizes[cur] += f(cur, n) + 1
        return sizes[cur]
    f(None, 0)

    dp1 = [None] * N
    def g(pre, cur):        
        a = mf.factorial(sizes[cur])
        for n in edges[cur]:
            if n == pre:
                continue
            a = a * g(cur, n) % MOD
            a = a * mf.factorial_inv(sizes[n]+1) % MOD
        dp1[cur] = a
        return a
    g(None, 0)

    dp2 = [None] * N
    dp2[0] = 1
    def h(cur):
        if dp2[cur]:
            return dp2[cur]
        a = dp1[par[cur]] #0
        a = a * mf.factorial(sizes[cur]+1) % MOD #1
        a = a * mf.factorial(N-sizes[cur]-2) % MOD #2
        a = a * h(par[cur]) % MOD #3
        a = a * mf.factorial_inv(sizes[par[cur]]) % MOD #4
        a = a * mf.factorial_inv(N-sizes[par[cur]]-1) % MOD #5
        a = a * mod_inv(MOD, dp1[cur]) % MOD #6
        dp2[cur] = a
        return a

    for i in range(N):
        a = dp1[i] * h(i) % MOD
        a = a * mf.factorial(N-1) % MOD
        a = a * mf.factorial_inv(sizes[i]) % MOD
        a = a * mf.factorial_inv(N - sizes[i] - 1) % MOD
        print(a)

def mod_range(mod, start, stop=None, step=1):    
    if stop == None:
        stop = start
        start = 0
    return map(lambda i: i % mod, range(start, stop, step))

def mod_inv(mod, n):
    '''
    >>> mod_inv(3, 2)
    2
    >>> mod_inv(1000000007, 2)
    500000004
    '''
    return pow(n, mod-2, mod)

class ModFactorial:
    def __init__(self, mod, size=1):
        '''
        >>> ModFactorial(7, 7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert mod > size
        self._mod = mod
        self._init_factorials(size)

    def _mod_range(self, start, stop=None, step=1):
        return mod_range(self._mod, start, stop, step)
        
    def _init_factorials(self, size):
        '''
        >>> mf1 = ModFactorial(1000000007)
        >>> mf2 = ModFactorial(1000000007, 10)
        >>> mf1.factorial(10) == mf2.factorial(10)
        True
        '''
        self._factorials = [1] * size        
        n = 1 # リストの参照は遅いので減らす
        for i, m in enumerate(self._mod_range(1, size), 1):
            n = (n * m) % self._mod
            self._factorials[i] = n
            
    def _append_factorials(self, n):
        for m in map(lambda i: i % self._mod, range(len(self._factorials), n+1)):
            self._factorials.append((self._factorials[-1] * m) % self._mod)

    def _mod_inv(self, n):
        return mod_inv(self._mod, n)

    def factorial(self, n):
        '''
        >>> ModFactorial(1000000007).factorial(10)
        3628800
        >>> ModFactorial(7).factorial(6)
        6
        >>> ModFactorial(7).factorial(7)
        Traceback (most recent call last):
        ...
        AssertionError
        '''
        assert n < self._mod
        if len(self._factorials) <= n:
            self._append_factorials(n)
        return self._factorials[n]

    def factorial_inv(self, n):
        '''
        >>> MOD = 1000000007
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(10)
        283194722
        >>> mf.factorial_inv(10) * mf.factorial(10) % MOD
        1
        >>> MOD = 7
        >>> mf = ModFactorial(MOD)
        >>> mf.factorial_inv(6)
        6
        >>> mf.factorial_inv(6) * mf.factorial(6) % MOD
        1
        '''
        return self._mod_inv(self.factorial(n))

    def permutation(self, n, r):
        '''
        >>> ModFactorial(1000000007).permutation(10, 2)
        90
        '''
        return self.factorial(n) * self.factorial_inv(n-r) % self._mod

    def combination(self, n, r):
        '''
        >>> ModFactorial(1000000007).combination(10, 2)
        45
        '''
        return self.permutation(n, r) * self.factorial_inv(r) % self._mod


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7
N = int(input())
tree = dict(zip(range(N), [[] for i in range(N)]))
edge_id = {}
c = 0
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  tree[a].append(b)
  tree[b].append(a)
  edge_id[(a, b)] = c
  edge_id[(b, a)] = c + 1
  c += 2

# 部分木のサイズ
# 頂点v1 -> v2の向きを考えたときに、頂点v2を根とする部分木のサイズを計算する
size = [0] * 2*(N-1)
def calc_size(v1, v2):
  global size
  idx = edge_id[(v1, v2)]
  if size[idx]:
    return size[idx]
  children = tree[v2]
  s = 1
  for child in children:
    if child == v1:
      continue
    s += calc_size(v2, child)
  size[idx] = s
  idx_inv = edge_id[(v2, v1)]
  size[idx_inv] = N - s
  return s

# 階乗、組合せの計算
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def comb(n, r, mod=MOD):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

# 頂点iに1を書くときの場合の数
ans = [0] * N
dp = [0] * 2*(N-1)
def calc_dp(v1, v2):
  global dp
  idx = edge_id[(v1, v2)]
  if dp[idx]:
    return dp[idx]
  children = tree[v2]
  s = calc_size(v1, v2)
  res = g1[s-1]
  for child in children:
    if child == v1:
      continue
    res *= calc_dp(v2, child)
    res %= MOD
    _s = calc_size(v2, child)
    res *= g2[_s]
    res %= MOD
  dp[idx] = res
  return res

def calc_ans(i):
  global ans
  global dp
  if ans[i]:
    return ans[i]
  children = tree[i]
  res = g1[N-1]
  for child in children:
    res *= calc_dp(i, child)
    res %= MOD
    _s = calc_size(i, child)
    res *= g2[_s]
    res %= MOD
  ans[i] = res
  return res

calc_ans(0)
d = deque([[0, -1]])
c = 0
while d:
  node, par = d.popleft()
  c += 1
  children = tree[node]
  for child in children:
    if child == par:
      continue
    s = calc_size(node, child)
    r = s * pow(N-s, MOD-2, MOD) % MOD
    ans[child] = ans[node] * r % MOD
    d.append([child, node])

print(*ans, sep='\n')