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


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



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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})
            ans %= MOD
    dp[ts] = ans
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
input=sys.stdin.readline

mod=10**9+7
MAX=2*10**5+100
g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod


N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]

data=[[] for i in range(N+1)]
for A,B in AB:
    data[A].append(B)
    data[B].append(A)

parent=[0]*(N+1)
flag=[0]*(N+1)
child=[0]*(N+1)
parent[1]=-1
flag[1]=1
que=[1]
ddd=deque([])
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                h.append(v)
                parent[v]=u
                child[u]+=1
        if child[u]==0:
            ddd.append(u)
    que=h

size=[0]*(N+1)
lst=[0]*(N+1)

while ddd:
    u=ddd.pop()
    size[u]=1
    
    qqq=1
    ppp=[]
    for v in data[u]:
        if v==parent[u]:
            child[v]-=1
            if child[v]==0:
                ddd.appendleft(v)
            continue
        else:
            size[u]+=size[v]
            if ppp:
                ppp.append(size[v]+ppp[-1])
            else:
                ppp.append(size[v])
            qqq=qqq*lst[v]%mod

    for i in range(len(ppp)-1,0,-1):
        qqq=qqq*cmb(ppp[i],ppp[i-1])%mod
    lst[u]=qqq

que=deque(data[1][:])
ans=[0]*(N+1)
lsls=[0]*(N+1)
ans[1]=lst[1]
lsls[1]=1
while que:
    u=que.pop()
    par=parent[u]
    
    qqq=1
    qqq*=lsls[par]
    
    ppp=[N-size[par]]
    for v in data[par]:
        if v==u:
            continue
        if v==parent[par]:
            continue
        else:
            qqq=qqq*lst[v]%mod
            ppp.append(size[v]+ppp[-1])
    for i in range(len(ppp)-1,0,-1):
        qqq=qqq*cmb(ppp[i],ppp[i-1])%mod
    lsls[u]=qqq
    
    ppp=[N-size[u]]
    for v in data[u]:
        if v==parent[u]:
            continue
        else:
            ppp.append(size[v]+ppp[-1])
            qqq=qqq*lst[v]%mod
            que.appendleft(v)
    for i in range(len(ppp)-1,0,-1):
        qqq=qqq*cmb(ppp[i],ppp[i-1])%mod
    ans[u]=qqq

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

Submission status: Time Limit Exceeded

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

setrecursionlimit(10000000)

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

Solution code:
from sys import setrecursionlimit
setrecursionlimit(2 * (10 ** 5))

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

MOD = 10 ** 9 + 7

