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:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
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
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
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()

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



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

cnt=[-1]*n
par=[-1]*n
def f(x):
    ret=1
    for y in G[x]:
        if par[x]==y:
            continue
        par[y]=x
        ret+=f(y)
    cnt[x]=ret
    return ret

f(0)
D=[0]*n
def tree_dp(x):
    c = 1
    remain_v = cnt[x] - 1
    for y in G[x]:
        if y == par[x]:
            continue
        c = c * tree_dp(y) * comb(remain_v, cnt[y]) % mod
        remain_v -= cnt[y]
    D[x] = c
    if x: return c

tree_dp(0)
ans=[0]*n
ans[0]=D[0]



q=deque([0])
while q:
    e=q.pop()
    for d in G[e]:
        if d==par[e]:
            continue
        ans[d]=pow(comb(n-1,cnt[d])*D[d],mod-2,mod)*ans[e]*comb(n-1,cnt[d]-1)*D[d]%mod
        q+=[d]

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(500000)

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

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 sys
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

from functools import reduce
def rerooting(n, edges, fac, facinv):
    # 全方位木 dp
    # 参考1: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    # 参考2: https://atcoder.jp/contests/abc160/submissions/15255726

    # >>> ここを変える >>>
    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
    # <<< ここを変える <<<

    G = [[0]*0 for _ in range(n)]
    for i in range(n-1):
        a, b = edges[i]
        G[a].append(b)
        G[b].append(a)
    # step 1
    order = []  # 行きがけ順
    stack = [0]
    while stack:
        v = stack.pop()
        order.append(v)
        for u in G[v]:
            stack.append(u)
            G[u].remove(v)
    # 下から登る
    dp_down = [identity] * n  # 自身とその下
    for v in order[:0:-1]:
        dp_down[v] = add_node(reduce(
            merge, [dp_down[u] for u in G[v]], identity
        ), v)
    # step 2
    # 上から降りる
    dp_up = [identity] * n  # 親とその先
    for v in order:
        Gv = G[v]
        if len(Gv) == 0:
            continue
        cum = identity
        right = [identity]
        for u in Gv[:0:-1]:
            cum = merge(dp_down[u], cum)
            right.append(cum)
        right.reverse()
        cum = dp_up[v]
        for u, cum_r in zip(Gv, right):
            dp_up[u] = add_node(merge(cum, cum_r), v)
            cum = merge(cum, dp_down[u])
    results = [identity] * 0
    for v, Gv in enumerate(G):
        results.append(add_node(
            reduce(merge, [dp_down[u] for u in Gv], dp_up[v]), 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(sys.stdin.buffer.readline())
    AB = np.array(sys.stdin.buffer.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: Accepted

Solution code:
# 入力高速化

import sys

def rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考1: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    # 参考2: https://atcoder.jp/contests/abc160/submissions/15255726
    from functools import reduce
    G = [[] for _ in range(n)]
    for a, b in edges:
        G[a].append(b)
        G[b].append(a)
    # step 1
    order = []  # 行きがけ順
    stack = [0]
    while stack:
        v = stack.pop()
        order.append(v)
        for u in G[v]:
            stack.append(u)
            G[u].remove(v)
    # 下から登る
    dp_down = [0]*n  # 自身とその下
    for v in order[:0:-1]:
        dp_down[v] = add_node(reduce(
            merge, (dp_down[u] for u in G[v]), identity
        ), v)
    # step 2
    # 上から降りる
    dp_up = [identity] * n  # 親とその先
    for v in order:
        Gv = G[v]
        if len(Gv) == 0:
            continue
        cum = identity
        right = [identity]
        for u in Gv[:0:-1]:
            cum = merge(dp_down[u], cum)
            right.append(cum)
        right.reverse()
        cum = dp_up[v]
        for u, cum_r in zip(Gv, right):
            dp_up[u] = add_node(merge(cum, cum_r), v)
            cum = merge(cum, dp_down[u])
    results = [add_node(
        merge(
            reduce(merge, (dp_down[u] for u in Gv), identity),
            dp_up[v]
        ), v
    ) for v, Gv in enumerate(G)]
    return results

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

def main():
    N = int(sys.stdin.buffer.readline())
    m = map(int, sys.stdin.buffer.read().split())
    AB = tuple((a-1, b-1) for a, b in zip(m, m))
    mod = 10**9 + 7
    comb = Combination(202020)
    identity = (1, 0)
    fac, facinv = comb.fac, comb.facinv
    def merge(a, b):
        a0, a1 = a
        b0, b1 = b
        return a0*b0*fac[a1+b1]*facinv[a1]*facinv[b1]%mod, a1+b1
    def add_node(a, idx):
        a0, a1 = a
        return a0, a1+1
    Ans = rerooting(N, AB, identity, merge, add_node)
    print("\n".join(str(ans) for ans, _ in Ans))

main()

Submission status: Accepted

Solution code:
# 木を単方向に
def rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考1: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    # 参考2: https://atcoder.jp/contests/abc160/submissions/15255726
    from functools import reduce
    G = [[] for _ in range(n)]
    for a, b in edges:
        G[a].append(b)
        G[b].append(a)
    # step 1
    order = []  # 行きがけ順
    stack = [0]
    while stack:
        v = stack.pop()
        order.append(v)
        for u in G[v]:
            stack.append(u)
            G[u].remove(v)
    # 下から登る
    dp_down = [0]*n  # 自身とその下
    for v in order[:0:-1]:
        dp_down[v] = add_node(reduce(
            merge, (dp_down[u] for u in G[v]), identity
        ), v)
    # step 2
    # 上から降りる
    dp_up = [identity] * n  # 親とその先
    for v in order:
        Gv = G[v]
        if len(Gv) == 0:
            continue
        cum = identity
        right = [identity]
        for u in Gv[:0:-1]:
            cum = merge(dp_down[u], cum)
            right.append(cum)
        right.reverse()
        cum = dp_up[v]
        for u, cum_r in zip(Gv, right):
            dp_up[u] = add_node(merge(cum, cum_r), v)
            cum = merge(cum, dp_down[u])
    results = [add_node(
        merge(
            reduce(merge, (dp_down[u] for u in Gv), identity),
            dp_up[v]
        ), v
    ) for v, Gv in enumerate(G)]
    return results

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

def main():
    N = int(input())
    AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    mod = 10**9 + 7
    comb = Combination(202020)
    identity = (1, 0)
    fac, facinv = comb.fac, comb.facinv
    def merge(a, b):
        a0, a1 = a
        b0, b1 = b
        return a0*b0*fac[a1+b1]*facinv[a1]*facinv[b1]%mod, a1+b1
    def add_node(a, idx):
        a0, a1 = a
        return a0, a1+1
    Ans = rerooting(N, AB, identity, merge, add_node)
    print("\n".join(str(ans) for ans, _ in Ans))

main()

Submission status: Accepted

Solution code:
# reduce

def rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考1: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    # 参考2: https://atcoder.jp/contests/abc160/submissions/15255726
    from functools import reduce
    G = [[] for _ in range(n)]
    for a, b in edges:
        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
    # 下から登る
    dp_down = [0]*n  # 自身とその下
    for v in order[:0:-1]:
        p = parents[v]
        dp_down[v] = add_node(reduce(
            merge,
            (dp_down[u] for u in G[v] if u!=p),
            identity
        ), v)
    # step 2
    # 上から降りる
    dp_up = [identity] * n  # 親とその先
    for v in order:
        Gv = G[v]
        if len(Gv) == 1 and v != 0:
            continue
        p = parents[v]
        cum = identity
        right = [identity]
        for u in Gv[::-1]:
            if u != p:
                cum = merge(dp_down[u], cum)
                right.append(cum)
        cum = dp_up[v]
        idx_right = -2
        for u in Gv:
            if u != p:
                dp_up[u] = add_node(merge(cum, right[idx_right]), v)
                idx_right -= 1
                cum = merge(cum, dp_down[u])
    results = [add_node(
        merge(
            reduce(merge, (dp_down[u] for u in Gv if u != parents[v]), identity),
            dp_up[v]
        ), v
    ) for v, Gv in enumerate(G)]
    return results

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

def main():
    N = int(input())
    AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    mod = 10**9 + 7
    comb = Combination(202020)
    identity = (1, 0)
    fac, facinv = comb.fac, comb.facinv
    def merge(a, b):
        a0, a1 = a
        b0, b1 = b
        return a0*b0*fac[a1+b1]*facinv[a1]*facinv[b1]%mod, a1+b1
    def add_node(a, idx):
        a0, a1 = a
        return a0, a1+1
    Ans = rerooting(N, AB, identity, merge, add_node)
    print("\n".join(str(ans) for ans, _ in Ans))

main()

Submission status: Accepted

Solution code:
# 部分木の解を 1 次元で持つように変更

def rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考1: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    # 参考2: https://atcoder.jp/contests/abc160/submissions/15255726
    from functools import reduce
    G = [[] for _ in range(n)]
    for a, b in edges:
        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
    # 下から登る
    dp_down = [0]*n  # 自身とその下
    for v in order[:0:-1]:
        p = parents[v]
        result = identity
        for u in G[v]:
            if p != u:
                result = merge(result, dp_down[u])
        dp_down[v] = add_node(result, v)
    # step 2
    # 上から降りる
    dp_up = [identity] * n  # 親とその先
    for v in order:
        Gv = G[v]
        if len(Gv) == 1 and v != 0:
            continue
        p = parents[v]
        cum = identity
        right = [identity]
        for u in Gv[::-1]:
            if u != p:
                cum = merge(dp_down[u], cum)
                right.append(cum)
        cum = dp_up[v]
        idx_right = -2
        for u in Gv:
            if u != p:
                dp_up[u] = add_node(merge(cum, right[idx_right]), v)
                idx_right -= 1
                cum = merge(cum, dp_down[u])
    results = [add_node(
        merge(
            reduce(merge, (dp_down[u] for u in Gv if u != parents[v]), identity),
            dp_up[v]
        ), v
    ) for v, Gv in enumerate(G)]
    return results

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

def main():
    N = int(input())
    AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    mod = 10**9 + 7
    comb = Combination(202020)
    identity = (1, 0)
    fac, facinv = comb.fac, comb.facinv
    def merge(a, b):
        a0, a1 = a
        b0, b1 = b
        return a0*b0*fac[a1+b1]*facinv[a1]*facinv[b1]%mod, a1+b1
    def add_node(a, idx):
        a0, a1 = a
        return a0, a1+1
    Ans = rerooting(N, AB, identity, merge, add_node)
    print("\n".join(str(ans) for ans, _ in Ans))

main()

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc160/submissions/15902850
# を配列アクセスが減るように

def rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    G = [[] for _ in range(n)]
    G_idxs = [[] for _ in range(n)]  # 自分を指すノードのインデックス
    for a, b in 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 = [[0]*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 = [0] * 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 results


class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

def main():
    N = int(input())
    AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    mod = 10**9 + 7
    comb = Combination(202020)
    identity = (1, 0)
    fac, facinv = comb.fac, comb.facinv
    def merge(a, b):
        a0, a1 = a
        b0, b1 = b
        return a0*b0*fac[a1+b1]*facinv[a1]*facinv[b1]%mod, a1+b1
    def add_node(a, idx):
        a0, a1 = a
        return a0, a1+1
    Ans = rerooting(N, AB, identity, merge, add_node)
    print("\n".join(str(ans) for ans, _ in Ans))

main()

Submission status: Accepted

Solution code:
# zip をやめる

import sys
import numpy as np

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)


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

    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 = np.empty(n, dtype=np.int64)
    order = np.empty(n, dtype=np.int64)  # 行きがけ順
    idx_order = 0
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order[idx_order] = v
        idx_order += 1
        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 in range(len(G[v])):
            u = G[v][idx_Gv]
            subtree_res_v_i = subtree_res[v][idx_Gv]
            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 idx_Gv in range(len(G[v])):
            r = subtree_res_v[idx_Gv]
            cum_t = cum_from_tail[idx_Gv]
            u = G[v][idx_Gv]
            idx_u2v = G_idxs[v][idx_Gv]
            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(sys.stdin.buffer.readline())
    AB = np.array(sys.stdin.buffer.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: Accepted

Solution code:
# 適当にndarrayに

import sys
import numpy as np

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)


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

    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 = np.empty(n, dtype=np.int64)
    order = np.empty(n, dtype=np.int64)  # 行きがけ順
    idx_order = 0
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order[idx_order] = v
        idx_order += 1
        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(sys.stdin.buffer.readline())
    AB = np.array(sys.stdin.buffer.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()