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 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] * self.N; R = [0] * self.N
        L2 = [0] * self.N; R2 = [0] * self.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:
# coding: utf-8
N = int(input())
branches = {}
for i  in range(N-1):
    branches[i] = list(map(int, input().split()))
tr = {}
to = {}
dp = {}
dp2 = {}
fact = [1] * int(2 * 1e5 +1)
mod = 10 ** 9 + 7


for i in range(1,len(fact)):
    fact[i] = fact[i-1] * i % mod

def perm(n, k):
    return fact[n] / fact[n-k]

def _to(node):
    if node in to.keys():
        return to[node]
    else:
        to[node] = []
        for i in range(N-1):
            if branches[i][0] == node:
                to[node].append(branches[i][1])
            elif branches[i][1] == node:
                to[node].append(branches[i][0])
        return to[node]

def dps(node, p=-1):
    go = False
    a, b, childs = 0, 1, 1
    if node in dp.keys():
        return dp[node]
    
    for branch in _to(node):
        if branch == p:
            continue
        _dp, _wt = dps(branch, p=node)
        b *= fact[_wt + 1]
        a += _wt + 1
        childs *= _dp

    dp[node] = [int(fact[a] / b * childs) % mod, a]
    return dp[node]

def bps(node, p=-1):
    if p == -1:
        dp2[node] = dp[node]
    dp_p, wt_p = dp2[node]
    for branch in _to(node):
        if branch == p:
            continue
        dp_branch, wt_branch = dp[branch]
        if branch in dp2.keys():
            bps(branch, p=node)
        else:
            tmp = [int(dp_p / perm(wt_p, wt_branch + 1) * fact[wt_branch + 1] / dp_branch),
                   wt_p-wt_branch-1]
            dp_new = dp_branch / fact[tmp[1]+1] * perm(wt_p, tmp[1]+1) * tmp[0]
            dp2[branch] = [int(dp_new % mod), wt_p]
            bps(branch, p=node)
    return None
        
if __name__ == "__main__":
    dps(1)
    bps(1)
    for i in range(1, N+1):
        print(dp2[i][0])

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
N = int(input())
branches = {}
for i  in range(N-1):
    branches[i] = list(map(int, input().split()))
tr = {}
to = {}
dp = {}
dp2 = {}

def fact(n):
    ret = 1
    if n == 0:
        return 1
    for i in range(1, n+1):
        ret *= i
    return ret

def perm(n, k):
    ret = 1
    if k == 0:
        return ret
    for i in range (n-k+1, n+1):
        ret *= i
    return ret 

def _to(node):
    if node in to.keys():
        return to[node]
    else:
        to[node] = []
        for i in range(N-1):
            if branches[i][0] == node:
                to[node].append(branches[i][1])
            elif branches[i][1] == node:
                to[node].append(branches[i][0])
        return to[node]

def dps(node, p=-1):
    go = False
    a, b, childs = 0, 1, 1
    if node in dp.keys():
        return dp[node]
    
    for branch in _to(node):
        if branch == p:
            continue
        _dp, _wt = dps(branch, p=node)
        b *= fact(_wt + 1)
        a += _wt + 1
        childs *= _dp

    dp[node] = [int(fact(a) / b * childs), a]
    return dp[node]

def bps(node, p=-1):
    if p == -1:
        dp2[node] = dp[node]
    dp_p, wt_p = dp2[node]
    for branch in _to(node):
        if branch == p:
            continue
        dp_branch, wt_branch = dp[branch]
        if branch in dp2.keys():
            bps(branch, p=node)
        else:
            tmp = [int(dp_p / perm(wt_p, wt_branch + 1) * fact(wt_branch + 1) / dp_branch),
                   wt_p-wt_branch-1]
            dp_new = dp_branch / fact(tmp[1]+1) * perm(wt_p, tmp[1]+1) * tmp[0]
            dp2[branch] = [int(dp_new), wt_p]
            bps(branch, p=node)
    return None
        
