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: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
MOD = 10 ** 9 + 7
mod = MOD
n = N
fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


for i in range(1, n):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r or r < 0:
        return 0
    return fac[n] * caf[r] * caf[n - r]


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


def dfs(s, d):
    if s in D[d]:
        return D[d][s]
    res = []
    res2 = 1
    for sg in G[d]:
        if sg != s:
            res.append(dfs(d, sg) + 1)
            res2 *= D2[sg][d]
    sres = sum(res)
    D[d][s] = sres
    for sr in res:
        res2 *= ncr(sres, sr)
        res2 %= MOD
        sres -= sr
    D2[d][s] = res2
    return D[d][s]


for i in range(N):
    dfs(N + 1, i)

for i in range(N):
    print(D2[i][N + 1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

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() for _ in range(n)]
pathq= [0]*n

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

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 + 1, meth*conbi(*cnt)%mod]
        return memo[(i,j)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
M = 10 ** 9 + 7
def inv(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return x0

def comb(n, k):
    r1 = 1
    for i in range(k):
        r1 = r1 * (n - i) % M
    r2 = 1
    for i in range(k):
        r2 = r2 * (i + 1) % M
    return r1 * inv(r2, M) % M

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

def count(i, last):
    rs = []
    for n in g[i]:
        if n != last:
            rs.append(count(n, i))
    if len(rs) == 0:
        return (1, 1)
    if len(rs) == 0:
        return (rs[0][0], rs[0][1] + 1)
    sz = sum(v[1] for v in rs)
    allsz = sz + 1
    r = 1
    for v in rs:
        r = r * comb(sz, v[1]) * v[0] % M
        sz -= v[1]
    return (r, allsz)

    
for i in range(n):
    print(count(i, -1)[0])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
m = map(int, read().split())
AB = zip(m, m)

fn = 1
for i in range(2, n+1):
    fn = fn*i % MOD


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

for a,b in AB:
    E[a-1].append(b-1)
    E[b-1].append(a-1)

def call(e):
    if e in memo:
        return memo[e]
    a,b = e
    rev = 1
    size = 1
    for v in E[b]:
        if v == a:
            continue
        _rev, _size = call((b,v))
        size += _size
        rev = mod_mul(rev, _rev)

    rev = mod_mul(rev, size)
    memo[e] = (rev, size)
    return memo[e]


for k in range(n):
    rev = n
    for v in E[k]:
        _rev, _size = call((k,v))
        rev = mod_mul(rev, _rev)

    print(mod_div(fn, rev))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

MOD = 10**9 + 7
MAX_N = 10**6

fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

fac_inv = [1] + [0] * MAX_N
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

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

f_cnt = [0] * n
f_dp = [0] * n
def dfs1(p, v):
    val = 1
    cnt = 0
    for nv in edge[v]:
        if nv == p:
            continue
        ncnt, nval = dfs1(v, nv)
        val *= mod_nCr(cnt + ncnt, ncnt) 
        val *= nval
        val %= MOD
        cnt += ncnt
    f_cnt[v] = cnt + 1
    f_dp[v] = val
    return (cnt+1, val)

b_dp = [0] * n
def dfs2(p, v, pval):
    val = 1
    cnt = 0
    p_cnt = n - f_cnt[v]
    for nv in edge[v]:
        if nv == p:
            ncnt = p_cnt
            nval = pval
        else:
            ncnt, nval = f_cnt[nv], f_dp[nv]
        coef = mod_nCr(cnt + ncnt, ncnt) * nval % MOD
        val = val * coef % MOD
        b_dp[v] = val
        cnt += ncnt
    i = 0
    for nv in edge[v]:
        if nv == p:
            continue
        ncnt, nval = f_cnt[nv], f_dp[nv]
        coef = mod_nCr(n - 1, ncnt) * nval % MOD
        pp = val * pow(coef, MOD-2, MOD) % MOD
        i += 1
        dfs2(v, nv, pp)

dfs1(-1, 0)
dfs2(-1, 0, 1)
for item in b_dp:
    print(item)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 200002


def COMinit():
    fac[0] = fac[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % MOD

n = n_in()
E = [[] for i in range(n)]


fn = 1
for i in range(2, n+1):
    fn = fn*i % MOD


memo = {}

for _ in range(n-1):
    a,b = l_in()
    # print(a,b)
    E[a-1].append(b-1)
    E[b-1].append(a-1)

def call(e):
    if e in memo:
        return memo[e]
    a,b = e
    rev = 1
    size = 1
    for v in E[b]:
        if v == a:
            continue
        _rev, _size = call((b,v))
        size += _size
        rev = mod_mul(rev, _rev)

    rev = mod_mul(rev, size)
    memo[e] = (rev, size)
    return memo[e]


for k in range(n):
    rev = n
    for v in E[k]:
        _rev, _size = call((k,v))
        rev = mod_mul(rev, _rev)

    print(mod_div(fn, rev))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
MOD = 10 ** 9 + 7
mod = MOD
n = N
fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


for i in range(1, n):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r or r < 0:
        return 0
    return fac[n] * caf[r] * caf[n - r]


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


def dfs(s, d):
    if s in D[d]:
        return [D[d][s], D2[d][s]]
    res = []
    res2 = 1
    for sg in G[d]:
        if sg != s:
            tres = dfs(d, sg)
            res.append(tres[0] + 1)
            res2 *= tres[1]
    sres = sum(res)
    D[d][s] = sres
    for sr in res:
        res2 *= ncr(sres, sr)
        res2 %= MOD
        sres -= sr
    D2[d][s] = res2
    return [D[d][s], D2[d][s]]


for i in range(N):
    dfs(N + 1, i)

for i in range(N):
    print(D2[i][N + 1])

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate,chain
import sys

sys.setrecursionlimit(10000000)

MOD = 10**9+7


# mを法とするときのa^n
def modpow(a,n,m):
    res = 1
    t = a
    while n:
        if n%2:
            res = (res*t)%m
        t = (t*t)%m
        n //= 2
    return res

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


def solve(N,adj,edges):
    factorio = [1]*(N+1)
    t = 1
    for i in range(1,N+1):
        t *= i
        t %= MOD
        factorio[i] = t

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

            patterns[(a,b)] = (prod*factorio[n]*modpow(d,MOD-2, MOD))%MOD
            childrens[(a,b)] = n+1

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

    for k in range(N):
        rec(-1,k)
        print(patterns[(-1,k)])


if __name__ == '__main__':
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
     
    N = int(readline())
    m = map(int, read().split())
    edges = tuple((a-1,b-1) for a,b in zip(m, m))
    
    adj = [list() for _ in range(N)]
    for a,b in edges:
        adj[a].append(b)
        adj[b].append(a)

    solve(N,adj,edges)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate,chain
from sys import setrecursionlimit
from sys import stdin

setrecursionlimit(10000000)

MOD = 10**9+7


# mを法とするときのa^n
def modpow(a,n,m):
    res = 1
    t = a
    while n:
        if n%2:
            res = (res*t)%m
        t = (t*t)%m
        n //= 2
    return res

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


def solve(N,adj,edges):
    factorio = [1]*(N+1)
    t = 1
    for i in range(1,N+1):
        t *= i
        t %= MOD
        factorio[i] = t

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

            patterns[(a,b)] = (prod*factorio[n]*modpow(d,MOD-2, MOD))%MOD
            childrens[(a,b)] = n+1

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

    for k in range(N):
        rec(-1,k)
        print(patterns[(-1,k)])


if __name__ == '__main__':
    it = iter(stdin)
    N = int(next(it))
    adj = [list() for _ in range(N)]
    edges = []
    for _ in range(N-1):
        a,b = map(int,next(it).split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
        edges.append((a-1,b-1))

    solve(N,adj,edges)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 200002

fac  = [0]*MAX
finv = [0]*MAX
inv  = [0]*MAX

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        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 mod_COM(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;

COMinit()


n = n_in()
E = [[] for i in range(n)]

memo = {}

for _ in range(n-1):
    a,b = l_in()
    # print(a,b)
    E[a-1].append(b-1)
    E[b-1].append(a-1)

def call(e):
    if e in memo:
        return memo[e]
    a,b = e
    rev = 1
    size = 1
    for v in E[b]:
        if v == a:
            continue
        _rev, _size = call((b,v))
        size += _size
        rev = mod_mul(rev, _rev)

    rev = mod_mul(rev, size)
    memo[e] = (rev, size)
    return memo[e]


for k in range(n):
    rev = n
    for v in E[k]:
        _rev, _size = call((k,v))
        rev = mod_mul(rev, _rev)

    print(mod_div(fac[n], rev))

Submission status: Time Limit Exceeded

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):
    if n < 1:
        return 1
    return fact(n-1) * n

@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)

        # print(u, p, ret)
        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))

    # N = (10**4) * 1
    # AB = [(_, _+1) for _ in range(N-1)]
    # (slv(N, AB))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

class nCrMod():
    def __init__(self, mod, n):
        self.mod = mod
        self.fac = [1, 1] + [0] * n
        self.finv = [1, 1] + [0] * n
        self.inv = [0, 1] + [0] * n
        f, fi = self.fac[1], self.finv[1]
        for i in range(2, n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac[i] = f
            self.finv[i] = fi
            self.inv[i] = v

    def __call__(self, n, r):
        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, N)
    T = [{} for _ in range(N)]

    def h(n, f):
        if f in T[n]:
            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.finv[c] % mod
        r = r * nCr.fac[cc] % mod
        T[n][f] = (r, cc + 1)
        return (r, cc + 1)

    print('\n'.join(str(h(i, -1)[0]) for i in range(N)))

sys.setrecursionlimit(10 ** 6)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 200002

fac  = [0 for _ in range(MAX)]
finv = [0 for _ in range(MAX)]
inv  = [0 for _ in range(MAX)]

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        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 mod_COM(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;

COMinit()


n = n_in()

E = [[] for _ in range(n)]

memo = {}

for _ in range(n-1):
    a,b = l_in()
    E[a-1].append(b-1)
    E[b-1].append(a-1)


def call(e):
    if e in memo:
        return memo[e]
    a,b = e
    rev = 1
    size = 1
    for v in E[b]:
        if v == a:
            continue
        _rev, _size = call((b,v))
        size += _size
        rev = mod_mul(rev, _rev)

    rev = mod_mul(rev, size)
    memo[e] = (rev, size)
    return memo[e]


for k in range(n):
    rev = n
    for v in E[k]:
        _rev, _size = call((k,v))
        rev = mod_mul(rev, _rev)

    print(mod_div(fac[n], rev))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 210000

fac  = [0 for _ in range(MAX)]
finv = [0 for _ in range(MAX)]
inv  = [0 for _ in range(MAX)]

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        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 mod_COM(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;

COMinit()


n = n_in()

E = [[] for _ in range(n)]

memo = {}

for _ in range(n-1):
    a,b = l_in()
    E[a-1].append(b-1)
    E[b-1].append(a-1)


def call(e):
    if e in memo:
        return memo[e]
    a,b = e
    rev = 1
    size = 1
    for v in E[b]:
        if v == a:
            continue
        _rev, _size = call((b,v))
        size += _size
        rev = mod_mul(rev, _rev)

    rev = mod_mul(rev, size)
    memo[e] = (rev, size)
    return memo[e]



for k in range(n):
    rev = 1
    for v in E[k]:
        # print(v)
        _rev, _size = call((k,v))
        rev = mod_mul(rev, _rev)

    # print( call((0,1)))
    # print(rev)
    rev = mod_mul(rev, n)
    print(mod_div(fac[n], rev))
    # break

Submission status: Time Limit Exceeded

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N=int(input())
E=[[] for i in range(N+1)]

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

mod=10**9+7

FACT=[1]
for i in range(1,2*10**5+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(2*10**5,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

Q=[1]
SORTED=[1]
USE=[0]*(N+1)
USE[1]=1
P=[-1]*(N+1)

while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            SORTED.append(to)
            Q.append(to)
            P[to]=x

FROM1=[-1]*(N+1)
FROM2=[-1]*(N+1)

for x in SORTED[::-1]:
    if len(E[x])==1 and x!=1:
        FROM1[x]=1
        FROM2[x]=1
    else:
        L=[]
        SUML=0
        A=1
        for to in E[x]:
            if to==P[x]:
                continue
            L.append(FROM1[to])
            SUML+=FROM1[to]
            A=A*FROM2[to]%mod
        #print(x,L)
        FROM1[x]=SUML+1
        S=SUML

        for l in L:
            A=A*Combi(S,l)%mod
            S-=l
        FROM2[x]=A

TO1=[-1]*(N+1)
TO2=[-1]*(N+1)
TO2[1]=1

for x in SORTED:
    if x!=1 and len(E[x])==1:
        continue
    
    SS=1
    L=[]
    SUML=0
    for to in E[x]:
        if to==P[x]:
            continue
        
        SS=SS*FROM2[to]%mod
        L.append(FROM1[to])
        SUML+=FROM1[to]

    L.append(N-1-SUML)
    SUML+=N-1-SUML

    for to in E[x]:
        if to==P[x]:
            continue
        
        A=SS*pow(FROM2[to],mod-2,mod)*TO2[x]%mod
        S=SUML-FROM1[to]
        flag=0

        #print(x,L)
        for l in L:
            if flag==0 and l==FROM1[to]:
                flag=1
                continue
            A=A*Combi(S,l)%mod
            S-=l
        TO2[to]=A

for i in range(1,N+1):
    ANS=TO2[i]

    L=[]
    SUML=0

    for to in E[i]:
        if to==P[i]:
            continue
        ANS=ANS*FROM2[to]%mod
        L.append(FROM1[to])
        SUML+=FROM1[to]

    L.append(N-1-SUML)
    SUML+=N-1-SUML
    S=SUML
    for l in L:
        ANS=ANS*Combi(S,l)%mod
        S-=l
    print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

def print_l(l):
    print(' '.join(map(str, l)))

class Interval():
    def __init__(self, li):
        self.li = li
        self.n = len(li)
        self.sum_li = [li[0]]
        for i in range(1, self.n):
            self.sum_li.append(self.sum_li[i-1] + li[i])

    def sum(self, a, b=None):
        if b is None:
            return self.sum(0, a)

        res = self.sum_li[min(self.n-1, b-1)]
        if a > 0:
            res -= self.sum_li[a-1]
        return res


MOD = 1000000007

def mod_add(a, b):
  return (a+b)%MOD

def mod_sub(a, b):
  return (a+MOD-b)%MOD

def mod_mul(a, b):
  return a*b%MOD

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = (1,0,a)
    w = (0,1,b)
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    return (w[0],w[1])

def mod_inv(a):
    x,_  = extgcd(a, MOD)
    return (MOD+x%MOD)%MOD

def mod_div(a, b):
    return a*mod_inv(b)%MOD

def mod_pow(a, b):
    res = 1
    while b > 0:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res

MAX = 210000

fac  = [0 for _ in range(MAX)]
finv = [0 for _ in range(MAX)]
inv  = [0 for _ in range(MAX)]

def COMinit():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        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 mod_COM(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;

COMinit()


n = n_in()

E = [[] for _ in range(n)]

memo = {}

for _ in range(n-1):
    a,b = l_in()
    E[a-1].append(b-1)
    E[b-1].append(a-1)


def call(e):
    if e in memo.keys():
        return memo[e]
    a,b = e
    rev = 1
    size = 1
    for v in E[b]:
        if v == a:
            continue
        _rev, _size = call((b,v))
        size += _size
        rev = mod_mul(rev, _rev)

    rev = mod_mul(rev, size)
    memo[e] = (rev, size)
    return memo[e]



for k in range(n):
    rev = 1
    for v in E[k]:
        # print(v)
        _rev, _size = call((k,v))
        rev = mod_mul(rev, _rev)

    # print( call((0,1)))
    # print(rev)
    rev = mod_mul(rev, n)
    print(mod_div(fac[n], rev))
    # break