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: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        fx = ans[x]
        nf = fx*inv[s[x]-1]%mod
        sx = s[x]
        for y in v[x]:
            sy = s[y]
            nsx = sx-sy
            nsy = s[x]
            if ans[y] == None:
                fy = nf*s[y]*f[nsy-1]*pow(nsx,mod-2,mod)%mod
                ans[y] = fy
                s[x] = nsx
                s[y] = nsy
                dfs(y)
                s[x] = sx
                s[y] = sy

    n = I()
    f = [1]
    for i in range(1,n+1):
        f.append(f[-1]*i%mod)
    inv = [None]*(n+1)
    inv[n] = pow(f[n],mod-2,mod)
    for i in range(n)[::-1]:
        inv[i] = inv[i+1]*(i+1)%mod

    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    m = d[V[0]]
    s = [0]*n
    res = 1
    for i in V:
        j = p[i]
        s[i] += 1
        if j != None:
            s[j] += s[i]
            res *= inv[s[i]]
        if d[i] == m:
            continue
        res *= f[s[i]-1]
        res %= mod
    ans = [None]*n
    ans[0] = res
    dfs(0)
    for i in ans:
        print(i)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

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

mod = 10**9+7

def cmb(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
NN = 4*10**5 # 使うデータによって変える
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

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

Child = [1]*N
Score = [1]*N

def dfs1(s):
    stack = [s]
    Ind = [0]*N
    while stack:
        p = stack[-1]
        #print(p)
        #print(Score)
        #print(Child)
        if Ind[p] == len(graph[p]):
            stack.pop()
            par = -1
            if len(stack) > 0:
                par = stack[-1]
            P = []
            for ch in graph[p]:
                if ch == par: continue
                Child[p] += Child[ch]
                P.append([Score[ch], Child[ch]])
            tmp = Child[p]-1
            for s, c in P:
                Score[p] = (Score[p] * s * cmb(tmp, c)) % mod
                tmp -= c
        elif len(stack) > 1 and stack[-2] == graph[p][Ind[p]]:
            Ind[p] += 1
        else:
            stack.append(graph[p][Ind[p]])
            Ind[p] += 1

ans = [-1]*N

def dfs2(s):
    stack = [s]
    ans[s] = Score[s]
    Ind = [0]*N
    while stack:
        p = stack[-1]
        #print(p)
        #print(Score)
        #print(Child)
        if Ind[p] == len(graph[p]):
            stack.pop()
            if len(stack) > 0:
                par = stack[-1]
                kiyo = Score[par] * cmb(Child[p]-1, Child[par])
                Score[p] = Score[p] * pow(kiyo, mod-2, mod) % mod
                Child[p] -= Child[par]
                Child[par] += Child[p]
                Score[par] = (Score[par] * Score[p] * cmb(Child[par]-1, Child[p])) % mod
        elif len(stack) > 1 and stack[-2] == graph[p][Ind[p]]:
            Ind[p] += 1
        else:
            ch = graph[p][Ind[p]]
            kiyo = Score[ch] * cmb(Child[p]-1, Child[ch])
            Score[p] = Score[p] * pow(kiyo, mod-2, mod) % mod
            Child[p] -= Child[ch]
            Child[ch] += Child[p]
            Score[ch] = (Score[ch] * Score[p] * cmb(Child[ch]-1, Child[p])) % mod
            ans[ch] = Score[ch]
            stack.append(ch)
            Ind[p] += 1

def main():
    dfs1(0)
    dfs2(0)
    print(*ans, sep="\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/ python3.8
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int, read().split())
AB = zip(m, m)

MOD = 10 ** 9 + 7

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

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

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

size_d = [0] * (N + 1)
dp_d = [1] * (N + 1)

for v in order[::-1]:
    dp_d[v] *= fact[size_d[v]]
    dp_d[v] %= MOD
    p = parent[v]
    s = size_d[v] + 1
    size_d[p] += s
    dp_d[p] *= fact_inv[s] * dp_d[v]
    dp_d[p] %= MOD

size_u = [N - 2 - x for x in size_d]
dp_u = [1] * (N + 1)

for v in order[1:]:
    p = parent[v]
    x = dp_d[p]
    x *= dp_u[p]
    x *= fact_inv[size_d[p]]
    x *= fact[size_d[v] + 1]
    x *= pow(dp_d[v], MOD - 2, MOD)
    x *= fact[size_u[v]]
    x *= fact_inv[size_u[p] + 1]
    dp_u[v] = x % MOD

for xd, xu, sd, su in zip(dp_d[1:], dp_u[1:], size_d[1:], size_u[1:]):
    su += 1
    x = xd * xu * fact[sd + su] * fact_inv[sd] * fact_inv[su] % MOD
    print(x)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10**6)
stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

n_ = 2 * 10**5 + 20
mod = 10**9 + 7
fun = [1] * (n_ + 1)
for i in range(1, n_ + 1):
    fun[i] = fun[i - 1] * i % mod
rev = [1] * (n_ + 1)
rev[n_] = pow(fun[n_], mod - 2, mod)
for i in range(n_ - 1, 0, -1):
    rev[i] = rev[i + 1] * (i + 1) % mod

def modinv(x, mod):
    x %= mod
    a, b = x, mod
    u, v = 1, 0
    while b:
        t = a // b
        a -= t * b; a, b = b, a
        u -= t * v; u, v = v, u
    return u % mod

def nCr(n, r):
    if r > n:
        return 0
    return fun[n] * rev[r] % mod * rev[n - r] % mod

n = ni()
g = [list() for _ in range(n)]
for _ in range(n-1):
    a,b = nm()
    a -= 1; b -= 1
    g[a].append(b)
    g[b].append(a)

sl = [1]*n
pm = [1]*n
def dfs(v, p):
    for x in g[v]:
        if x == p:
            continue
        dfs(x, v)
        sl[v] += sl[x]
        pm[v] = pm[v] * pm[x] % mod
    sv = sl[v] - 1
    for x in g[v]:
        if x == p:
            continue
        pm[v] = pm[v] * nCr(sv, sl[x]) % mod
        sv -= sl[x]
    return

def dfs2(v, p):
    pp = pm[p] *  modinv(nCr(n-1, sl[v]) * pm[v], mod) % mod
    sp = n - sl[v]
    pm[v] = pm[v] * pp % mod * nCr(n-1, sp) % mod
    for x in g[v]:
        if x == p:
            continue
        dfs2(x, v)

dfs(0, -1)
for x in g[0]:
    dfs2(x, 0)

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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

SIZE=2*10**5+5; MOD=10**9+7 #998244353 #ここを変更する