if __name__ == "__main__":
    dps(1)
    bps(1)
    for i in range(1, N+1):
        print(dp2[i][0])

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8
N = int(input())
branches = {}
for i  in range(N-1):
    branches[i] = list(map(int, input().split()))
tr = {}
to = {}
dp = {}
dp2 = {}

def fact(n):
    ret = 1
    if n == 0:
        return 1
    for i in range(1, n+1):
        ret *= i
    return ret

def perm(n, k):
    ret = 1
    if k == 0:
        return ret
    for i in range (n-k+1, n+1):
        ret *= i
    return ret 

def _to(node):
    if node in to.keys():
        return to[node]
    else:
        to[node] = []
        for i in range(N-1):
            if branches[i][0] == node:
                to[node].append(branches[i][1])
            elif branches[i][1] == node:
                to[node].append(branches[i][0])
        return to[node]

def dps(node, p=-1):
    go = False
    a, b, childs = 0, 1, 1
    if node in dp.keys():
        return dp[node]
    
    for branch in _to(node):
        if branch == p:
            continue
        _dp, _wt = dps(branch, p=node)
        b *= fact(_wt + 1)
        a += _wt + 1
        childs *= _dp

    dp[node] = [int(fact(a) / b * childs), a]
    return dp[node]

def bps(node, p=-1):
    if p == -1:
        dp2[node] = dp[node]
    dp_p, wt_p = dp2[node]
    for branch in _to(node):
        if branch == p:
            continue
        dp_branch, wt_branch = dp[branch]
        if branch in dp2.keys():
            bps(branch, p=node)
        else:
            tmp = [int(dp_p / perm(wt_p, wt_branch + 1) * fact(wt_branch + 1) / dp_branch),
                   wt_p-wt_branch-1]
            a, b, childs = tmp[1]+1, fact(tmp[1]+1), tmp[0]
            for cc_br in _to(branch):
                if cc_br == node:
                    continue
                cc_dp, cc_wt = dp[cc_br]
                b *= fact(cc_wt + 1)
                a += cc_wt + 1
                childs *= cc_dp
            dp2[branch] = [int(fact(a) / b * childs), a]
            bps(branch, p=node)
    return None
        
if __name__ == "__main__":
    dps(1)
    bps(1)
    for i in range(1, N+1):
        print(dp2[i][0])

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
p = 1000000007  #ここを変える
ccache = []
inv_ccache = []
N = 1000000
def powmod(a, n):
    global p
    res = 1
    tmp=a
    while n>0:
        if n & 1 == 1:
            res = (res * tmp) % p
        n=n//2
        tmp = tmp * tmp % p
    return res
def invmod(n):
    return powmod(n, p - 2)
def cmod(n, r):
    global p
    global ccache
    global inv_ccache
    global N
    if len(ccache) == 0:
      ccache.append(1)
      inv_ccache.append(1)
      for i in range(N):
        ccache.append(ccache[i]*(i+1)%p)
        inv_ccache.append(1)
      inv_ccache[N]=invmod(ccache[N])
      for i in range(N-1):
        inv_ccache[N-1-i]=inv_ccache[N-i]*(N-i)%p
    if r > n or r < 0:
        return 0
    if r > n // 2:
        return cmod(n, n - r)
    return ccache[n]*inv_ccache[r]%p*inv_ccache[n-r]%p
 
n = int(input())
adj_of = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    adj_of[a - 1].append(b - 1)
    adj_of[b - 1].append(a - 1)
stack = [(0, -1)] # root, excludee
course = []
while len(stack) > 0:
    popped = stack.pop()
    course.append(popped)
    for adj in adj_of[popped[0]]:
        if adj != popped[1]:
            stack.append((adj, popped[0]))
