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:
from itertools import accumulate,chain

MOD = 10**9+7


# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m




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

factorio = tuple(chain((1,),accumulate(range(1,N+1), lambda x,y: (x*y)%MOD)))

patterns = dict()
childrens = dict()
def rec(a,b):
    if (a,b) in patterns:
        return patterns[(a,b)], childrens[(a,b)]
    if a != -1 and len(adj[b]) == 1:
        patterns[(a,b)] = 1
        childrens[(a,b)] = 1
        return 1,1

    prod = 1 # product of patterns
    d = 1 # denominator of multinomial coefficient
    n = 0 # total childrens
    for c in adj[b]:
        if a == c:
            continue
        p,c = rec(b,c)
        prod *= p
        prod %= MOD
        d *= factorio[c]
        d %= MOD
        n += c

    patterns[(a,b)] = (prod*factorio[n]*modinv(d,MOD))%MOD
    childrens[(a,b)] = n+1
    return patterns[(a,b)], childrens[(a,b)]

for a,b in edges:
    rec(a,b)
    rec(b,a)

for k in range(N):
    p,c = rec(-1,k)
    print(p)

Submission status: Runtime Error

Solution code:
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)

dp = {}


def f(s):
    ts = tuple(s)
    if ts in dp:
        return dp[ts]
    if len(s) == n - 1:
        return 1

    ans = 0
    for si in s:
        for j in g[si]:
            if j in s:
                continue

            ans += f(s | {j})
    dp[ts] = ans
    return ans


for i in range(n):
    print(f({i}))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap

M = 10**9 + 7
@lru_cache(maxsize=None)
def fact(n):
    ret = 1
    for i in range(1, n+1):
        ret *= i
        ret %= M
    return ret

@mt
def slv(N, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    @lru_cache(maxsize=None)
    def f(u, p):
        n = 0
        r = 1
        nn = []
        for v in g[u]:
            if v == p:
                continue
            n_, r_ = f(v, u)
            r *= r_
            r %= M
            n += n_
            nn.append(n_)

        ret = fact(n) * r
        ret %= M
        for i in nn:
            ret //= fact(i)
        return n+1, ret

    for i in range(1, N+1):
        print(f(i, -1)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
M = 10 ** 9 + 7
N = int(input())

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

cache = [{} for _ in range(N)]

facts = [None]
facts_i = [None]
def cache_facts(n, M):
	f = 1
	for i in range(1, n + 1):
		f = (f * i) % M
		facts.append(f)
		facts_i.append(calc_inverse(f, M))

# inverse
def calc_inverse(n, law):
	if n == 1:
		return 1
	
	pre_r = law
	pre_x = 0
	pre_y = 1
	cur_r = n
	cur_x = 1
	cur_y = 0
	
	while True:
		d = pre_r // cur_r
		r = pre_r % cur_r
		
		nxt_r = r
		nxt_x = pre_x - d * cur_x
		nxt_y = pre_y - d * cur_y
		
		if nxt_r == 1:
			ret = nxt_x
			while ret < 0:
				ret += law;
			return ret;
		elif nxt_r == 0:
			return None
		
		pre_r = cur_r;
		pre_x = cur_x;
		pre_y = cur_y;
		cur_r = nxt_r;
		cur_x = nxt_x;
		cur_y = nxt_y;

cache_facts(N, M)

def calc(n, p):
	c = cache[n]
	if p in c:
		return c[p]
	
	e = e_table[n]
	if len(e) == 1 and e[0] == p:
		data = (1, 1)
	else:
		total_count = 0
		total_p_inv = 1
		total_patterns = 1
		for child in e:
			if child != p:
				count, patterns = calc(child, n)
		
				total_count += count
				total_p_inv = total_p_inv * facts_i[count] % M
				total_patterns = total_patterns * patterns % M
		
		data = (total_count + 1, ((facts[total_count] * total_p_inv) % M) * total_patterns % M)
	
#	print(n, p, data)
	
	c[p] = data
	return data

for i in range(N):
	print(calc(i, None)[1])

Submission status: Runtime Error

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

from collections import defaultdict
graph = defaultdict(list)
for i in range(n - 1):
    graph[ab[i][0] - 1].append(ab[i][1] - 1)
    graph[ab[i][1] - 1].append(ab[i][0] - 1)

childs = [-1] * n

def dfs(cur, prev):
    ret = 1
    for target in graph[cur]:
        if target != prev:
            ret += dfs(target, cur)
    childs[cur] = ret
    return ret

_ = dfs(0, -1)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, y//2)**2 * x % mod

def div(a, b):
    return mul(a, power(b, mod-2))

mod = 10 ** 9 + 7

tmpans = 1
for i in range(1, n+1):
    tmpans = tmpans * i % mod
for child in childs:
    tmpans = div(tmpans, child)

ans = [0] * n
ans[0] = tmpans

def dfs2(cur, prev):
    if cur != 0:
        # change cur <--> prev
        ans[cur] = div(ans[prev] * childs[cur] , n - childs[cur])

    for target in graph[cur]:
        if target != prev:
            dfs2(target, cur)

dfs2(0, -1)

for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(3*10**5)

n = int(input())
edge = [tuple(map(int, input().split())) for _ in range(n-1)]
mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

d = [{} for _ in range(n)]

def dfs(v, p):
    if p in d[v]:
        return d[v][p]
    num, count = 0, 1
    for next in connect[v]:
        if next != p:
            i, c = dfs(next, v)
            num += i
            count *= c
            count %= mod
            count *= comb(num, i)
            count %= mod
    num += 1
    d[v][p] = num, count
    return num, count

for i in range(n):
    dfs(i, -1)
    print(d[i][-1][1])

Submission status: Runtime Error

Solution code:
class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    mod = 10 ** 9 + 7
    nCr = nCrMod(mod)
    T = {}

    def h(n, f):
        if (n, f) in T:
            return T[(n, f)]
        r = 1
        cc = 0
        for i in E[n]:
            if i == f:
                continue
            p, c = h(i, n)
            cc += c
            r = r * p * nCr(cc, c) % mod
        T[(n, f)] = (r, cc + 1)
        return (r, cc + 1)


    for i in range(N):
        print(h(i, -1)[0])
main()