SIZE += 1
inv = [0]*SIZE  # inv[j] = j^{-1} mod MOD
fac = [0]*SIZE  # fac[j] = j! mod MOD
#finv = [0]*SIZE # finv[j] = (j!)^{-1} mod MOD
inv[1] = 1
fac[0] = fac[1] = 1
#finv[0] = finv[1] = 1
for i in range(2,SIZE):
    inv[i] = MOD - (MOD//i)*inv[MOD%i]%MOD
    fac[i] = fac[i-1]*i%MOD
    #finv[i]= finv[i-1]*inv[i]%MOD


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n = int(input())
ab = [int(i)-1 for i in read().split()]

g = [[] for _ in range(n)]
M = iter(ab)
for a,b in zip(M,M):
    g[a].append(b)
    g[b].append(a)

order = []
parent = [-1]*n
q = [0]
while q:
    v = q.pop()
    order.append(v)
    for c in g[v]:
        if c != parent[v]:
            q.append(c)
            parent[c] = v
        
size = [1]*n
for i in order[n-1:0:-1]:
    size[parent[i]] += size[i]

res = fac[n]
for i in range(n):
    res *= inv[size[i]]
    res %= MOD

ans = [0]*n
ans[0] = res

for c in order[1::]:
    v = parent[c]
    ans[c] = ans[v]*size[c]%MOD*inv[n-size[c]]%MOD

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

Submission status: Accepted

Solution code:
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()
g = []
for i in range(n): g.append([])
for i in range(n-1):
    x, y = na()
    x -= 1
    y -= 1
    g[x].append(y)
    g[y].append(x)

dp = [0] * n
ep = [0] * n
des = [0] * n

def enumfif(n, mod):
    f = [0] * (n+1)
    invf = [0] * (n+1)
    f[0] = 1
    for i in range(1, n+1):
        f[i] = f[i-1] * i % mod

    a = f[n]
    b = mod
    p, q = 1, 0
    while b > 0:
        c = a//b
        d = a; a = b; b = d % b
        d = p; p = q; q = d-c*q
    invf[n] = p + mod if p < 0 else p
    for i in range(n-1,-1,-1):
        invf[i] = invf[i+1] * (i+1) % mod
    return f, invf

def C(n, r, mod, fif):
    if n < 0 or r < 0 or r > n:
        return 0
    return fif[0][n] * fif[1][r] * fif[1][n-r] % mod

mod = 1000000007
fif = enumfif(200005, mod)

sys.setrecursionlimit(200005)

def dfs(cur, pre, g):
    val = 1
    de = 0
    for e in g[cur]:
        if e == pre: continue
        dfs(e, cur, g)
        de += des[e]
        val = val * dp[e] * C(de, des[e], mod, fif) % mod
    dp[cur] = val
    des[cur] = de + 1

def dfs2(cur, pre, g):
    # print(cur, pre)
    for e in g[cur]:
        if e == pre: continue
        val = dp[cur] * fif[1][n-1] * fif[0][n-des[e]-1] * fif[0][des[e]] % mod
        dp[e] = val * C(n-1, n-des[e], mod, fif) % mod
        # val = dp[cur] * fif[1][n-1] * fif[0][n-des[e]-1] * fif[0][des[e]] * invl(dp[e], mod) % mod
        # dp[e] = dp[e] * val * C(n-1, n-des[e], mod, fif) % mod
        dfs2(e, cur, g)

def invl(a, mod):
    b = mod
    p = 1; q = 0
    while b > 0:
        c = a // b
        a, b = b, a%b
        p, q = q, p-c*q
    return p + mod if p < 0 else p


dfs(0, -1, g)
dfs2(0, -1, g)
for val in dp:
    print(val)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-


from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    # def __dfs1(self, u, p):
    #     o = []
    #     s = [(u, -1)]
    #     while s:
    #         u, p = s.pop()
    #         o.append((u, p))
    #         for v in self.tree[u]:
    #             if v == p:
    #                 continue
    #             s.append((v, u))

    #     for u, p in reversed(o):
    #         r = self.ie
    #         for v in self.tree[u]:
    #             if v == p:
    #                 continue
    #             # ep(u_, v, self.dp)
    #             r = self.merge(r, self.f(self.dp[u][v], v))

    #         self.dp[p][u] = self.g(r, u)
    #         print(p, u, self.dp[p][u])

    # def __dfs2(self, u, p, a):
    #     s = [(u, p, a)]

    #     while s:
    #         u, p, a = s.pop()

    #         self.dp[u][p] = a

    #         pl = [0] * (len(self.tree[u]) + 1)
    #         pl[0] = self.ie
    #         for i, v in enumerate(self.tree[u]):
    #             pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

    #         pr = [0] * (len(self.tree[u]) + 1)
    #         pr[-1] = self.ie
    #         for i, v in reversed(list(enumerate(self.tree[u]))):
    #             pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

    #         for i, v in enumerate(self.tree[u]):
    #             if v == p:
    #                 continue
    #             r = self.merge(pl[i], pr[i+1])
    #             s.append((v, u, self.g(r, v)))

    def __dfs1(self, u, p):
        r = self.ie
        for v in self.tree[u]:
            if v == p:
                continue
            self.dp[u][v] = self.__dfs1(v, u)
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)

    def __dfs2(self, u, p, a):
        for v in self.tree[u]:
            if v == p:
                self.dp[u][v] = a
                break
        pl = [0] * (len(self.tree[u]) + 1)
        pl[0] = self.ie
        for i, v in enumerate(self.tree[u]):
            pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

        pr = [0] * (len(self.tree[u]) + 1)
        pr[-1] = self.ie
        for i, v in reversed(list(enumerate(self.tree[u]))):
            pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

        for i, v in enumerate(self.tree[u]):
            if v == p:
                continue
            r = self.merge(pl[i], pr[i+1])
            self.__dfs2(v, u, self.g(r, v))

    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)


def atcoder_dp_dp_v():
    # https://atcoder.jp/contests/dp/tasks/dp_v
    # https://atcoder.jp/contests/dp/submissions/16664670
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u))


def atcoder_abc60_f():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    M = 10**9+7

    from functools import reduce

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

    def f(x, _):
        c = x[0]
        s = x[1]
        c *= pow(fact[s], M-2, M)
        c %= M
        return (c, s)

    def g(x, _):
        c = x[0]
        s = x[1]
        c *= fact[s]
        c %= M
        return (c, s+1)

    def merge(x, y):
        return (x[0]*y[0]%M, x[1]+y[1])

    rr = ReRooting(f, g, merge, (1, 0))
    for a, b in AB:
        rr.add_edge(a, b)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)[0])




if __name__ == '__main__':
    # atcoder_dp_dp_v()
    atcoder_abc60_f()