sizes = [{} for _ in range(n)] #size, pattern_num
pattern_nums = [{} for _ in range(n)]
for step in reversed(course):
    size = 1
    pattern_num = 1
    for adj in adj_of[step[0]]:
        if adj != step[1]:
            size += sizes[adj][step[0]]
            pattern_num *= pattern_nums[adj][step[0]] * cmod(size - 1, sizes[adj][step[0]]) % p
            pattern_num %= p
    sizes[step[0]][step[1]] = size
    pattern_nums[step[0]][step[1]] = pattern_num
 
#print(course)
#print(sizes)
#print(pattern_nums)
 
ans = [None] * n
for step in course:
    if step[0] == 0:
        ans[0] = pattern_nums[0][-1]
        continue
    #ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums[step[1]][step[0]]\
    #             * cmod(sizes[step[0]][step[1]] + sizes[step[1]][step[0]], sizes[step[0]][step[1]]) % p
    pattern_nums_step1_step0 = ans[step[1]] * invmod(cmod(n - 1, sizes[step[0]][step[1]]) % p * pattern_nums[step[0]][step[1]]) % p
    ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums_step1_step0 % p\
                 * cmod(n - 1, sizes[step[0]][step[1]] - 1) % p
 
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs_1(s,p): #部分木のサイズを数えるdfs
    par[s] = p
    for v in edges[s]:
        if v == p:
            continue
        size[s] += dfs_1(v,s)
    return size[s]

def dfs_2(s,p): #1を根としたときに進む向きのdp計算用dfs
    dp1[s] = fact[size[s]-1]
    for v in edges[s]:
        if v == p:
            continue
        dp1[s] *= dfs_2(v,s)
        dp1[s] %= mod
        dp1[s] *= pow(fact[size[v]], mod-2, mod)
        dp1[s] %= mod
    return dp1[s]

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

def bfs(s):
    que = deque()
    que.append((s,-1))
    while que:
        v,p = que.popleft()
        if v == 0:
            dp2[v] = dp1[v]
        else:
            inv = (dp2[p]*pow((dp1[v]*comb(n-1,size[v]))%mod,mod-2,mod)) % mod
            dp2[v] = (dp1[v]*inv*comb(n-1,size[v]-1)) % mod
        for u in edges[v]:
            if u == p:
                continue
            que.append((u,v))
n = I()
fact = [1]*(n+1)
par = [None]*n
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

edges = [[] for _ in range(n)]
size = [1]*n
dp1 = [0]*n #1を根としたときに進む向きのdp
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

dfs_1(0,-1)
dfs_2(0,-1)
dp2 = [0]*n
bfs(0)
for i in dp2:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs_1(s,p): #部分木のサイズを数えるdfs
    par[s] = p
    for v in edges[s]:
        if v == p:
            continue
        size[s] += dfs_1(v,s)
    return size[s]

def dfs_2(s,p): #1を根としたときに進む向きのdp計算用dfs
    dp1[s] = fact[size[s]-1]
    for v in edges[s]:
        if v == p:
            continue
        dp1[s] *= dfs_2(v,s)
        dp1[s] %= mod
        dp1[s] *= pow(fact[size[v]], mod-2, mod)
        dp1[s] %= mod
    return dp1[s]

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

def bfs(s): #dp1と逆向きに進むdp計算用bfs
    que = deque()
    que.append((s,-1))
    while que:
        v,p = que.popleft()
        if v == 0:
            dp2[v] = dp1[v]
        else:
            inv = dp2[p]*pow(dp1[v],mod-2,mod)*pow(comb(n-1,size[v]),mod-2,mod)
            inv %= mod
            dp2[v] = dp1[v]*inv*comb(n-1,size[v]-1)
            dp2[v] %= mod
        for u in edges[v]:
            if u == p:
                continue
            que.append((u,v))
n = I()
fact = [1]*(n+1)
par = [None]*n
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

edges = [[] for _ in range(n)]
size = [1]*n
dp1 = [0]*n #1を根としたときに進む向きのdp
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

