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: Runtime Error

Solution code:
import math
import sys
from collections import deque
to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) *invfact[c_num] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

    return dpv[(parent,v)], treenum[(parent,v)]

def revways(v, parent):
    global dpv, treenum, N, fact, invfact, MOD

    # if dpv.get(parent,parent) == None:
    treenum[(parent,v)] = N-treenum[(v,parent)]
    #dpv[parent][v] = (dpv[v][v]*invfact[treenum[v][v]-1]*fact[treenum[v][v]-1-treenum[v][parent]]*fact[treenum[v][parent]]% (MOD)/dpv[v][parent]) % (MOD)
    val = (dpv[(v,v)]*invfact[treenum[(v,v)]-1]*fact[treenum[(v,v)]-1-treenum[(v,parent)]]*fact[treenum[(v,parent)]]% (MOD)) % (MOD)
    dpv[(parent,parent)] =  val *invfact[treenum[(parent,v)]] *invfact[treenum[(v,parent)]-1] * fact[N-1] % (MOD)


def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

    invfact[NMAX] = pow(fact[NMAX], MOD-2, MOD)
    for i in range(NMAX-1,0,-1):
        invfact[i] = invfact[i+1] * (i+1) % MOD

    pways(1,1)

    bfs = deque([])
    for i in range(1, N+1):
        if i in to[1]:
            bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and j in to[i[1]]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[(i,i)]))

main()

Submission status: Runtime Error

Solution code:
import math
import sys
from collections import deque
to = [0]
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) *invfact[c_num] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

    return dpv[(parent,v)], treenum[(parent,v)]

def revways(v, parent):
    global dpv, treenum, N, fact, invfact, MOD

    # if dpv.get(parent,parent) == None:
    treenum[(parent,v)] = N-treenum[(v,parent)]
    #dpv[parent][v] = (dpv[v][v]*invfact[treenum[v][v]-1]*fact[treenum[v][v]-1-treenum[v][parent]]*fact[treenum[v][parent]]% (MOD)/dpv[v][parent]) % (MOD)
    val = (dpv[(v,v)]*invfact[treenum[(v,v)]-1]*fact[treenum[(v,v)]-1-treenum[(v,parent)]]*fact[treenum[(v,parent)]]% (MOD)) % (MOD)
    dpv[(parent,parent)] =  val *invfact[treenum[(parent,v)]] *invfact[treenum[(v,parent)]-1] * fact[N-1] % (MOD)


def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())

    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

    invfact[NMAX] = pow(fact[NMAX], MOD-2, MOD)
    for i in range(NMAX-1,0,-1):
        invfact[i] = invfact[i+1] * (i+1) % MOD

    pways(1,1)

    bfs = deque([])
    for i in range(1, N+1):
        if i in to[1]:
            bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and j in to[i[1]]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[(i,i)]))

main()

Submission status: Runtime Error

Solution code:
import sys

def solve():
    input = lambda: sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10 ** 7)
    mod = 10 ** 9 + 7

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

    def dfs(v, Pa=-1):
        for u in to[v]:
            if u == Pa: continue
            dfs(u, v)
            size[v] += size[u]
            dp[v] *= dp[u] % mod
            dp[v] *= inv[size[u]] % mod
        dp[v] *= fact[size[v]] % mod
        size[v] += 1

    def bfs(v, Pa=-1, P_val=1, P_sz=0):
        ans[v] = P_val * dp[v] * comb(n - 1, P_sz) % mod
        for u in to[v]:
            if u == Pa: continue
            val = ans[v] * INV(dp[u] * comb(n - 1, size[u])) % mod
            bfs(u, v, val, n - size[u])

    n = int(input())
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        to[a].append(b)
        to[b].append(a)

    fac = [1] * (n + 2)
    inv = [1] * (n + 2)

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

    dp = [1] * n
    size = [0] * n
    ans = [0] * n

    dfs(0)
    bfs(0)
    print(*ans, sep='\n')

if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys


def solve():
    input = lambda: sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10 ** 7)
    mod = 10 ** 9 + 7

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

    def dfs(v, Pa=-1):
        for u in to[v]:
            if u == Pa: continue
            dfs(u, v)
            size[v] += size[u]
            dp[v] *= dp[u] % mod
            dp[v] *= inv[size[u]] % mod
        dp[v] *= fact[size[v]] % mod
        size[v] += 1

    def bfs(v, Pa=-1, P_val=1, P_sz=0):
        ans[v] = P_val * dp[v] * comb(n - 1, P_sz) % mod
        for u in to[v]:
            if u == Pa: continue
            val = ans[v] * INV(dp[u] * comb(n - 1, size[u])) % mod
            bfs(u, v, val, n - size[u])

    n = int(input())
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        to[a].append(b)
        to[b].append(a)

    fac = [1] * (n + 2)
    inv = [1] * (n + 2)

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

    dp = [1] * n
    size = [0] * n
    ans = [0] * n

    dfs(0)
    bfs(0)
    print(*ans, sep='\n')


if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(10**7)
mod = 10**9+7

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

def dfs(v, Pa=-1):
    for u in to[v]:
        if u == Pa: continue
        dfs(u, v)
        size[v] += size[u]
        dp[v] *= dp[u] % mod
        dp[v] *= comb(size[v], size[u]) % mod
    size[v] += 1

def bfs(v, Pa=-1, P_val=1, P_sz=0):
    ans[v] = P_val * dp[v] * comb(n-1, P_sz) % mod
    for u in to[v]:
        if u == Pa: continue
        val = ans[v] * INV(dp[u]*comb(n-1, size[u])) % mod
        bfs(u, v, val, n-size[u])

n = int(input())
to = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x : int(x)-1, input().split())
    to[a].append(b)
    to[b].append(a)

fac = [1] * (n+2)
inv = [1] * (n+2)

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

dp = [1] * n
size = [0] * n
ans = [0] * n

dfs(0)
bfs(0)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
mod = 10**9+7

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

def dfs(v, Pa=-1):
    for u in to[v]:
        if u == Pa: continue
        dfs(u, v)
        size[v] += size[u]
        dp[v] *= dp[u] % mod
        dp[v] *= comb(size[v], size[u]) % mod
    size[v] += 1

def bfs(v, Pa=-1, P_val=1, P_sz=0):
    ans[v] = P_val * dp[v] * comb(n-1, P_sz) % mod
    for u in to[v]:
        if u == Pa: continue
        val = ans[v] * INV(dp[u]*comb(n-1, size[u])) % mod
        bfs(u, v, val, n-size[u])

n = int(input())
to = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(lambda x : int(x)-1, input().split())
    to[a].append(b)
    to[b].append(a)

fac = [1] * (n+2)
inv = [1] * (n+2)

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

dp = [1] * n
size = [0] * n
ans = [0] * n

dfs(0)
bfs(0)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
mod = 10**9+7

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

def dfs(v, Pa=-1):
    for u in to[v]:
        if u == Pa: continue
        dfs(u, v)
        size[v] += size[u]
        dp[v] *= dp[u] % mod
        dp[v] *= comb(size[v], size[u]) % mod
    size[v] += 1

def bfs(v, Pa=-1, P_val=1, P_sz=0):
    ans[v] = P_val * dp[v] * comb(n-1, P_sz) % mod
    for u in to[v]:
        if u == Pa: continue
        val = ans[v] * INV(dp[u]*comb(n-1, size[u])) % mod
        bfs(u, v, val, n-size[u])

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

fac = [1] * (n+1)
inv = [1] * (n+1)

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

dp = [1] * n
size = [0] * n
ans = [0] * n

dfs(0)
bfs(0)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)
mod = 10**9+7

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

def dfs(v, Pa=-1):
    for u in to[v]:
        if u == Pa: continue
        dfs(u, v)
        size[v] += size[u]
        dp[v] *= dp[u] % mod
        dp[v] *= comb(size[v], size[u]) % mod
    size[v] += 1