Submission status: Runtime Error

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

from collections import deque

MOD = 10**9+7
INF = float('inf')

def inv(n): return pow(n, MOD-2, MOD)

kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

N = int(input())
graph = [[] for i in range(N)]
for _ in range(N-1):
  a,b = list(map(int,input().split()))
  graph[a-1].append(b-1)
  graph[b-1].append(a-1)
  
p = [-1 for i in range(N)] 
a = [[] for i in range(N)]

shori = []
def bfs(graph, start):
  N = len(graph)
  d = [INF] * N
  d[start] = 0
  q = deque([start])
  while q:
    u = q.popleft()
    shori.append(u)
    for v in graph[u]:
      if d[v] != INF: continue
      d[v] = d[u] + 1
      p[v] = u
      a[u].append(v)
      q.append(v)
  return d

bfs(graph,0)

size = [0 for i in range(N)]
def calc_size(x):
  if size[x]: return size[x]
  temp = 1
  for y in a[x]:
    temp += calc_size(y)
  size[x] = temp
  return size[x]
calc_size(0)

narabi = [0 for i in range(N)]
def calc_narabi(x):
  if narabi[x]: return narabi[x]
  temp = kaijo(size[x]-1)
  for y in a[x]:
    temp *= gyaku_kaijo(size[y])*calc_narabi(y)
    temp %= MOD
  narabi[x] = temp
  return narabi[x]
calc_narabi(0)


pnarabi = [1 for i in range(N)]
for i in shori[1:]:
  pnarabi[i] = narabi[p[i]] * inv(narabi[i]) * inv(nCr(size[p[i]]-1,size[i])) * pnarabi[p[i]] * nCr(N-1-size[i],N-size[p[i]])
  pnarabi[i] %= MOD

for i in shori[1:]:
  temp = narabi[i] * nCr(N-1,size[i]-1) *pnarabi[i]
  temp %= MOD
  narabi[i] = temp

print(*narabi,sep="\n")

Submission status: Runtime Error

Solution code:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


import numpy as np
mod = 10**9+7

def pow_mod(base, exp):  # [numba_pow, "i8(i8,i8)"],
    # mod はグローバル変数を参照
    exp %= mod - 1
    res = 1
    while exp:
        if exp % 2:
            res = res * base % mod
        base = base * base % mod
        exp //= 2
    return res

def comb_cunstruct(n):
    # mod はグローバル変数を参照
    fac = np.empty(n+1, dtype=np.int64)
    facinv = np.empty(n+1, dtype=np.int64)
    fac[0] = f = 1
    for i in range(1, n+1):
        f = f * i % mod
        fac[i] = f
    f = pow_mod(f, -1)
    for i in range(n, -1, -1):
        facinv[i] = f
        f = f * i % mod
    return fac, facinv

def comb(n, r, fac, facinv):
    # mod はグローバル変数を参照
    return fac[n] * facinv[r] % mod * facinv[n-r] % mod

def rerooting(n, edges, fac, facinv):
    # 全方位木 dp
    # 参考: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    identity = (1, 0)
    def merge(a, b):
        return a[0] * b[0] % mod * comb(a[1] + b[1], a[1], fac, facinv) % mod, a[1] + b[1]
    def add_node(value, idx):
        return value[0], value[1] + 1
    merge(identity, identity)

    G = [[0]*0 for _ in range(n)]
    G_idxs = [[0]*0 for _ in range(n)]  # 自分を指すノードのインデックス
    for idx_edges in range(n-1):
        a, b = edges[idx_edges]
        G_idxs[a].append(len(G[b]))
        G_idxs[b].append(len(G[a]))
        G[a].append(b)
        G[b].append(a)
    # step 1
    parents = [0] * n
    order = []  # 行きがけ順
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order.append(v)
        for u in G[v]:
            if p != u:
                stack.append(u)
                parents[u] = v
    subtree_res = [[identity]*len(Gv) for Gv in G]
    # 下から登る
    for v in order[:0:-1]:
        p = parents[v]
        result = identity
        for idx_Gv, (u, subtree_res_v_i) in enumerate(zip(G[v], subtree_res[v])):
            if p == u:
                parent_idx = idx_Gv
            else:
                result = merge(result, subtree_res_v_i)
        idx_p2v = G_idxs[v][parent_idx]
        subtree_res[p][idx_p2v] = add_node(result, v)
    # step 2
    # 上から降りる
    results = [identity] * n
    for v in order:
        subtree_res_v = subtree_res[v]
        cum = identity
        cum_from_tail = [identity]
        for r in subtree_res_v[:0:-1]:
            cum = merge(r, cum)
            cum_from_tail.append(cum)
        cum_from_tail.reverse()
        cum = identity
        for r, cum_t, u, idx_u2v in zip(subtree_res_v, cum_from_tail, G[v], G_idxs[v]):
            result = add_node(merge(cum, cum_t), v)
            subtree_res[u][idx_u2v] = result
            cum = merge(cum, r)
        results[v] = add_node(cum, v)
    return np.array(results)