class ModCmb:
    def __init__(self, size):
        self.inv = [1] * (size + 1)
        self.fact = [1] * (size + 1)
        temp_inv = [1] * (size + 1)
        for i in range(2, size + 1):
            temp_inv[i] = ( -(MOD // i) * temp_inv[MOD%i] ) % MOD
        for i in range(2, size + 1):
            self.fact[i] = self.fact[i-1] * i % MOD
            self.inv[i] = self.inv[i-1] * temp_inv[i] % MOD

    def cmb(self, n, r):
        if n <= 1 or n == r:
            return 1
        elif r == 1:
            return n
        else:
            return  (self.fact[n] * self.inv[r] % MOD ) * self.inv[n-r] % MOD

mc = ModCmb(n)

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

for a, b in ab:
    edge[a].append([b, 0, 0])
    edge[b].append([a, 0, 0])

def func(x, p):
    if len(edge[x]) == 1:
        return [1, 1]
    temp = []
    c = []
    for i, e in enumerate(edge[x]):
        if e[0] == p:
            continue
        if e[1] > 0:
            temp.append(e[1])
            c.append(e[2])
        else:
            t = func(e[0], x)
            edge[x][i][1] = t[0]
            edge[x][i][2] = t[1]
            c.append(t[1])
            temp.append(t[0])
    res = temp[0]
    rc = c[0]
    i = 1
    for z in temp[1:]:
        rc += c[i]
        res = (res * z * mc.cmb(rc, c[i])) % MOD
        i += 1
    return [res, rc + 1]

for x in range(n):
    temp = []
    c = []
    for i, e in enumerate(edge[x]):
        if e[1] > 0:
            temp.append(e[1])
            c.append(e[2])
        else:
            t = func(e[0], x)
            edge[x][i][1] = t[0]
            edge[x][i][2] = t[1]
            temp.append(t[0])
            c.append(t[1])
    #print('hoge ', len(temp), len(edge[x]))
    res = temp[0]
    rc = c[0]
    i = 1
    for z in temp[1:]:
        rc += c[i]
        res = (res * z * mc.cmb(rc, c[i])) % MOD
        i += 1
    #print(edge[x], temp, c)
    print(res)

Submission status: Time Limit Exceeded

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

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 = 2 * 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 = {}
def dfs(v, p):
    if (v, p) in d:
        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 * comb(num, i)
            count %= mod
    num += 1
    d[(v, p)] = num, count
    return num, count

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

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
mod=10**9+7
MAX=2*10**5+100

g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
    
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]

data=[[] for i in range(N+1)]
for A,B in AB:
    data[A].append(B)
    data[B].append(A)

parent=[0]*(N+1)
flag=[0]*(N+1)
child=[0]*(N+1)
parent[1]=-1
flag[1]=1
que=[1]
ddd=deque([])

while que:
    h=[]
    for u in que:
        cnt=0
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                h.append(v)
                parent[v]=u
                child[u]+=1
                cnt+=1
        if cnt==0:
            ddd.append(u)
    que=h

size=[0]*(N+1)
lst=[0]*(N+1)

while ddd:
    u=ddd.pop()
    size[u]=1
    
    qqq=1
    ppp=[]
    for v in data[u]:
        if v==parent[u]:
            child[v]-=1
            if child[v]==0:
                ddd.appendleft(v)
            continue
        else:
            size[u]+=size[v]
            if ppp:
                ppp.append(size[v]+ppp[-1])
            else:
                ppp.append(size[v])
            qqq=qqq*lst[v]%mod

    for i in range(len(ppp)-1,0,-1):
        qqq=qqq*cmb(ppp[i],ppp[i-1])%mod
    lst[u]=qqq

que=deque(data[1][:])
ans=[0]*(N+1)
lsls=[0]*(N+1)
ans[1]=lst[1]
lsls[1]=1
while que:
    u=que.pop()
    par=parent[u]
    
    qqq=1
    qqq*=lsls[par]
    
    ppp=[N-size[par]]
    for v in data[par]:
        if v==u:
            continue
        if v==parent[par]:
            continue
        else:
            qqq=qqq*lst[v]%mod
            ppp.append(size[v]+ppp[-1])
    for i in range(len(ppp)-1,0,-1):
        qqq=qqq*cmb(ppp[i],ppp[i-1])%mod
    lsls[u]=qqq
    
    ppp=[N-size[u]]
    for v in data[u]:
        if v==parent[u]:
            continue
        else:
            ppp.append(size[v]+ppp[-1])
            qqq=qqq*lst[v]%mod
            que.appendleft(v)
    for i in range(len(ppp)-1,0,-1):
        qqq=qqq*cmb(ppp[i],ppp[i-1])%mod
    ans[u]=qqq

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from functools import reduce
import sys
try:
    from typing import Dict, List, Tuple
except ImportError:
    pass

MOD = 1000000007  # type: int


def extgcd(a: int, b: int) -> "Tuple[int, int, int]":
    if b == 0:
        return (1, 0, a)
    q, r = a // b, a % b
    x, y, d = extgcd(b, r)
    s, t = y, x - q * y
    return s, t, d 


def modinv(a: int):
    return extgcd(a, MOD)[0]


facttable = []  # type: List[int]


def init_facttable(N: int):
    facttable[:] = [1] * (N + 1)
    for i in range(1, N + 1):
        facttable[i] = facttable[i - 1] * i % MOD


sys.setrecursionlimit(10000000)


dfs_memo = {}  # type: Dict[Tuple[int, int], Tuple[int, int]]


def dfs(G: "List[List[Tuple[int, int]]]", n: int, par: int = -1) -> "Tuple[int, int]":
    if (n, par) in dfs_memo:
        return dfs_memo[n, par]
    cds = [
        dfs(G, t, e)
        for e, t in G[n]
        if e != par
    ]
    nnodes = sum(nnode for nnode, comb in cds) + 1
    combs = facttable[nnodes - 1] * modinv(reduce(
        lambda a, b: a * facttable[b[0]] % MOD,
        cds,
        1
    )) % MOD * reduce(
        lambda a, b: a * b[1] % MOD,
        cds,
        1
    ) % MOD
    dfs_memo[n, par] = nnodes, combs
    return nnodes, combs


def solve(N: int, a: "List[int]", b: "List[int]"):
    init_facttable(N)
    G = [[] for _ in range(N)]  # type: List[List[Tuple[int, int]]]
    for i, (ai, bi) in enumerate(zip(a, b)):
        ai -= 1
        bi -= 1
        G[ai].append((i, bi))
        G[bi].append((i, ai))
    for k in range(N):
        print(dfs(G, k)[1])


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

Solution code:
from collections import defaultdict as dd
MOD = 10 ** 9 + 7

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

edge = dd(dict)
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a][b] = edge[b][a] = 1

