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:
# 全方位DP
import sys
input = lambda: sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
from collections import defaultdict, deque
from math import factorial

MOD = 10**9+7
class Facts():
    def __init__(self, max_num=10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def power_func(self, a, b):
        ans = 1
        while b > 0:
            if b & 1:
                ans = ans * a % self.p
            a = a * a % self.p
            b >>= 1
        return ans

    def fact_inv(self, a):
        return self.power_func(a, self.p-2) % self.p

n = int(input())
fact = Facts(max_num=200000)
edges = defaultdict(lambda: [])

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

# step1 吸い上げ
size = [1 for _ in range(n+1)]
def dfs1(num, par=-1):
    res = 1
    for node in edges[num]:
        if node == par:
            continue
        else:
            res += dfs1(node, num)
    res %= MOD
    size[num] = res
    return res
dfs1(1)
# print(size)
dp = [0 for _ in range(n+1)]
def dfs2(n, par=-1):
    res = fact.fact[size[n] - 1]
    for node in edges[n]:
        if node == par:
            continue
        else:
            res *= dfs2(node, n) * fact.fact_inv(fact.fact[size[node]])
    res %= MOD
    dp[n] = res
    return res
dfs2(1)
# print(dp)

# step2 還元
ans = [0 for _ in range(n+1)]
inv_1 = fact.fact_inv(fact.fact[n-1])
def dfs3(num, par=-1):
    if par != -1:
        res = dp[num] * fact.fact_inv(fact.fact[size[num] - 1]) * \
            fact.fact[n-1] * ans[par] * inv_1 * \
            fact.fact[n-size[num]-1] * fact.fact[size[num]] * \
            fact.fact_inv(dp[num]) * \
            fact.fact_inv(fact.fact[n-size[num]]) % MOD
        ans[num] = res
    else:
        ans[num] = dp[num]
    for node in edges[num]:
        if node == par:
            continue
        dfs3(node, num)
dfs3(1)
print("\n".join(list(map(str, ans[1:]))))

Submission status: Runtime Error

Solution code:
# coding: utf-8
DATA = """
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = [int(i) for i in get_line().strip().split(" ")][0]

m = {i:[] for i in range(N)}

for _ in range(N-1):
	a, b = [int(i) for i in get_line().strip().split(" ")]
	a -= 1
	b -= 1

	m[a].append(b)
	m[b].append(a)

memo = {}
count = 0
def Calc(f):
	mul = 1
	s = 0
	if (f, tuple(m[f])) in memo:
		return memo[f, tuple(m[f])]
	global count
	count += 1
	for t in m[f]:
		m[t].remove(f)
		dummy = Calc(t)
		s += dummy[0] + 1
		mul *= dummy[1] * (dummy[0] + 1)
		m[t].append(f)
	memo[f, tuple(m[f])] = (s, mul)
	return s, mul

import functools 
#P = functools.reduce(lambda x, y: x * y, range(1, N), 1)
P = 1
MOD = 10 ** 9 + 7

for i in range(N):
	sum, mul = Calc(i)
	#print (P // mul, (P // mul) % 19, (P%19) // (mul%19))
	print((P//mul) % MOD)
#print (count)

Submission status: Runtime Error

Solution code:
# coding: utf-8
DATA = """
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = [int(i) for i in get_line().strip().split(" ")][0]

m = {i:[] for i in range(N)}

for _ in range(N-1):
	a, b = [int(i) for i in get_line().strip().split(" ")]
	a -= 1
	b -= 1

	m[a].append(b)
	m[b].append(a)

memo = {}
count = 0
def Calc(f):
	mul = 1
	s = 0
	if tuple(m[f]) in memo:
		return memo[tuple(m[f])]
	global count
	count += 1
	for t in m[f]:
		m[t].remove(f)
		dummy = Calc(t)
		s += dummy[0] + 1
		mul *= dummy[1] * (dummy[0] + 1)
		m[t].append(f)
	memo[tuple(m[f])] = (s, mul)
	return s, mul

import functools 
P = functools.reduce(lambda x, y: x * y, range(1, N), 1)

MOD = 10 ** 9 + 7

for i in range(N):
	sum, mul = Calc(i)
	#print (P // mul, (P // mul) % 19, (P%19) // (mul%19))
	print((P//mul) % MOD)
#print (count)

Submission status: Runtime Error

Solution code:
# coding: utf-8
DATA = """
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = [int(i) for i in get_line().strip().split(" ")][0]

m = {i:{} for i in range(N)}

for _ in range(N-1):
	a, b = [int(i) for i in get_line().strip().split(" ")]
	a -= 1
	b -= 1

	m[a][b] = False
	m[b][a] = False

memo = {}
count = 0
def Calc(f):
	mul = 1
	s = 0
	if tuple(m[f].items()) in memo:
		return memo[tuple(m[f].items())]
	global count
	count += 1
	for t in m[f]:
		del m[t][f]
		dummy = Calc(t)
		
		s += dummy[0] + 1
		mul *= dummy[1] * (dummy[0] + 1)
		m[t][f] = True
	
	memo[tuple(m[f].items())] = (s, mul)
	return s, mul

import functools 
P = functools.reduce(lambda x, y: x * y, range(1, N), 1)

MOD = 10 ** 9 + 7

for i in range(N):
	sum, mul = Calc(i)
	#print (P // mul, (P // mul) % 19, (P%19) // (mul%19))
	print((P//mul) % MOD)
#print (count)

Submission status: Runtime Error

Solution code:
# coding: utf-8
DATA = """
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
""".split("\n")

def get_debug_line():
	for i in DATA:
		yield i

if 1:
	get_line = input
else:
	get_line = get_debug_line().__next__
	get_line()

N = [int(i) for i in get_line().strip().split(" ")][0]

m = {i:{} for i in range(N)}

for _ in range(N-1):
	a, b = [int(i) for i in get_line().strip().split(" ")]
	a -= 1
	b -= 1

	m[a][b] = False
	m[b][a] = False

memo = {}
count = 0
def Calc(f):
	mul = 1
	s = 0
	if tuple(m[f].items()) in memo:
		return memo[tuple(m[f].items())]
	global count
	count += 1
	for t in m[f]:
		if m[f][t] == True:
			continue
		m[t][f] = True
		dummy = Calc(t)
		
		s += dummy[0] + 1
		mul *= dummy[1] * (dummy[0] + 1)
		m[t][f] = False
	
	memo[tuple(m[f].items())] = (s, mul)
	return s, mul

import functools 
P = functools.reduce(lambda x, y: x * y, range(1, N), 1)

MOD = 10 ** 9 + 7

for i in range(N):
	sum, mul = Calc(i)
	#print (P // mul, (P // mul) % 19, (P%19) // (mul%19))
	print((P//mul) % MOD)
#print (count)

Submission status: Runtime Error

Solution code:
def reroot(nodeCount, edges, identity, merge, addNode):
    adjacents = [list() for _ in range(nodeCount)]
    indexForAdjacents = [list() for _ in range(nodeCount)]
    for u, v in edges:
        indexForAdjacents[u].append(len(adjacents[v]))
        indexForAdjacents[v].append(len(adjacents[u]))
        adjacents[u].append(v)
        adjacents[v].append(u)
    childSubtreeRes = [[identity]*len(adjacents[i]) for i in range(nodeCount)]
    nodeRes = [identity]*nodeCount
    parents = [-1]*nodeCount
    order = [0]*nodeCount
    index = 0
    stack = [0]
    while stack:
        node = stack.pop()
        order[index] = node
        index += 1
        for adjacent in adjacents[node]:
            if adjacent == parents[node]:
                continue
            stack.append(adjacent)
            parents[adjacent] = node
    for node in reversed(order):
        parent = parents[node]
        result = identity
        parentIndex = -1
        for j in range(len(adjacents[node])):
            if adjacents[node][j] == parent:
                parentIndex = j
                continue
            result = merge(result, childSubtreeRes[node][j])
        childSubtreeRes[parent][indexForAdjacents[node][parentIndex]] = addNode(result, node)
    for node in order:
        accumsFromTail = [identity]*len(adjacents[node])
        for j in range(len(adjacents[node])-1, 0, -1):
            accumsFromTail[j - 1] = merge(childSubtreeRes[node][j], accumsFromTail[j])
        accum = identity
        for j in range(len(adjacents[node])):
            result = addNode(merge(accum, accumsFromTail[j]), node)
            childSubtreeRes[adjacents[node][j]][indexForAdjacents[node][j]] = result
            accum = merge(accum, childSubtreeRes[node][j])
        nodeRes[node] = addNode(accum, node)
    return nodeRes

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
  
mod = 10**9 + 7
int1 = lambda x: int(x) - 1
merge = lambda p, q: (p[0] * q[0] * rev[q[1]] % mod, p[1] + q[1])
addNode = lambda value, idx: (value[0] * fun[value[1]] % mod, value[1] + 1)
N = int(input())
identity = (1, 0)
edges = [tuple(map(int1, input().split())) for _ in range(N-1)]
res = reroot(N, edges, identity, merge, addNode)
for x, y in res:
    print(x)

Submission status: Runtime Error

Solution code:
def reroot(nodeCount, edges, identity, merge, addNode):
    adjacents = [list() for _ in range(nodeCount)]
    indexForAdjacents = [list() for _ in range(nodeCount)]
    for u, v in edges:
        indexForAdjacents[u].append(len(adjacents[v]))
        indexForAdjacents[v].append(len(adjacents[u]))
        adjacents[u].append(v)
        adjacents[v].append(u)
    childSubtreeRes = [[identity]*len(adjacents[i]) for i in range(nodeCount)]
    nodeRes = [identity]*nodeCount
    parents = [-1]*nodeCount
    order = [0]*nodeCount
    index = 0
    stack = [0]
    while stack:
        node = stack.pop()
        order[index] = node
        index += 1
        for adjacent in adjacents[node]:
            if adjacent == parents[node]:
                continue
            stack.append(adjacent)
            parents[adjacent] = node
    for node in reversed(order):
        parent = parents[node]
        result = identity
        parentIndex = -1
        for j in range(len(adjacents[node])):
            if adjacents[node][j] == parent:
                parentIndex = j
                continue
            result = merge(result, childSubtreeRes[node][j])
        childSubtreeRes[parent][indexForAdjacents[node][parentIndex]] = addNode(result, node)
    for node in order:
        accumsFromTail = [identity]*len(adjacents[node])
        for j in range(len(adjacents[node])-1, 0, -1):
            accumsFromTail[j - 1] = merge(childSubtreeRes[node][j], accumsFromTail[j])
        accum = identity
        for j in range(len(adjacents[node])):
            result = addNode(merge(accum, accumsFromTail[j]), node)
            childSubtreeRes[adjacents[node][j]][indexForAdjacents[node][j]] = result
            accum = merge(accum, childSubtreeRes[node][j])
        nodeRes[node] = addNode(accum, node)
    return nodeRes

def fun(v):
    ret = 1
    for i in range(2, v+1):
        ret = ret * i % mod
    return ret
  
mod = 10**9 + 7
int1 = lambda x: int(x) - 1
merge = lambda p, q: (p[0] * q[0] * pow(fun(q[1]), mod-2, mod) % mod, p[1] + q[1])
addNode = lambda value, idx: (value[0] * fun(value[1]) % mod, value[1] + 1)
N = int(input())
identity = (1, 0)
edges = [tuple(map(int1, input().split())) for _ in range(N-1)]
res = reroot(N, edges, identity, merge, addNode)
for x, y in res:
    print(x)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)

MOD = 10 ** 9 + 7
inv = [None, 1]
for i in range(2, 10 ** 5 + 1):
    inv.append(MOD - MOD // i * inv[MOD % i] % MOD)

fact = [1]
ifact = [1]
for i in range(1, 10 ** 5 + 1):
    fact.append((i * fact[-1]) % MOD)
    ifact.append((inv[i] * ifact[-1]) % MOD)


class Node:
    def __init__(self, ind):
        self.ind = ind
        self.val = 1
        self.ndesc = 1
        self.neighs = []


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

stack = [(-1, nodes[0])]
for i in range(N):
    fro, node = stack[i]
    for neigh in node.neighs:
        if neigh.ind == fro:
            continue
        stack.append((node.ind, neigh))

for i in range(N - 1, -1, -1):
    fro, node = stack[i]
    node.val = node.val * fact[node.ndesc - 1] % MOD
    if fro == -1:
        continue
    nodes[fro].ndesc += node.ndesc
    nodes[fro].val = nodes[fro].val * node.val * ifact[node.ndesc] % MOD

stack = [(-1, node, nodes[0].val * inv[N] % MOD)]
for i in range(N):
    fro, node, val = stack[i]
    node.val = val * node.ndesc * inv[max(1, N - node.ndesc)] % MOD
    for neigh in node.neighs:
        if neigh.ind == fro:
            continue
        stack.append((node.ind, neigh, node.val))

for i in range(N):
    print(nodes[i].val)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)

MOD = 10 ** 9 + 7
inv = [None, 1]
for i in range(2, 10 ** 5 + 1):
    inv.append(MOD - MOD // i * inv[MOD % i] % MOD)

fact = [1]
ifact = [1]
for i in range(1, 10 ** 5 + 1):
    fact.append((i * fact[-1]) % MOD)
    ifact.append((inv[i] * ifact[-1]) % MOD)


class Node:
    def __init__(self, ind):
        self.ind = ind
        self.val = 1
        self.ndesc = 1
        self.neighs = []

    def calc(self, fro):
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.calc(self.ind)
            self.val = self.val * neigh.val * ifact[neigh.ndesc] % MOD
            self.ndesc += neigh.ndesc
        self.val = self.val * fact[self.ndesc - 1] % MOD

    def comp(self, fro, carry):
        self.val = carry * self.ndesc * inv[max(1, N - self.ndesc)] % MOD
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.comp(self.ind, self.val)


N = int(input())
nodes = [Node(i) for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].neighs.append(nodes[b - 1])
    nodes[b - 1].neighs.append(nodes[a - 1])
nodes[0].calc(0)
nodes[0].comp(0, (nodes[0].val * inv[N]) % MOD)
for i in range(N):
    print(nodes[i].val)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 * 2)

MOD = 10 ** 9 + 7
inv = [None, 1]
for i in range(2, 10 ** 5 + 1):
    inv.append(MOD - MOD // i * inv[MOD % i] % MOD)

fact = [1]
ifact = [1]
for i in range(1, 10 ** 5 + 1):
    fact.append((i * fact[-1]) % MOD)
    ifact.append((inv[i] * ifact[-1]) % MOD)


class Node:
    def __init__(self, ind):
        self.ind = ind
        self.val = 1
        self.ndesc = 1
        self.neighs = []

    def calc(self, fro):
        subdescs = []
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.calc(self.ind)
            self.val *= neigh.val
            self.ndesc += neigh.ndesc
            subdescs.append(neigh.ndesc)
        self.val = self.val * fact[self.ndesc - 1] % MOD
        for subdesc in subdescs:
            self.val = self.val * ifact[subdesc] % MOD

    def comp(self, fro, carry):
        self.val = carry * self.ndesc * inv[max(1, N - self.ndesc)] % MOD
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.comp(self.ind, self.val)


N = int(input())
nodes = [Node(i) for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].neighs.append(nodes[b - 1])
    nodes[b - 1].neighs.append(nodes[a - 1])
nodes[0].calc(0)
nodes[0].comp(0, (nodes[0].val * inv[N]) % MOD)
for i in range(N):
    print(nodes[i].val)

Submission status: Runtime Error

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 10)

MOD = 10 ** 9 + 7
inv = [None, 1]
for i in range(2, 10 ** 5 + 1):
    inv.append(MOD - MOD // i * inv[MOD % i] % MOD)

fact = [1]
ifact = [1]
for i in range(1, 10 ** 5 + 1):
    fact.append((i * fact[-1]) % MOD)
    ifact.append((inv[i] * ifact[-1]) % MOD)


class Node:
    def __init__(self, ind):
        self.ind = ind
        self.val = 1
        self.ndesc = 1
        self.neighs = []

    def calc(self, fro):
        subdescs = []
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.calc(self.ind)
            self.val *= neigh.val
            self.ndesc += neigh.ndesc
            subdescs.append(neigh.ndesc)
        self.val = self.val * fact[self.ndesc - 1] % MOD
        for subdesc in subdescs:
            self.val = self.val * ifact[subdesc] % MOD

    def comp(self, fro, carry):
        self.val = carry * self.ndesc * inv[max(1, N - self.ndesc)] % MOD
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.comp(self.ind, self.val)


N = int(input())
nodes = [Node(i) for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].neighs.append(nodes[b - 1])
    nodes[b - 1].neighs.append(nodes[a - 1])
nodes[0].calc(0)
nodes[0].comp(0, (nodes[0].val * inv[N]) % MOD)
for i in range(N):
    print(nodes[i].val)

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
inv = [None, 1]
for i in range(2, 10 ** 5 + 1):
    inv.append((MOD - MOD // i * inv[MOD % i]) % MOD)

fact = [1]
ifact = [1]
for i in range(1, 10 ** 5 + 1):
    fact.append((i * fact[-1]) % MOD)
    ifact.append((inv[i] * ifact[-1]) % MOD)


class Node:
    def __init__(self, ind):
        self.ind = ind
        self.val = 1
        self.ndesc = 1
        self.neighs = []

    def calc(self, fro):
        subdescs = []
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.calc(self.ind)
            self.val *= neigh.val
            self.ndesc += neigh.ndesc
            subdescs.append(neigh.ndesc)
        self.val = self.val * fact[self.ndesc - 1] % MOD
        for subdesc in subdescs:
            self.val = self.val * ifact[subdesc] % MOD

    def comp(self, fro, carry):
        self.val = carry * self.ndesc * inv[max(1, N - self.ndesc)] % MOD
        for neigh in self.neighs:
            if neigh.ind == fro:
                continue
            neigh.comp(self.ind, self.val)


N = int(input())
nodes = [Node(i) for i in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].neighs.append(nodes[b - 1])
    nodes[b - 1].neighs.append(nodes[a - 1])
nodes[0].calc(0)
nodes[0].comp(0, (nodes[0].val * inv[N]) % MOD)
for i in range(N):
    print(nodes[i].val)

Submission status: Runtime Error

Solution code:
n = int(input())
e = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

mod = 10**9+7

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


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


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


child = [0] * n


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


dfs1()

a = [0] * n


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


dfs2()

b = [0] * n


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

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


dfs3()

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

Submission status: Runtime Error

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

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

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

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

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

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

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

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

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

Submission status: Runtime Error

Solution code:
n = int(input()); arr = [list(map(int,input().split())) for _ in range(n-1)]
graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1);graph[b-1].append(a-1)

mod = 10**9+7
fac = [1]*(n+1)
inv = [1]*(n+1)
ifac = [1]*(n+1)
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = (- (mod//i)*inv[(mod%i)]) % mod
    ifac[i] = ifac[i-1] * inv[i] % mod

parents = [-1]*n
children = [[] for _ in range(n)]
orders = []
stack = [0]
flags = [True] * n; flags[0] = False
while stack:
    tmp = stack.pop()
    orders.append(tmp)
    for node in graph[tmp]:
        if flags[node]:
            flags[node] = False
            children[tmp].append(node)
            stack.append(node)
            parents[node] = tmp

size = [1] * (n+1)
dp = [1] * (n+1)    
for child in orders[::-1]:
    parent = parents[child]
    size[parent] += size[child]
    dp[child] = dp[child] * fac[size[child]-1] % mod
    dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
_ = size.pop();_ = dp.pop()

size2 = [n-i+1 for i in size]
dp2 = [1] * n
for parent in orders[1:]:
    child = parents[parent]
    #dp2[parent] = dp2[parent] * fac[size2[parent]-2] * dp2[child] * ifac[size2[child]-1] * dp[child] * ifac[size[child]-1] * pow(dp[parent], mod-2, mod) * fac[size[parent]] % mod
    dp2[parent] = dp2[parent] * fac[n-1] * size[parent] * dp2[child] ifac[size2[child]] % mod
    
for i in range(n):
    #print(fac[n-1]*dp[i]*ifac[size[i]-1]*dp2[i]*ifac[size2[i]-1] % mod)
    print(dp2[i])

Submission status: Runtime Error

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

Q = 10**9+7

def subtrees(N, E, v):
    # N: vertex
    # E: edges
    # v: one vertex
    # return: directed edges adopted to tree dp
    from collections import deque
    ret_first = deque()
    ret_second = deque()
    V = [False]*N
    d = deque([v])
    while d:
        t = d.popleft()
        if V[t]:
            continue
        else:
            V[t] = True
        for e in E[t]:
            if not V[e]:
                d.append(e)
                ret_first.appendleft((t,e))
                ret_second.append((e,t))
    return list(ret_first + ret_second)

def get_number_of_vertex_with_subtrees(E, subtrees):
    # E: edges
    # subtrees: directed edges adopted to tree dp
    from collections import defaultdict
    d = defaultdict( lambda: 1)
    for s, t in subtrees:
        for v in E[t]:
            if v == s:
                continue
            d[(s,t)] += d[(t,v)]
    return d

def getInv(N):
    inv = [0] * (N + 1)
    inv[1] = 1
    for i in range(2, N + 1):
        inv[i] = (-(Q // i) * inv[Q % i]) % Q
    return inv

def factorials(N):
    invs = getInv(N)
    factorials = [1]
    inv_factorials = [1]
    for i in range(N):
        factorials.append( factorials[-1]*(i+1)%Q)
        inv_factorials.append( inv_factorials[-1]*invs[i+1]%Q)
    return factorials, inv_factorials

def main():
    from collections import defaultdict
    N = int( input())
    E = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = map( lambda x: int(x)-1, input().split())
        E[a].append(b)
        E[b].append(a)
    subtree = subtrees(N,E,0)
    num_subtree = get_number_of_vertex_with_subtrees(E, subtree)
    F, G = factorials(N)
    d = defaultdict( int)
    for s, t in subtree:
        z = 1
        count = 0
        for v in E[t]:
            if v == s:
                continue
            count += num_subtree[(t,v)]
            z *= G[num_subtree[(t,v)]]
            z %= Q
            z *= d[(t,v)]
            z %= Q
        z *= F[count]
        z %= Q
        d[(s,t)] = z
    ANS = []
    for v in range(N):
        z = 1
        count = 0
        for e in E[v]:
            count += num_subtree[(v,e)]
            z *= G[num_subtree[(v,e)]]
            z %= Q
            z *= d[(v,e)]
            z %= Q
        z *= F[count]
        z %= Q
        ANS.append(z)

    print( "\n".join( map( str, ANS)))
    
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7

m = 2*10**5+5
fac = [0] * m
finv = [0] * m
inv = [0] * m


def COMBinitialize(m):
    fac[0] = 1
    finv[0] = 1
    if m > 1:
        fac[1] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, m):
            fac[i] = fac[i-1] * i % MOD
            inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
            finv[i] = finv[i - 1] * inv[i] % MOD


COMBinitialize(m)


def COMB(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


class DP():
    def __init__(self, dp=modint(1), t=0):
        self.dp = dp
        self.t = t

    def __iadd__(self, other):
        self.dp *= other.dp
        self.dp *= COMB(self.t+other.t, self.t)
        self.t += other.t
        return self

    def __sub__(self, other):
        res = DP(self.dp, self.t)
        res.t -= other.t
        res.dp /= COMB(res.t+other.t, res.t)
        res.dp /= other.dp
        return res

    def add_root(self):
        return DP(self.dp, self.t + 1)


def main():
    import sys
    input = sys.stdin.buffer.readline
    N = int(input())
    edge = [[] for _ in range(N)]
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)

    dp = [DP() for _ in range(N+5)]

    def dfs(v, p=-1):
        for u in edge[v]:
            if u == p:
                continue
            dfs(u, v)
            dp[v] += dp[u].add_root()

    def bfs(v, p=-1):
        for u in edge[v]:
            if u == p:
                continue
            d = dp[v] - dp[u].add_root()
            dp[u] += d.add_root()
            bfs(u, v)

    dfs(0)
    bfs(0)
    for i in range(N):
        print(dp[i].add_root().dp)


if __name__ == '__main__':
    main()