dfs_1(0,-1)
dfs_2(0,-1)
dp2 = [0]*n
bfs(0)
for i in dp2:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs_1(s,p): #部分木のサイズを数えるdfs
    if flag[s]:
        return size[s]
    flag[s] = True
    par[s] = p
    for v in edges[s]:
        if v == p:
            continue
        size[s] += dfs_1(v,s)
    return size[s]

def dfs_2(s,p): #1を根としたときに進む向きのdp計算用dfs
    if flag[s]:
        return dp1[s]
    flag[s] = True
    dp1[s] = fact[size[s]-1]
    for v in edges[s]:
        if v == p:
            continue
        dp1[s] *= dfs_2(v,s) * pow(fact[size[v]], mod-2, mod)
        dp1[s] %= mod
    return dp1[s]

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

def bfs(s): #dp1と逆向きに進むdp計算用bfs
    que = deque()
    que.append((s,-1))
    while que:
        v,p = que.popleft()
        if v == 0:
            dp2[v] = dp1[v]
        else:
            inv = (dp2[p]*pow(dp1[v],mod-2,mod) % mod)*pow(comb(n-1,size[v]),mod-2,mod)
            inv %= mod
            dp2[v] = (dp1[v]*inv % mod)*comb(n-1,size[v]-1)
            dp2[v] %= mod
        for u in edges[v]:
            if u == p:
                continue
            que.append((u,v))
n = I()
fact = [1]*(n+1)
par = [None]*n
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

edges = [[] for _ in range(n)]
flag = [False]*n
size = [1]*n
dp1 = [0]*n #1を根としたときに進む向きのdp
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

dfs_1(0,-1)
flag = [False]*n
dfs_2(0,-1)
dp2 = [0]*n
bfs(0)
for i in dp2:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs_1(s,p): #部分木のサイズを数えるdfs
    if flag[s]:
        return size[s]
    flag[s] = True
    par[s] = p
    for v in edges[s]:
        if v == p:
            continue
        size[s] += dfs_1(v,s)
    return size[s]

def dfs_2(s,p): #1を根としたときに進む向きのdp計算用dfs
    if flag[s]:
        return dp1[s]
    flag[s] = True
    dp1[s] = fact[size[s]-1]
    for v in edges[s]:
        if v == p:
            continue
        dp1[s] *= dfs_2(v,s)
        dp1[s] %= mod
        dp1[s] *= pow(fact[size[v]], mod-2, mod)
        dp1[s] %= mod
    return dp1[s]

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

def bfs(s): #dp1と逆向きに進むdp計算用bfs
    que = deque()
    que.append((s,-1))
    while que:
        v,p = que.popleft()
        if v == 0:
            dp2[v] = dp1[v]
        else:
            inv = dp2[p]*pow(dp1[v],mod-2,mod)*pow(comb(n-1,size[v]),mod-2,mod)
            inv %= mod
            dp2[v] = dp1[v]*inv*comb(n-1,size[v]-1)
            dp2[v] %= mod
        for u in edges[v]:
            if u == p:
                continue
            que.append((u,v))
n = I()
fact = [1]*(n+1)
par = [None]*n
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

edges = [[] for _ in range(n)]
flag = [False]*n
size = [1]*n
dp1 = [0]*n #1を根としたときに進む向きのdp
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

dfs_1(0,-1)
flag = [False]*n
dfs_2(0,-1)
dp2 = [0]*n
bfs(0)
for i in dp2:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs_1(s,p): #部分木のサイズを数えるdfs
    if flag[s]:
        return size[s]
    flag[s] = True
    par[s] = p
    for v in edges[s]:
        if v == p:
            continue
        size[s] += dfs_1(v,s)
    return size[s]

def dfs_2(s,p): #1を根としたときに進む向きのdp計算用dfs
    if flag[s]:
        return dp1[s]
    flag[s] = True
    dp1[s] = fact[size[s]-1]
    for v in edges[s]:
        if v == p:
            continue
        dp1[s] *= dfs_2(v,s)
        dp1[s] %= mod
        dp1[s] *= pow(fact[size[v]], mod-2, mod)
        dp1[s] %= mod
    return dp1[s]

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

