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:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, a: "List[int]", b: "List[int]"):
    ff = [1] * (N + 1)
    for i in range(1, N+1):
        ff[i] = (ff[i-1] * i) % MOD
    iff = [pow(ff[i], MOD-2, MOD) for i in range(N+1)]
    cache = {}
    def f(source, sink):
        key = (source, sink)
        if key in cache:
            return cache[key]
        c, ic, p = 0,1, 1
        for e in edges[sink]:
            if e == source:
                continue
            cc, pp = f(sink, e)
            p = (p * pp) % MOD
            c += cc
            ic = (ic * iff[cc]) % MOD
        cache[key] = c+1, p * (ff[c] * ic) % MOD
        return cache[key]

    def g(node):
        c, ic, p = 0, 1, 1
        for e in edges[node]:
            cc, pp = f(node, e)
            c += cc
            p = (p * pp) % MOD
            ic = (ic * iff[cc]) 
        return ((ff[c] * ic) % MOD) * p
    
    edges = [[] for _ in range(N+1)]
    for aa, bb in zip(a, b):
        edges[aa].append(bb)
        edges[bb].append(aa)
    
    for i in range(1, N+1):
        print(g(i))
        


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int


def solve(N: int, a: "List[int]", b: "List[int]"):
    ff = [1] * (N + 1)
    for i in range(1, N+1):
        ff[i] = (ff[i-1] * i) % MOD
    iff = [pow(ff[i], MOD-2, MOD) for i in range(N+1)]
    cache = {}
    def f(source, sink):
        key = (source, sink)
        if key in cache:
            return cache[key]
        c, ic, p = [],1, 1
        for e in edges[sink]:
            if e == source:
                continue
            cc, pp = f(sink, e)
            p = (p * pp) % MOD
            c.append(cc)
            ic = (ic * iff[cc]) % MOD
        cache[key] = sum(c)+1, p * (ff[sum(c)] * ic) % MOD
        return cache[key]

    def g(node):
        c, ic, p = 0, 1, 1
        for e in edges[node]:
            cc, pp = f(node, e)
            c += cc
            p = (p * pp) % MOD
            ic = (ic * iff[cc]) 
        return ((ff[c] * ic) % MOD) * p
    
    edges = [[] for _ in range(N+1)]
    for aa, bb in zip(a, b):
        edges[aa].append(bb)
        edges[bb].append(aa)
    
    for i in range(1, N+1):
        print(g(i))
        


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())
G = defaultdict(set)
for _ in range(N - 1):
  a, b = map(int, input().split())
  G[a - 1].add(b - 1)
  G[b - 1].add(a - 1)

memo = {}
def calc(X, Y):
  if len(X) == N - 1:
    return 1
  K = (frozenset(X), frozenset(Y))
  if K not in memo:
    memo[K] = sum(calc(X | {y}, (Y - {y}) | (G[y] - X)) for y in Y) % (10** 9 + 7)
  return memo[K]

for k in range(N):
  print(calc({k}, G[k]))

Submission status: Runtime Error

Solution code:
mod = 10**9+7
fact = [1]*(2*10**5+1)
for n in range(1,2*10**5+1):
    fact[n] = n*fact[n-1]%mod
factinv = [1]*(2*10**5+1)
inv = [1]*(2*10**5+1)
for n in range(1,2*10**5+1):
    factinv[n] = pow(fact[n],mod-2,mod)
    inv[n] = pow(n,mod-2,mod)
def comb(n,k):
    return fact[n]*factinv[k]*factinv[n-k]%mod

N = int(input())
g = [[] for _ in range(N)]

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

p = [-1]*N
p[0] = 0
q = [0]
while q:
    i = q.pop()
    for j in g[i]:
        if p[j]==-1:
            p[j] = i
            q.append(j)

c = [[] for _ in range(N)]
for i in range(1,N):
    c[p[i]].append(i)

cn = [-1]*N
def rec(n):
    if cn[n] != -1:
        return cn[n]
    res = 0
    for i in c[n]:
        res += rec(i)+1
    cn[n] = res
    return res

cn[0] = rec(0)    

ans = [0]*N

def dfs(n):
    res = fact[cn[n]]
    for c in g[n]:
        if c==p[n]:
            continue
        res *= factinv[cn[c]+1]*dfs(c)
        res %= mod
    return res