memo_num = dd(int)
memo_ptn = dd(int)
for k in range(1, N+1):
    visited = [False] * (N+1)
    stk = [(None, k)]
    i = 0
    while stk:
        parent, node = stk[i]
        if (parent, node) in memo_num:
            continue

        if not visited[node]:
            visited[node] = True
            for child in edge[node].keys():
                if not visited[child] and (node, child) not in memo_num:
                    stk.append((node, child))
                    i += 1
        else:
            num = 1
            ptn = 1
            for child in edge[node].keys():
                if child != parent:
                    n = memo_num[(node, child)]
                    num += n
                    ptn *= pow(factorial[n], MOD-2, MOD)
                    ptn %= MOD
                    p = memo_ptn[(node, child)]
                    ptn *= p
                    ptn %= MOD
            ptn *= factorial[num-1]
            ptn %= MOD
            memo_num[(parent, node)] = num
            memo_ptn[(parent, node)] = ptn
            i -= 1
            stk.pop()
    print(memo_ptn[(None, k)])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5+10)
 
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 = 2 * 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 = {}
 
def dfs(v, p):
    if (v, p) in d:
        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):
    print(dfs(i, -1)[1])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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


mod = 10**9 + 7
N = 2*10**5  # 出力の制限
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


n = int(input())
node_dic = {}
for i in range(n-1):
    a, b = map(int, input().split())
    if a-1 in node_dic:
        node_dic[a-1].append(b-1)
    else:
        node_dic[a-1] = [b-1]
    if b-1 in node_dic:
        node_dic[b-1].append(a-1)
    else:
        node_dic[b-1] = [a-1]

# print(node_dic)

memo_dic = {}


def count(old, now):
    if old in memo_dic and now in memo_dic[old]:
        return memo_dic[old][now]
    # print(old, now)
    edge_list = []
    ans_list = []
    edge_sum = 0
    ans_sum = 1
    for edge in node_dic[now]:
        if edge == old:
            continue
        else:
            edge, ans = count(now, edge)
        edge_list.append(edge)
        edge_sum += edge
        ans_list.append(ans)
    if len(edge_list):
        edge_rest = edge_sum
        for e, a in zip(edge_list, ans_list):
            ans_sum = ans_sum * a * cmb(edge_rest, e, mod) % mod
            edge_rest -= e
    # print(old, now, edge_sum+1, ans_sum)
    if old in memo_dic:
        memo_dic[old][now] = (edge_sum + 1, ans_sum)
    else:
        memo_dic[old] = {now: (edge_sum + 1, ans_sum)}
    return edge_sum + 1, ans_sum


for i in range(n):
    edge, ans = count(-1, i)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
MOD = 10 ** 9 + 7

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

edge = dd(dict)
for _ in range(N-1):
    a, b = map(int, input().split())
    edge[a][b] = edge[b][a] = 1