def bfs(s): #dp1と逆向きに進むdp計算用bfs
    que = deque()
    que.append((s,-1))
    flag = [False]*n
    while que:
        v,p = que.popleft()
        if flag[v]:
            continue
        flag[v] = True
        if v == 0:
            dp2[v] = dp1[v]
        else:
            inv = (dp2[p]*pow(dp1[v],mod-2,mod)%mod)*pow(comb(n-1,size[v]),mod-2,mod)
            inv %= mod
            dp2[v] = (dp1[v]*inv % mod)*comb(n-1,size[v]-1)
            dp2[v] %= mod
        for u in edges[v]:
            que.append((u,v))
n = I()
fact = [1]*(n+1)
par = [None]*n
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

edges = [[] for _ in range(n)]
flag = [False]*n
size = [1]*n
dp1 = [0]*n #1を根としたときに進む向きのdp
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

dfs_1(0,-1)
flag = [False]*n
dfs_2(0,-1)
dp2 = [0]*n
bfs(0)
for i in dp2:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9+7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def dfs_1(s,p): #部分木のサイズを数えるdfs
    if flag[s]:
        return size[s]
    flag[s] = True
    par[s] = p
    for v in edges[s]:
        if v == p:
            continue
        size[s] += dfs_1(v,s)
    return size[s]

def dfs_2(s,p): #1を根としたときに進む向きのdp計算用dfs
    if flag[s]:
        return dp1[s]
    flag[s] = True
    dp1[s] = fact[size[s]-1]
    for v in edges[s]:
        if v == p:
            continue
        dp1[s] *= dfs_2(v,s)
        dp1[s] %= mod
        dp1[s] *= pow(fact[size[v]], mod-2, mod)
        dp1[s] %= mod
    return dp1[s]

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

def bfs(s): #dp1と逆向きに進むdp計算用bfs
    que = deque()
    que.append((s,-1))
    flag = [False]*n
    while que:
        v,p = que.popleft()
        if flag[v]:
            continue
        flag[v] = True
        if v == 0:
            dp2[v] = dp1[v]
        else:
            inv = dp2[p]*pow(dp1[v],mod-2,mod)*pow(comb(n-1,size[v]),mod-2,mod)
            inv %= mod
            dp2[v] = dp1[v]*inv*comb(n-1,size[v]-1)
            dp2[v] %= mod
        for u in edges[v]:
            que.append((u,v))
n = I()
fact = [1]*(n+1)
par = [None]*n
for i in range(1,n+1):
    fact[i] = i*fact[i-1]
    fact[i] %= mod

edges = [[] for _ in range(n)]
flag = [False]*n
size = [1]*n
dp1 = [0]*n #1を根としたときに進む向きのdp
for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

dfs_1(0,-1)
flag = [False]*n
dfs_2(0,-1)
dp2 = [0]*n
bfs(0)
for i in dp2:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
p = 1000000007  #ここを変える
ccache = []
inv_ccache = []
def powmod(a, n):
    global p
    res = 1
    while n>0:
        res = (res * res) % p
        if n & 1 == 1:
            res = (res * a) % p
    return res
def invmod(n):
    return powmod(n, p - 2)
def cmod(n, r):
    global p
    global ccache
    global inv_ccache
    if len(ccache) == 0:
      ccache.append(1)
      inv_ccache.append(1)
      for i in range(1000000):
        ccache.append(ccache[i]*(i+1)%p)
        inv_ccache.append(invmod(ccache[i+1]))
    if r > n or r < 0:
        return 0
    if r > n // 2:
        return cmod(n, n - r)
    return ccache[n]*inv_ccache[r]%p*inv_ccache[n-r]%p
 
n = int(input())
adj_of = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    adj_of[a - 1].append(b - 1)
    adj_of[b - 1].append(a - 1)