ans[0] = dfs(0)

q = [0]
while q:
    i = q.pop()
    for j in g[i]:
        if ans[j]==0:
            ans[j] = ans[i]*(cn[j]+1)*inv[N-1-cn[j]]%mod
            q.append(j)

for i in range(N):
    print(ans[i])

Submission status: Runtime Error

Solution code:
def main():
    import sys
    from collections import deque
    input = sys.stdin.readline

    # comb init
    mod = 1000000007
    nmax = 10 ** 5 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

    def comb(n, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

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


    que = deque()
    que.append(1)
    seen = [-1] * (N+1)
    seen[1] = 0
    par = [0] * (N+1)
    child = [[] for _ in range(N+1)]
    seq = []
    while que:
        v = que.popleft()
        seq.append(v)
        for u in adj[v]:
            if seen[u] == -1:
                seen[u] = seen[v] + 1
                par[u] = v
                child[v].append(u)
                que.append(u)
    seq.reverse()

    dp = [1] * (N+1)
    size = [1] * (N+1)
    for v in seq:
        for u in child[v]:
            size[v] += size[u]
        L = size[v] - 1
        for u in child[v]:
            dp[v] = (dp[v] * (dp[u] * comb(L, size[u]))%mod)%mod
            L -= size[u]

    seq.reverse()
    dp2 = [0] * (N+1)
    for v in seq:
        if v == 1:
            dp2[1] = dp[1]
            continue
        p = par[v]
        dp2[v] = dp[v]
        PP = (dp2[p] * pow((dp[v] * comb(N-1, size[v]))%mod, mod-2, mod))%mod
        dp2[v] = (dp2[v] * PP * comb(N-1, size[v]-1))%mod
    for v in range(1, N+1):
        print(dp2[v])


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())
G = defaultdict(set)
for _ in range(N - 1):
  a, b = map(int, input().split())
  G[a - 1].add(b - 1)
  G[b - 1].add(a - 1)

memo = {}
def calc(x):
  x = (frozenset(x[0]), frozenset(x[1]))
  if x not in memo:
    count = 0
    if x[1]:
      for y in x[1]:
        count += calc((x[0] | {y}, (x[1] - {y}) | (G[y] - x[0])))
      memo[x] = count
    else:
      memo[x] = 1
  return memo[x]

for k in range(N):
  print(calc(({k}, G[k])))

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)
	
	c[p] = data
	return data

edge_table = [set() for _ in range(N)]
count_table = [set() for _ in range(N)]
for i, e in enumerate(e_table):
	count_table[len(e)].add(i)
	for j in e_table[i]:
		edge_table[i].add(j)

while len(count_table[1]) > 0:
#	print(count_table, edge_table)
	n = count_table[1].pop()
	p = edge_table[n].pop()
#	print(n, p)
	calc(n, p)
	p_count = len(edge_table[p])
	count_table[p_count].remove(p)
	count_table[p_count - 1].add(p)
	edge_table[p].remove(n)

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

Submission status: Runtime Error

Solution code:
import sys


# 2乗の木DP

def prepare(n, MOD):
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def nhr(factorials, invs, n, r, MOD):
    return factorials[n + r - 1] * invs[n - 1] * invs[r] % MOD


def dfs0(links):
    q = [(0, -1)]
    while q:
        v, p = q.pop()
        links[v].discard(p)
        links[v] = list(links[v])
        q.extend((u, v) for u in links[v])


def dfs1(links, st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd):
    q = [(0, -1, 0)]
    while q:
        v, p, o = q.pop()
        if o == 0:
            # 初回訪問
            q.append((v, p, 1))
            q.extend((u, v, 0) for u in links[v])
        else:
            # 子の探索が終わった後の砲門
            curr_count = [0]
            curr_pattern = [1]
            for u in links[v]:
                stc_u = st_count_fwd[u][-1] + 1
                new_pattern = factorials[curr_count[-1] + stc_u] * invs[curr_count[-1]] * invs[stc_u] % MOD
                curr_pattern.append(new_pattern * curr_pattern[-1] * st_pattern_fwd[u][-1] % MOD)
                curr_count.append(curr_count[-1] + stc_u)
            st_count_fwd[v] = curr_count
            st_pattern_fwd[v] = curr_pattern
            curr_count = [0]
            curr_pattern = [1]
            for u in reversed(links[v]):
                stc_u = st_count_fwd[u][-1] + 1
                new_pattern = factorials[curr_count[-1] + stc_u] * invs[curr_count[-1]] * invs[stc_u] % MOD
                curr_pattern.append(new_pattern * curr_pattern[-1] * st_pattern_fwd[u][-1] % MOD)
                curr_count.append(curr_count[-1] + stc_u)
            st_count_bwd[v] = curr_count[::-1]
            st_pattern_bwd[v] = curr_pattern[::-1]