def bfs(v, Pa=-1, P_val=1, P_sz=0):
    ans[v] = P_val * dp[v] * comb(n-1, P_sz) % mod
    for u in to[v]:
        if u == Pa: continue
        val = ans[v] * INV(dp[u] * comb(n-1, size[u]))
        bfs(u, v, val, n-size[u])

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

fac = [1] * (n+1)
inv = [1] * (n+1)

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

dp = [1] * n
size = [0] * n
ans = [0] * n

dfs(0)
bfs(0)
print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**7)
MOD = 10**9+7

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

lim = 10**6
fact = [1, 1] + [0] * (lim-1)
fact_inv = [1, 1] + [0] * (lim-1)
inv = [0, 1] + [0] * (lim-1)
for i in range(2, lim+1):
    fact[i] = fact[i-1] * i % MOD
    inv[i] = MOD - inv[MOD % i] * (MOD//i) % MOD
    fact_inv[i] = fact_inv[i-1] * inv[i] % MOD
def comb(n, m):
    if n < m or n < 0 or m < 0: return 0
    return fact[n] * (fact_inv[m] * fact_inv[n-m] % MOD) % MOD

dp = [1] * n
size = [0] * n

def dfs(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        dfs(nv, v)
        ns = size[nv]+1
        size[v] += ns
        dp[v] *= dp[nv] * comb(size[v], ns) % MOD
        dp[v] %= MOD

def dfs2(v, pv):
    for nv in g[v]:
        if nv == pv: continue
        d, sz = dp[v], size[v]
        d *= inv[dp[nv]] * inv[comb(sz, size[nv]+1)] % MOD
        d %= MOD
        sz -= size[nv]+1

        size[nv] += sz+1
        dp[nv] *= d * comb(size[nv], sz+1) % MOD
        dp[nv] %= MOD
        dfs2(nv, v)

dfs(0, -1)
dfs2(0, -1)
print(*dp, sep="\n")

Submission status: Runtime Error

Solution code:

from functools import lru_cache
import math
import sys

n = int(input())
sys.setrecursionlimit(max(1000, 2*n))

is_leaf = [True] * (n+1)
is_leaf[0] = None
d = {i: [] for i in range(1,n+1)}
for i in range(n-1):
    a,b = [int(c) for c in input().split()]
    d[a].append(b)
    d[b].append(a)
    if len(d[a]) >= 2:
        is_leaf[a] = False
    if len(d[b]) >=2:
        is_leaf[b] = False

_fact = [1] * n
_fact_inv = [1] * n

for i in range(1,n):
    _fact[i] = (_fact[i-1] * i) % M
    _fact_inv[i] = pow(_fact[i], M-2, M)

# @lru_cache(2*n)
# def _fact(n, M=10**9+7):
#     if n==1:
#         return 1
#     tmp = _fact(n-1)
#     tmp *= n
#     tmp %= M
#     return tmp

# @lru_cache(2*n)
# def _fact_inv(n, M=10**9+7):
#     tmp = _fact(n)
#     if tmp==1:
#         return 1
#     return pow(tmp, M-2, M)


M=10**9+7

# node : leaf
@lru_cache(2*n)
def _sub(a,b, M=10**9+7):
    # a -> bの枝に対してb以降の組み合わせ数・ノード数を返す
    if is_leaf[b]:
        return (1,1)
    counts = []
    num_nodes = []
    for node in d[b]:
        if node==a:
            continue
        count, num_node = _sub(b,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
#     if len(counts):
#         return ()
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count *= _fact_inv[n]
        count %= M
    count *= _fact[total]
    count %= M
    return (int(count) , total+1)

for start in range(1,n+1):
    counts = []
    num_nodes = []
    for node in d[start]:
        count, num_node = _sub(start,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count *= _fact_inv[n]
        count %= M
    count *= _fact[total]
    count %= M
    print(int(count))

Submission status: Runtime Error

Solution code:

from functools import lru_cache
import math
import sys

n = int(input())
sys.setrecursionlimit(max(1000, n))

is_leaf = [True] * (n+1)
is_leaf[0] = None
d = {i: [] for i in range(1,n+1)}
for i in range(n-1):
    a,b = [int(c) for c in input().split()]
    d[a].append(b)
    d[b].append(a)
    if len(d[a]) >= 2:
        is_leaf[a] = False
    if len(d[b]) >=2:
        is_leaf[b] = False

_fact = [1] * n
_fact_inv = [1] * n

for i in range(1,n):
    _fact[i] = (_fact[i-1] * i) % M
    _fact_inv[i] = pow(_fact[i], M-2, M)

# @lru_cache(2*n)
# def _fact(n, M=10**9+7):
#     if n==1:
#         return 1
#     tmp = _fact(n-1)
#     tmp *= n
#     tmp %= M
#     return tmp

# @lru_cache(2*n)
# def _fact_inv(n, M=10**9+7):
#     tmp = _fact(n)
#     if tmp==1:
#         return 1
#     return pow(tmp, M-2, M)


M=10**9+7

# node : leaf
@lru_cache(2*n)
def _sub(a,b, M=10**9+7):
    # a -> bの枝に対してb以降の組み合わせ数・ノード数を返す
    if is_leaf[b]:
        return (1,1)
    counts = []
    num_nodes = []
    for node in d[b]:
        if node==a:
            continue
        count, num_node = _sub(b,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
#     if len(counts):
#         return ()
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count *= _fact_inv[n]
        count %= M
    count *= _fact[total]
    count %= M
    return (int(count) , total+1)

for start in range(1,n+1):
    counts = []
    num_nodes = []
    for node in d[start]:
        count, num_node = _sub(start,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count *= _fact_inv[n]
        count %= M
    count *= _fact[total]
    count %= M
    print(int(count))

Submission status: Runtime Error

Solution code:
input = _input().__next__

from functools import lru_cache
import math
import sys

n = int(input())
sys.setrecursionlimit(max(1000, n))

is_leaf = [True] * (n+1)
is_leaf[0] = None
d = {i: [] for i in range(1,n+1)}
for i in range(n-1):
    a,b = [int(c) for c in input().split()]
    d[a].append(b)
    d[b].append(a)
    if len(d[a]) >= 2:
        is_leaf[a] = False
    if len(d[b]) >=2:
        is_leaf[b] = False

_fact = [1] * n
_fact_inv = [1] * n

for i in range(1,n):
    _fact[i] = (_fact[i-1] * i) % M
    _fact_inv[i] = pow(_fact[i], M-2, M)

# @lru_cache(2*n)
# def _fact(n, M=10**9+7):
#     if n==1:
#         return 1
#     tmp = _fact(n-1)
#     tmp *= n
#     tmp %= M
#     return tmp

# @lru_cache(2*n)
# def _fact_inv(n, M=10**9+7):
#     tmp = _fact(n)
#     if tmp==1:
#         return 1
#     return pow(tmp, M-2, M)


M=10**9+7

# node : leaf
@lru_cache(2*n)
def _sub(a,b, M=10**9+7):
    # a -> bの枝に対してb以降の組み合わせ数・ノード数を返す
    if is_leaf[b]:
        return (1,1)
    counts = []
    num_nodes = []
    for node in d[b]:
        if node==a:
            continue
        count, num_node = _sub(b,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
#     if len(counts):
#         return ()
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count *= _fact_inv[n]
        count %= M
    count *= _fact[total]
    count %= M
    return (int(count) , total+1)

for start in range(1,n+1):
    counts = []
    num_nodes = []
    for node in d[start]:
        count, num_node = _sub(start,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count *= _fact_inv[n]
        count %= M
    count *= _fact[total]
    count %= M
    print(int(count))

Submission status: Runtime Error

Solution code:


from functools import lru_cache
import math
import sys

n = int(input())
sys.setrecursionlimit(max(1000, n))

is_leaf = [True] * (n+1)
is_leaf[0] = None
d = {i: [] for i in range(1,n+1)}
for i in range(n-1):
    a,b = [int(c) for c in input().split()]
    d[a].append(b)
    d[b].append(a)
    if len(d[a]) >= 2:
        is_leaf[a] = False
    if len(d[b]) >=2:
        is_leaf[b] = False

@lru_cache(2*n)
def _fact(n, M=10**9+7):
    if n==1:
        return 1
    tmp = _fact(n-1)
    tmp *= n
    tmp %= M
    return tmp

@lru_cache(2*n)
def _fact_inv(n, M=10**9+7):
    tmp = _fact(n)
    if tmp==1:
        return 1
    return pow(tmp, M-2, M)


M=10**9+7

# node : leaf
@lru_cache(2*n)
def _sub(a,b, M=10**9+7):
    # a -> bの枝に対してb以降の組み合わせ数・ノード数を返す
    if is_leaf[b]:
        return (1,1)
    counts = []
    num_nodes = []
    for node in d[b]:
        if node==a:
            continue
        count, num_node = _sub(b,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
#     if len(counts):
#         return ()
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count *= _fact_inv(n)
        count %= M
    count *= _fact(total)
    count %= M
    return (int(count) , total+1)

for start in range(1,n+1):
    counts = []
    num_nodes = []
    for node in d[start]:
        count, num_node = _sub(start,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count *= _fact_inv(n)
        count %= M
    count *= _fact(total)
    count %= M
    print(int(count))

Submission status: Runtime Error

Solution code:
MOD = int(1e9+7)

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

subtree_size_memo = {}
def subtree_size(node,parent):
    if (node,parent) in subtree_size_memo:
        return subtree_size_memo[(node,parent)]
    if len(edges[node]) == 1:
        subtree_size_memo[(node,parent)] = 1
        return 1

    size = 1
    for neighbor in edges[node]:
        if neighbor != parent:
            size += subtree_size(neighbor,node)
    subtree_size_memo[(node,parent)] = size
    return size

factorial = [1]
for i in range(1,N+1):
    factorial.append( (i*factorial[i-1])%MOD)

def pow(a,b):
    if b == 0:
        return 1
    bisect = pow(a, b//2)
    if b % 2 == 0:
        return (bisect*bisect)%MOD
    return (a*bisect*bisect)%MOD
def inv(a):
    return pow(a,MOD-2)

def choose(n,k):
    if k > n:
        return 0
    if n == k:
        return 1
    return (factorial[n]*inv(factorial[k])%MOD)*inv(factorial[n-k])%MOD

ways_to_color_subtree_memo = {}
def ways_to_color_subtree(node,parent):
    if (node,parent) in ways_to_color_subtree_memo:
        return ways_to_color_subtree_memo[(node,parent)]
    ans = 1
    colors = subtree_size(node,parent)-1
    for neighbor in edges[node]:
        if neighbor == parent:
            continue
        neighbor_size = subtree_size(neighbor,node)
        ans *= choose(colors,neighbor_size)
        ans %= MOD
        ans *= ways_to_color_subtree(neighbor,node)
        ans %= MOD

        colors -= neighbor_size
    ways_to_color_subtree_memo[(node,parent)] = ans
    return ans

def ways_to_color(node):
    colors = N-1
    ans = 1
    for neighbor in edges[node]:
        neighbor_size = subtree_size(neighbor,node)
        ans *= choose(colors,neighbor_size)
        ans %= MOD
        ans *= ways_to_color_subtree(neighbor,node)
        ans %= MOD
        colors -= neighbor_size
    return ans
for i in range(1,N+1):
    print(ways_to_color(i))

#print(ways_to_color_subtree_memo)
#print(subtree_size_memo)

Submission status: Runtime Error

Solution code:
MOD = int(1e9+7)

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

subtree_size_memo = {}
def subtree_size(node,parent):
    if (node,parent) in subtree_size_memo:
        return subtree_size_memo[(node,parent)]
    if len(edges[node]) == 1:
        subtree_size_memo[(node,parent)] = 1
        return 1

    size = 1
    for neighbor in edges[node]:
        if neighbor != parent:
            size += subtree_size(neighbor,node)
    subtree_size_memo[(node,parent)] = size
    return size

factorial = [1]
for i in range(1,100001):
    factorial.append( (i*factorial[i-1])%MOD)

def pow(a,b):
    if b == 0:
        return 1
    bisect = pow(a, b//2)
    if b % 2 == 0:
        return (bisect*bisect)%MOD
    return (a*bisect*bisect)%MOD
def inv(a):
    return pow(a,MOD-2)

def choose(n,k):
    if k > n:
        return 0
    if n == k:
        return 1
    return (factorial[n]*inv(factorial[k])%MOD)*inv(factorial[n-k])%MOD

ways_to_color_subtree_memo = {}
def ways_to_color_subtree(node,parent):
    if (node,parent) in ways_to_color_subtree_memo:
        return ways_to_color_subtree_memo[(node,parent)]
    ans = 1
    colors = subtree_size(node,parent)-1
    for neighbor in edges[node]:
        if neighbor == parent:
            continue
        neighbor_size = subtree_size(neighbor,node)
        ans *= choose(colors,neighbor_size)
        ans %= MOD
        ans *= ways_to_color_subtree(neighbor,node)
        ans %= MOD

        colors -= neighbor_size
    ways_to_color_subtree_memo[(node,parent)] = ans
    return ans

def ways_to_color(node):
    colors = N-1
    ans = 1
    for neighbor in edges[node]:
        neighbor_size = subtree_size(neighbor,node)
        ans *= choose(colors,neighbor_size)
        ans %= MOD
        ans *= ways_to_color_subtree(neighbor,node)
        ans %= MOD
        colors -= neighbor_size
    return ans
for i in range(1,N+1):
    print(ways_to_color(i))

#print(ways_to_color_subtree_memo)
#print(subtree_size_memo)

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b): return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P

#全方位木dp
#-------------------------------------------------------------------
#扱うクラス
class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

#零元
zero = T(1, 0)
#一個上に遷移した時の変化
def step(x):
    return T(x.num, x.child+1)
#マージ
def merge(x, y):
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[]*N]
down_data = [zero] * N
dat = [zero] * N
rev_data = [zero] * N

class p:
    num = -1
    parent = -1

    def __init__(self, x, y):
        self.num = x
        self.parent = y
node_list = []
def makeNodeList(root):
    #dfsでの探索順の作成
    stack = []
    stack.append(p(root, -1))
    while len(stack) != 0:
        now = stack.pop()
        node_list.append(now)
        for to in G[now.num]:
            if to == now.parent: continue
            stack.append(p(to, now.num))
    node_list.reverse()

def dfs(root):
    for now in node_list:
        for to in G[now.num]:
            if to == now.parent: continue
            down_data[now.num] = merge(down_data[now.num], step(down_data[to]))

def dfs_rev(root):
    for now in node_list:
        #累積
        rev = rev_data[now.num]
        left = []
        right = []
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            if len(left)==0: left.append(step(down_data[to]))
            else: left.append(merge(left[cnt-1], step(down_data[to])))
            cnt += 1
        cnt = 0
        for to in reversed(G[now.num]):
            if to==now.parent: continue
            if len(right)==0: right.append(step(down_data[to]))
            else: right.append(merge(right[cnt-1], step(down_data[to])))
            cnt += 1
        dat[now.num] = merge(rev, down_data[now.num])
        cnt = 0
        for to in G[now.num]:
            if to==now.parent: continue
            x = zero if cnt==0 else left[cnt-1]
            y = zero if cnt==len(right)-1 else right[len(right)-2-cnt]
            rev_data[to] = step(merge(rev, merge(x, y)))
            cnt += 1

def calc(data_num):
    root = -1
    for i in range(1, data_num+1):
        if len(G[i]) == 1:
            root = i
            break
    makeNodeList(root)
    dfs(root)
    node_list.reverse()
    dfs_rev(root)
#-------------------------------------------------------------------
def main():
    n = int(input())
    for i in range(n-1):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)
    calc(n)

    for i in range(1, n+1): print(dat[i].num)

if __name__ == "__main__": main()