stack = [(0, -1)] # root, excludee
course = []
while len(stack) > 0:
    popped = stack.pop()
    course.append(popped)
    for adj in adj_of[popped[0]]:
        if adj != popped[1]:
            stack.append((adj, popped[0]))
sizes = [{} for _ in range(n)] #size, pattern_num
pattern_nums = [{} for _ in range(n)]
for step in reversed(course):
    size = 1
    pattern_num = 1
    for adj in adj_of[step[0]]:
        if adj != step[1]:
            size += sizes[adj][step[0]]
            pattern_num *= pattern_nums[adj][step[0]] * cmod(size - 1, sizes[adj][step[0]]) % p
            pattern_num %= p
    sizes[step[0]][step[1]] = size
    pattern_nums[step[0]][step[1]] = pattern_num
 
#print(course)
#print(sizes)
#print(pattern_nums)
 
ans = [None] * n
for step in course:
    if step[0] == 0:
        ans[0] = pattern_nums[0][-1]
        continue
    #ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums[step[1]][step[0]]\
    #             * cmod(sizes[step[0]][step[1]] + sizes[step[1]][step[0]], sizes[step[0]][step[1]]) % p
    pattern_nums_step1_step0 = ans[step[1]] * invmod(cmod(n - 1, sizes[step[0]][step[1]]) % p * pattern_nums[step[0]][step[1]]) % p
    ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums_step1_step0 % p\
                 * cmod(n - 1, sizes[step[0]][step[1]] - 1) % p
 
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
p = 1000000007  #ここを変える
ccache = {}
def powmod(a, n):
    global p
    n_b = str(format(n, "b"))  # 2進表現に
    res = 1
    for bit in n_b:
        res = (res * res) % p
        if bit == "1":
            res = (res * a) % p
    return res
def invmod(n):
    return powmod(n, p - 2)
def cmod(n, r):
    global p
    global ccache
    if r > n or r < 0:
        return 0
    if r > n // 2:
        return cmod(n, n - r)
    if (n, r) in ccache:
        return ccache[(n, r)]
    def mulmod(x, y):
        global p
        return x * y % p
    ccache[(n,r)]=reduce(mulmod, range(n - r + 1, n + 1), 1) * invmod(reduce(mulmod, range(1, r + 1), 1))
    return ccache[(n,r)]
 
n = int(input())
adj_of = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    adj_of[a - 1].append(b - 1)
    adj_of[b - 1].append(a - 1)
stack = [(0, -1)] # root, excludee
course = []
while len(stack) > 0:
    popped = stack.pop()
    course.append(popped)
    for adj in adj_of[popped[0]]:
        if adj != popped[1]:
            stack.append((adj, popped[0]))
sizes = [{} for _ in range(n)] #size, pattern_num
pattern_nums = [{} for _ in range(n)]
for step in reversed(course):
    size = 1
    pattern_num = 1
    for adj in adj_of[step[0]]:
        if adj != step[1]:
            size += sizes[adj][step[0]]
            pattern_num *= pattern_nums[adj][step[0]] * cmod(size - 1, sizes[adj][step[0]])
            pattern_num %= p
    sizes[step[0]][step[1]] = size
    pattern_nums[step[0]][step[1]] = pattern_num
 
#print(course)
#print(sizes)
#print(pattern_nums)
 
ans = [None] * n
for step in course:
    if step[0] == 0:
        ans[0] = pattern_nums[0][-1]
        continue
    #ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums[step[1]][step[0]]\
    #             * cmod(sizes[step[0]][step[1]] + sizes[step[1]][step[0]], sizes[step[0]][step[1]]) % p
    pattern_nums_step1_step0 = ans[step[1]] * invmod(cmod(n - 1, sizes[step[0]][step[1]]) * pattern_nums[step[0]][step[1]]) % p
    ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums_step1_step0\
                 * cmod(n - 1, sizes[step[0]][step[1]] - 1) % p
 
for a in ans:
    print(a)