def dfs2(links, st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd, ans):
    def sub(v, pc, pp):
        # print(v, pc, pp)
        if pc == 0:
            ans[v] = st_pattern_fwd[v][-1]
        else:
            cc = st_count_fwd[v][-1]
            cp = st_pattern_fwd[v][-1]
            pattern = factorials[cc + pc] * invs[cc] * invs[pc] % MOD
            pattern = pattern * cp * pp % MOD
            ans[v] = pattern

        for i, u in enumerate(links[v]):
            fc = st_count_fwd[v][i]
            fp = st_pattern_fwd[v][i]
            bc = st_count_bwd[v][i + 1]
            bp = st_pattern_bwd[v][i + 1]
            p1 = factorials[fc + bc] * invs[fc] * invs[bc] % MOD
            p1 = p1 * fp * bp % MOD
            p2 = factorials[fc + bc + pc] * invs[fc + bc] * invs[pc] % MOD
            p2 = p2 * p1 * pp % MOD
            # print(v, u, fc, fp, bc, bp, p1, p2)
            sub(u, fc + bc + pc + 1, p2)

    sub(0, 0, 1)


n, *ab = map(int, sys.stdin.buffer.read().split())
links = [set() for _ in range(n)]
for a, b in zip(ab[0::2], ab[1::2]):
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
MOD = 10 ** 9 + 7
factorials, invs = prepare(n, MOD)
st_count_fwd = [[] for _ in range(n)]
st_count_bwd = [[] for _ in range(n)]
st_pattern_fwd = [[] for _ in range(n)]
st_pattern_bwd = [[] for _ in range(n)]
ans = [0] * n

dfs0(links)
dfs1(links, st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd)
# print(st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd, sep='\n')
dfs2(links, st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd, ans)
print('\n'.join(map(str, ans)))

Submission status: Runtime Error

Solution code:
N = int(input())
a = []
b = []
for i in range(N-1):
    ai, bi = list(map(int, input().split()))
    a.append(ai)
    b.append(bi)


count = 0

def func_count(line, node):
    print(line,node)
    global count
    aa = 0
    for i in range(N-1):
        if i==line:
            continue
        if a[i]==node:
            aa += 1
            func_count(i, b[i])
        if b[i]==node:
            aa += 1
            func_count(i, a[i])
    if aa>2:
        count += aa-1

for i in range(N):
    count=0
    func_count(-1, i+1)
    print(count)

Submission status: Runtime Error

Solution code:
n = int(input())

mod = 10**9 + 7

def expo(x,n):
    var = 1
    while n>0:
        if n%2 == 1:
            var = (var*x) % mod
        x = (x*x)%mod
        n = n>>1
    return var

def conbi(*x):
    num = 1
    den = 1
    for i in range(1,sum(x)+1):
        num = (num*i)%mod
    for i in x:
        for j in range(1,i+1):
            den = (den * j)%mod
    return (num*expo(den,mod-2))%mod

path = [set()]*n
pathq= [0]*n
path2= [set()]*n
path2q=[0]*n
cross =[]

for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].add(b)
    pathq[a] += 1
    if pathq[a] == 3:
        cross.append(a)
    path[b].add(a)
    pathq[b] += 1
    if pathq[b] == 3:
        cross.append(b)

memo = {}
def go(i,j):
    if (i,j) in memo.keys():
        return memo[(i,j)]
    else:
        memo[(i,j)] = [1,1]
        cnt = []
        meth = 1
        for k in path[j]:
            if i != k:
                [x,y] = go(j,k)
                meth *= y
                meth %= mod
                cnt.append(x)
        memo[(i,j)] = [sum(cnt)%mod, meth*conbi(*cnt)%mod]
        return memo[(i,j)]