memo_num = dd(int)
memo_ptn = dd(int)
for k in range(1, N+1):
    visited = [False] * (N+1)
    stk = [(None, k)]
    i = 0
    while stk:
        parent, node = stk[i]
        if not visited[node]:
            visited[node] = True
            for child in edge[node].keys():
                if not visited[child] and (node, child) not in memo_num:
                    stk.append((node, child))
                    i += 1
        else:
            num = 1
            ptn = 1
            for child in edge[node].keys():
                if child != parent:
                    n = memo_num[(node, child)]
                    num += n
                    ptn *= pow(factorial[n], MOD-2, MOD)
                    ptn %= MOD
                    p = memo_ptn[(node, child)]
                    ptn *= p
                    ptn %= MOD
            ptn *= factorial[num-1]
            ptn %= MOD
            memo_num[(parent, node)] = num
            memo_ptn[(parent, node)] = ptn
            i -= 1
            stk.pop()
    print(memo_ptn[(None, k)])

Submission status: Time Limit Exceeded

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

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 = 2 * 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 = {}

def dfs(v, p):
    if (v, p) in d:
        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):
    print(dfs(i, -1)[1])

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    """
    return pow(a, mod - 2, mod)


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

factorials = get_factorials(max=N * 2, mod=MOD)
finvs = factorial_invs(max=N * 2, mod=MOD)

memo = [None for _ in range(N)]


@lru_cache(maxsize=1 << (2 * 10 ** 6).bit_length())
def solve(v, p):
    if memo[v] is not None:
        ret, children_cnt, without = memo[v]
        if without is not None:
            r, cnt = solve(without, v)
            ret *= finvs[children_cnt]
            ret %= MOD
            ret *= factorials[children_cnt + cnt]
            ret %= MOD
            ret *= finvs[cnt]
            ret %= MOD
            ret *= r
            ret %= MOD
            children_cnt += cnt
            without = None
            memo[v] = ret, children_cnt, without
        if p is None:
            return ret, children_cnt + 1
        r, cnt = solve(p, v)
        ret *= finvs[children_cnt]
        ret %= MOD
        ret *= factorials[children_cnt - cnt]
        ret %= MOD
        ret *= factorials[cnt]
        ret %= MOD
        ret *= mod_inv(r, MOD)
        ret %= MOD
        return ret, children_cnt - cnt + 1

    ret = 1
    children = []
    for u in graph[v]:
        if u == p:
            continue
        r, cnt = solve(u, v)
        children.append(cnt)
        ret *= r
        ret %= MOD
    children_cnt = sum(children)
    ret *= factorials[children_cnt]
    ret %= MOD
    for cnt in children:
        ret *= finvs[cnt]
        ret %= MOD

    memo[v] = ret, children_cnt, p
    return ret, children_cnt + 1


ans = []
for v in range(N):
    a, _ = solve(v, None)
    ans.append(a)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)


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


mod = 10**9 + 7
N = 2*10**5  # 出力の制限
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)


n = int(input())
node_dic = {}
for i in range(n-1):
    a, b = map(int, input().split())
    if a-1 in node_dic:
        node_dic[a-1].append(b-1)
    else:
        node_dic[a-1] = [b-1]
    if b-1 in node_dic:
        node_dic[b-1].append(a-1)
    else:
        node_dic[b-1] = [a-1]

# print(node_dic)


def count(old, now):
    # print(old, now)
    edge_list = []
    ans_list = []
    edge_sum = 0
    ans_sum = 1
    for edge in node_dic[now]:
        if edge == old:
            continue
        else:
            edge, ans = count(now, edge)
        edge_list.append(edge)
        edge_sum += edge
        ans_list.append(ans)
    if len(edge_list):
        edge_rest = edge_sum
        for e, a in zip(edge_list, ans_list):
            ans_sum = ans_sum * a * cmb(edge_rest, e, mod) % mod
            edge_rest -= e
    # print(old, now, edge_sum+1, ans_sum)
    return edge_sum + 1, ans_sum


for i in range(n):
    edge, ans = count(-1, i)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5*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 = 2 * 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):
    print(dfs(i, -1)[1])

Submission status: Time Limit Exceeded

Solution code:
import sys

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])
sys.setrecursionlimit(10 ** 6)
main()