numba_compile([
    [pow_mod, "i8(i8,i8)"],
    [comb_cunstruct, "Tuple((i8[:],i8[:]))(i8,)"],
    [comb, "i8(i8,i8,i8[:],i8[:])"],
    [rerooting, "(i8,i8[:,:],i8[:],i8[:])"],
])


def main():
    N = int(input())
    AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N-1, 2) - 1
    fac, facinv = comb_cunstruct(202020)
    Ans = rerooting(N, AB, fac, facinv)
    print("\n".join(map(str, Ans[:, 0].tolist())))

main()

Submission status: Runtime Error

Solution code:
import numpy as np
mod = 10**9+7

def pow_mod(base, exp):  # [numba_pow, "i8(i8,i8)"],
    # mod はグローバル変数を参照
    exp %= mod - 1
    res = 1
    while exp:
        if exp % 2:
            res = res * base % mod
        base = base * base % mod
        exp //= 2
    return res

def comb_cunstruct(n):
    # mod はグローバル変数を参照
    fac = np.empty(n+1, dtype=np.int64)
    facinv = np.empty(n+1, dtype=np.int64)
    fac[0] = f = 1
    for i in range(1, n+1):
        f = f * i % mod
        fac[i] = f
    f = pow_mod(f, -1)
    for i in range(n, -1, -1):
        facinv[i] = f
        f = f * i % mod
    return fac, facinv

def comb(n, r, fac, facinv):
    # mod はグローバル変数を参照
    return fac[n] * facinv[r] % mod * facinv[n-r] % mod

def rerooting(n, edges, fac, facinv):
    # 全方位木 dp
    # 参考: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    identity = (1, 0)
    def merge(a, b):
        return a[0] * b[0] % mod * comb(a[1] + b[1], a[1], fac, facinv) % mod, a[1] + b[1]
    def add_node(value, idx):
        return value[0], value[1] + 1
    merge(identity, identity)

    G = [[0]*0 for _ in range(n)]
    G_idxs = [[0]*0 for _ in range(n)]  # 自分を指すノードのインデックス
    for idx_edges in range(n-1):
        a, b = edges[idx_edges]
        G_idxs[a].append(len(G[b]))
        G_idxs[b].append(len(G[a]))
        G[a].append(b)
        G[b].append(a)
    # step 1
    parents = [0] * n
    order = []  # 行きがけ順
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order.append(v)
        for u in G[v]:
            if p != u:
                stack.append(u)
                parents[u] = v
    subtree_res = [[identity]*len(Gv) for Gv in G]
    # 下から登る
    for v in order[:0:-1]:
        p = parents[v]
        result = identity
        for idx_Gv, (u, subtree_res_v_i) in enumerate(zip(G[v], subtree_res[v])):
            if p == u:
                parent_idx = idx_Gv
            else:
                result = merge(result, subtree_res_v_i)
        idx_p2v = G_idxs[v][parent_idx]
        subtree_res[p][idx_p2v] = add_node(result, v)
    # step 2
    # 上から降りる
    results = [identity] * n
    for v in order:
        subtree_res_v = subtree_res[v]
        cum = identity
        cum_from_tail = [identity]
        for r in subtree_res_v[:0:-1]:
            cum = merge(r, cum)
            cum_from_tail.append(cum)
        cum_from_tail.reverse()
        cum = identity
        for r, cum_t, u, idx_u2v in zip(subtree_res_v, cum_from_tail, G[v], G_idxs[v]):
            result = add_node(merge(cum, cum_t), v)
            subtree_res[u][idx_u2v] = result
            cum = merge(cum, r)
        results[v] = add_node(cum, v)
    return np.array(results)


numba_compile([
    [pow_mod, "i8(i8,i8)"],
    [comb_cunstruct, "Tuple((i8[:],i8[:]))(i8,)"],
    [comb, "i8(i8,i8,i8[:],i8[:])"],
    [rerooting, "(i8,i8[:,:],i8[:],i8[:])"],
])