for i in range(n):
    ans = 1
    cnt = []
    meth = 1
    for k in path[i]:
        [x,y] = go(i,k)
        meth *= y
        meth %= mod
        cnt.append(x)
    print(meth*conbi(*cnt)%mod)

Submission status: Runtime Error

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

mod = 10 ** 9 + 7
N = 1000000

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

n = int(input())

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

memo = [[0, 0] for i in range(n)]

def dfs(cur, pre):
    if E[cur] == [pre]:
        memo[cur] = [1, 1]
        return 1, 1
    ns = []
    cnt = 1
    for e in E[cur]:
        if e != pre:
            ni, cnti = dfs(e, cur)
            ns.append(ni)
            cnt = cnt * cnti % mod
    s = sum(ns)
    S = s
    for ni in ns:
        cnt = cnt * cmb(s, ni) % mod
        s -= ni
    memo[cur] = [S, cnt]
    return S, cnt

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

Submission status: Runtime Error

Solution code:
class fact():
    def __init__(self, i, mod):
        self.l = [1] * (i+1)
        for i in range(1, i+1):
            self.l[i] = self.l[i-1] * i
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 5) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)


def main():
    N = int(input())
    d = {}
    mod = 10**9 + 7
    f = fact(N, mod)
    for i in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for i in range(1, N+1):
        v = set()
        r, t = solve(i, N, v, f, d)
        print(r % mod)
def solve(n, a, v, f, d):
    v.add(n)
    x = 0
    unv = []
    for i in d[n]:
        if i not in v:
            x += 1
            unv.append(i)
    if x == 1:
        r, t = solve(unv[0], a-1, v, f, d)
        return r, t + 1
    if x == 0:
        return 1, 1
    t = 1
    r = 1
    for i in unv:
        rr, tt = solve(i, a-1, v, f, d)
        t += tt
        r *= rr
        r *= f.g2[tt]
    r *= f.l[t-1]
    return r, t
main()

Submission status: Runtime Error

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


n_max=(10**5+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod

edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
Ans=[]
inf=10**6

#親と入次数を求める
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)
 
#トポソする
from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

Used=[False]*n
C=[0]*n
for i in reversed(range(n)):
  v=TS[i]
  Used[v]=True
  for g in edge[v]:
    if not Used[g]:
      C[g]+=C[v]+1

D=[1]*n
for i in reversed(range(n)):
  v=TS[i]
  D[v]=(D[v]*(C[v]+1))%mod
  if Par[v]!=-1:
    D[Par[v]]=(D[Par[v]]*D[v])%mod
E=[1]*n
for i in range(n):
  v=TS[i]
  if Par[v]!=-1:
    cur=E[Par[v]]
  else:
    cur=1
  
  for g in edge[v]:
    if g!=Par[v]:
      cur=(cur*D[g])%mod
  for g in edge[v]:
    if g!=Par[v]:
      E[g]=(cur*pow(D[g],mod-2,mod)*(n-C[g]-1))%mod
def I(x):
  return pow(x,mod-2,mod)


for i in range(n):
  print((F[n]*I(D[i])*I(E[i])*comb(n-1,C[i]))%mod)

Submission status: Runtime Error

Solution code:
 class fact():
    def __init__(self, i, mod):
        self.l = [1] * (i+1)
        for i in range(1, i+1):
            self.l[i] = self.l[i-1] * i
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 5) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)


def main():
    N = int(input())
    d = {}
    mod = 10**9 + 7
    f = fact(N, mod)
    for i in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for i in range(1, N+1):
        v = set()
        r, t = solve(i, N, v, f, d)
        print(r % mod)
def solve(n, a, v, f, d):
    v.add(n)
    x = 0
    unv = []
    for i in d[n]:
        if i not in v:
            x += 1
            unv.append(i)
    if x == 1:
        r, t = solve(unv[0], a-1, v, f, d)
        return r, t + 1
    if x == 0:
        return 1, 1
    t = 1
    r = 1
    for i in unv:
        rr, tt = solve(i, a-1, v, f, d)
        t += tt
        r *= rr
        r *= f.g2[tt]
    r *= f.l[t-1]
    return r, t