def main():
    N = int(input())
    AB = np.array(sys.stdin.read().split(), dtype=np.int64).reshape(N-1, 2) - 1
    fac, facinv = comb_cunstruct(202020)
    Ans = rerooting(N, AB, fac, facinv)
    print("\n".join(map(str, Ans[:, 0].tolist())))

main()

Submission status: Runtime Error

Solution code:
modval = 10**9+7
n = int(input())
edges = {i: [] for i in range(1, n+1)}
for _ in range(n-1):
  a, b = map(int, input().split())
  edges[a].append(b)
  edges[b].append(a)
def fermat_inverse(x):
  return pow(x, modval-2, modval)
def prime_factorial(x):
  total = 1
  for i in range(1, x+1):
    total = (total*i)%modval
  return total
def recurse_subtrees(node):
  partial = 1
  tree_size = 0
  visited[node] = True
  count_child_nodes = 0
  for new_node in edges[node]:
    # not the parent node
    if visited[new_node]: continue
    count_child_nodes += 1
    subtree_solution, subtree_size = recurse_subtrees(new_node)
    tree_size = (tree_size + subtree_size)%modval
    partial = (partial*subtree_solution)%modval
    fact = prime_factorial(subtree_size)
    inv = fermat_inverse(fact)
    partial = (partial*inv)%modval
  if count_child_nodes == 0:
    return (1, 1)
  partial = (partial * prime_factorial(tree_size))%modval
  return (partial, (tree_size+1)%modval)
for i in range(1, n+1):
  visited = {i: False for i in range(1, n+1)}
  print(recurse_subtrees(i)[0])

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
input=sys.stdin.readline


class ReRooting:
    def __init__(self, N, e, merge, f, g):
        self.G = defaultdict(list)
        self.parents = [-1]*(N+1)
        self.dp = defaultdict(lambda: defaultdict(int))
        self.merge = merge
        self.f = f
        self.g = g
        self.e = e

    def add_edge(self, s, t):
        self.G[s].append(t)

    def build(self):
        self.dfs1(1)
        self.dfs2(1)
        return self.dp

    def dfs1(self, s):
        l = []
        q = [1]
        while q:
            s = q.pop()
            l.append(s)
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                self.parents[t] = s
                q.append(t)

        for s in l[::-1]:
            v = self.e
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                v = self.merge(v, self.f(self.dp[s][t], s, t))
            self.dp[self.parents[s]][s] = self.g(v, self.parents[s], s)

    def dfs2(self, s):
        q = [(s, self.e)]
        while q:
            s, dp_p = q.pop()
            par = self.parents[s]
            for t in self.G[s]:
                if t == par:
                    self.dp[s][t] = dp_p

            size = len(self.G[s])
            ac_l = [self.e] * (size+1)
            ac_r = [self.e] * (size+1)
            for i, t in enumerate(self.G[s]):
                ac_l[i+1] = self.merge(ac_l[i], self.f(self.dp[s][t], s, t))
            for i, t in enumerate(self.G[s][::-1]):
                ac_r[size-i-1] = self.merge(ac_r[size-i], self.f(self.dp[s][t], s, t))
            self.dp[-1][s] = self.g(ac_l[size], -1, s)

            for i, t in enumerate(self.G[s]):
                if t == par:
                    continue
                q.append((t, self.g(self.merge(ac_l[i], ac_r[i+1]), t, s)))


def solve():
    N = int(input())

    MOD = 10**9+7
    n = N
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    d = defaultdict(list)

    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)

    merge1 = lambda x,y:x+y
    f1 = lambda x, par, s:x
    g1 = lambda x, par, s:x+1
    e1 = 0
    tree1 = Reroot(N, e1, merge1, f1, g1)
    tree_size = tree1.build()

    merge2 = lambda x,y:(x*y)%MOD
    f2 = lambda x, par, s:(x*rev[tree_size[par][s]])%MOD
    g2 = lambda x, par, s:(x*fac[tree_size[par][s]-1])%MOD
    e2 = 1
    tree2 = Reroot(N, e2, merge2, f2, g2)

    for _ in range(N-1):
        a, b = map(int, input().split())
        tree2.add_edge(a, b)
        tree2.add_edge(b, a)
        tree1.add_edge(a, b)
        tree1.add_edge(b, a)

    ans = tree2.build()
    for i in range(1, N+1):
        print(ans[-1][i])


if __name__ == "__main__":
    solve()