main()

Submission status: Runtime Error

Solution code:
n = int(input())

mod = 10**9 + 7

def expo(x,n):
    var = 1
    while n>0:
        if n%2 == 1:
            var = (var*x) % mod
        x = (x*x)%mod
        n = n>>1
    return var

def conbi(*x):
    num = 1
    den = 1
    for i in range(1,sum(x)+1):
        num = (num*i)%mod
    for i in x:
        for j in range(1,i+1):
            den = (den * j)%mod
    return (num*expo(den,mod-2))%mod

path = [set()]*n
pathq= [0]*n
path2= [set()]*n
path2q=[0]*n
cross =[]

for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].add(b)
    pathq[a] += 1
    if pathq[a] == 3:
        cross.append(a)
    path[b].add(a)
    pathq[b] += 1
    if pathq[b] == 3:
        cross.append(b)

memo = {[]:[]}
def go(i,j):
    if (i,j) in memo.keys():
        return memo[(i,j)]
    else:
        memo[(i,j)] = [1,1]
        cnt = []
        meth = 1
        for k in path[j]:
            if i != k:
                [x,y] = go(j,k)
                meth *= y
                meth %= mod
                cnt.append(x)
        memo[(i,j)] = [sum(cnt)%mod, meth*conbi(*cnt)%mod]
        return memo[(i,j)]

for i in range(n):
    ans = 1
    cnt = []
    meth = 1
    for k in path[i]:
        [x,y] = go(i,k)
        meth *= y
        meth %= mod
        cnt.append(x)
    print(meth*conbi(*cnt)%mod)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys, resource
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

resource.setrlimit(resource.RLIMIT_STACK,
                   (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

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):
    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, 0)[1])


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



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys, resource
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

# resource.setrlimit(resource.RLIMIT_STACK,
#                    (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

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):
    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, 0)[1])


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



if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
tree = [[]for _ in range(N + 1)]
for _ in range(N):
  p,c = map(int,input().rstrip().split(" "))
  tree[c].append(p)
  tree[p].append(c)
for i in range(1,N+1):
  print(tree[i])

Submission status: Runtime Error

Solution code:
MOD = 10**9 + 7
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD

memo = {}


def query(adj, pos, prev):
    # returns (pattern, count)
    # print("q", pos, prev)
    if (pos, prev) in memo:
        return memo[(pos, prev)]
    if len(adj[pos]) == 1 and prev in adj[pos]:
        memo[(pos, prev)] = (1, 1)
    else:
        pattern = 1
        count = 0
        for nxt in adj[pos]:
            if nxt == prev:
                continue
            ptn, cnt = query(adj, nxt, pos)
            count += cnt
            pattern = (pattern * ptn) * \
                (FACT[count] * INV[cnt] * INV[count-cnt]) % MOD
        count += 1
        memo[(pos, prev)] = (pattern, count)
    return memo[(pos, prev)]


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    for i in range(N):
        pattern, count = query(adj, i, -1)
        print(pattern)


if __name__ == "__main__":
    main()

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, n * 10):
    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
    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
pa = [-1] * n


def dfs_ch(i=0, r=-1):
    pa[i] = r
    c = 1
    for j in e[i]:
        if j != r:
            c += dfs_ch(j, i)
    child[i] = c
    return c


dfs_ch()

f = [0] * n


def dfs_f(i=0, r=-1):
    c = 1
    d = child[i]-1
    for j in e[i]:
        if j != r:
            c *= comb(d, child[j])
            d -= child[j]
            c *= dfs_f(j, i)
            c %= mod
    f[i] = c
    return c


dfs_f()
g = [0] * n


def dfs_g(i=0, r=-1, c=1):
    if r != -1:
        d = n - child[i]-1
        for j in e[r]:
            if j != i:
                if j == pa[r]:
                    pass
                else:
                    c *= f[j]
                    c *= comb(d, child[j])
                    d -= child[j]
                    c %= mod
    g[i] = c
    for j in e[i]:
        if j != r:
            dfs_g(j, i, c)


dfs_g()

for i in range(n):
    print(f[i]*g[i]*comb(n-1, child[i]-1) % mod)