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:
from copy import deepcopy as copy
import sys
sys.setrecursionlimit(300000)
n = int(input())
MOD = 10**9+7
class mint:
    def __init__(self, x):
        self.x = x % MOD if isinstance(x, int) else int(x) % MOD
    def __str__(self):
        return str(self.x)
    __repr__ = __str__
    def __iadd__(self, other):
        self.x += other.x if isinstance(other, mint) else other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __isub__(self, other):
        self.x += MOD-other.x if isinstance(other, mint) else MOD-other
        self.x -= MOD if self.x >= MOD else 0
        return self
    def __imul__(self, other):
        self.x *= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __imod__(self, other):
        self.x %= other.x if isinstance(other, mint) else other
        self.x %= MOD
        return self
    def __add__(self, other):
        return (
            mint(self.x + other.x) if isinstance(other, mint) else
            mint(self.x + other)
        )
    def __sub__(self, other):
        return (
            mint(self.x - other.x) if isinstance(other, mint) else
            mint(self.x - other)
        )
    def __mul__(self, other):
        return (
            mint(self.x * other.x) if isinstance(other, mint) else
            mint(self.x * other)
        )
    def __mod__(self, other):
        return (
            mint(self.x % other.x) if isinstance(other, mint) else
            mint(self.x % other)
        )
    def __truediv__(self, other):
        return (
            mint(
                self.x * pow(other.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(self.x * pow(other, MOD - 2, MOD))
        )
    def __pow__(self, other):
        return (
            mint(pow(self.x, other.x, MOD)) if isinstance(other, mint) else
            mint(pow(self.x, other, MOD))
        )
    __radd__ = __add__
    def __rsub__(self, other):
        return (
            mint(other.x - self.x) if isinstance(other, mint) else
            mint(other - self.x)
        )
    __rmul__ = __mul__
    def __rmod__(self, other):
        return (
            mint(other.x % self.x) if isinstance(other, mint) else
            mint(other % self.x)
        )
    def __rtruediv__(self, other):
        return (
            mint(
                other.x * pow(self.x, MOD - 2, MOD)
            ) if isinstance(other, mint) else
            mint(other * pow(self.x, MOD - 2, MOD))
        )
    def __rpow__(self, other):
        return (
            mint(pow(other.x, self.x, MOD)) if isinstance(other, mint) else
            mint(pow(other, self.x, MOD))
        )

class comb():
    # class <mint> should be imported
    def __init__(self, n):
        self.n = n
        fact = [0]*(n+1) # 1-indexed
        ifact = [0]*(n+1) # 逆元
        fact[0] = mint(1)
        for i in range(1, n+1):
            fact[i] = fact[i-1]*i
        ifact[-1] = pow(fact[-1], MOD-2)
        for i in range(n, 0, -1):
            ifact[i-1] = ifact[i]*i
        self.fact = fact
        self.ifact = ifact
    def calc(self, n, k):
        if n == 0:
            return 1
        if k<0 or k>n:
            return 0
        return self.fact[n]*self.ifact[k]*self.ifact[n-k]
cb = comb(200005)

class datum:
    def __init__(self, size=0, case=mint(1)):
        self.size = size
        self.case = case

def merge(d, p):
    now = copy(d)
    plus = copy(p)
    now.size += plus.size
    now.case *= plus.case
    now.case *= cb.ifact[plus.size]
    return now

def merge2(a,b):
    a2 = copy(a)
    b2 = copy(b)
    ressize = a2.size + b2.size
    rescase = a2.case* b2.case
    return datum(ressize, rescase)
def add_root(d):
    now = copy(d)
    now.case *= cb.fact[now.size]
    now.size += 1
    return now

def dfs(u,p=-1):
    now = datum()
    for v in to[u]:
        if v == p:
            continue
        dp[u][v] = dfs(v,u)
        now = merge(now,dp[u][v])
    now = add_root(now)
    return now

ans = [mint(0) for _ in range(n)]
def bfs(u,p=-1,pdp=datum()):
    for v in to[u]:
        if v == p:
            dp[u][v] = pdp
    deg = len(to[u])
    l = [datum() for _ in range(deg+1)]
    r = [datum() for _ in range(deg+1)]
    for i in range(deg):
        l[i+1] = merge(l[i], dp[u][to[u][i]])
    for i in reversed(range(1,deg+1)):
        r[i-1] = merge(r[i], dp[u][to[u][i-1]])

    ans[u] = add_root(l[-1]).case

    for i in range(deg):
        v = to[u][i]
        if v == p:
            continue
        lm = copy(l[i])
        rm = copy(r[i+1])
        bfs(v,u,add_root(merge2(lm,rm)))







to = [list() for _ in range(n)]
dp = [dict() for _ in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    a -=  1
    b -= 1
    to[a].append(b)
    to[b].append(a)

dfs(0)
bfs(0)

print(*ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

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)

factorial = [1,1]
inv_factorial = [1,1]
inv = [1,1]
for i in range(2,N + 1):
    factorial.append(factorial[-1]*i)
    inv.append(MOD - inv[MOD%i]*(MOD//i)%MOD)
    inv_factorial.append(inv_factorial[-1]*inv[-1]%MOD)

deg = [0] * N
parent = [0] * N
dp = [0] * N
ans = [0] * N
cnt_leaf = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]*inv[N - cnt_leaf[e] - 1]%MOD,v)
    
dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

import numpy as np
def prepare_np(n):
    nrt = int(n ** 0.5) + 1
    nsq = nrt * nrt
    facts = np.arange(nsq, dtype=np.int64).reshape(nrt, nrt)
    facts[0, 0] = 1
    for i in range(1, nrt):
        facts[:, i] = facts[:, i] * facts[:, i - 1] % MOD
    for i in range(1, nrt):
        facts[i] = facts[i] * facts[i - 1, -1] % MOD
    facts = facts.ravel().tolist()
 
    invs = np.arange(1, nsq + 1, dtype=np.int64).reshape(nrt, nrt)
    invs[-1, -1] = pow(facts[-1], MOD - 2, MOD)
    for i in range(nrt - 2, -1, -1):
        invs[:, i] = invs[:, i] * invs[:, i + 1] % MOD
    for i in range(nrt - 2, -1, -1):
        invs[i] = invs[i] * invs[i + 1, 0] % MOD
    invs = invs.ravel().tolist()
 
    return facts, invs

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)

factorial,inv_factorial = prepare_np(N + 1)

deg = [0] * N
parent = [0] * N
dp = [0] * N
ans = [0] * N
cnt_leaf = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]*pow(N - cnt_leaf[e] - 1,MOD - 2,MOD)%MOD,v)
    
dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100000000)

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)

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

inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

deg = [0] * N
parent = [0] * N
dp = [0] * N
ans = [0] * N
cnt_leaf = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]*pow(N - cnt_leaf[e] - 1,MOD - 2,MOD)%MOD,v)
    
dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

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)

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

inv_factorial = [-1] * (N + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(N)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

deg = [0] * N
parent = [0] * N
dp = [0] * N
ans = [0] * N
cnt_leaf = [0] * N

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(e,dpl[i]*dpr[i + 1]*pow(N - cnt_leaf[e] - 1,MOD - 2,MOD)%MOD,v)
    
dfs(0)
bfs(0)
print('\n'.join(map(str,ans)))

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

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

inv_factorial = [-1] * (MAXN + 1)
inv_factorial[-1] = pow(factorial[-1], MOD-2, MOD)
for i in reversed(range(MAXN)):
    inv_factorial[i] = inv_factorial[i + 1] * (i + 1) % MOD

G = [[] for _ in range(MAXN)]
deg = [None] * MAXN
parent = [None] * MAXN
dp = [None] * MAXN
ans = [None] * MAXN
cnt_leaf = [0] * MAXN

def dfs(v,p = -1):
    deg[v] = len(G[v])
    dp[v] = [0] * deg[v]
    res = 1
    cnt = 0
    for i,e in enumerate(G[v]):
        if e == p:
            parent[v] = i
            continue
        a,b = dfs(e,v)
        dp[v][i] = a*inv_factorial[b]%MOD
        cnt += b
        res *= dp[v][i]
        res %= MOD
    res *= factorial[cnt]%MOD
    cnt_leaf[v] = cnt
    return res,cnt + 1

def bfs(N,v,res_p = 0,p = - 1):
    if p != -1:
        dp[v][parent[v]] = res_p
    dpl = [1] * (deg[v] + 1)
    for i,x in enumerate(dp[v]):
        dpl[i + 1] = dpl[i]*x%MOD
    dpr = [1] * (deg[v] + 1)
    for i in range(deg[v] - 1,-1,-1):
        dpr[i] = dpr[i + 1]*dp[v][i]%MOD
    
    ans[v] = dpr[0]*factorial[N - 1]%MOD
    for i,e in enumerate(G[v]):
        if e == p:
            continue
        bfs(N,e,dpl[i]*dpr[i + 1]*pow(N - cnt_leaf[e] - 1,MOD - 2,MOD)%MOD,v)

def main():
    N = int(input())
    for _ in range(N - 1):
        a,b = map(int,input().split())
        a -= 1
        b -= 1
        G[a].append(b)
        G[b].append(a)
    
    dfs(0)
    bfs(N,0)
    print('\n'.join(map(str,ans[:N])))
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def hoge():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))

    from collections import defaultdict
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)


    M = 10**9+7 # 出力の制限
    N = n # 必要なテーブルサイズ

    g1 = [None] * (N+1) # 元テーブル
    g2 = [None] * (N+1) #逆元テーブル
    inverse = [None] * (N+1) #逆元テーブル計算用テーブル
    g1[0] = g1[1] = g2[0] = g2[1] = 1
    inverse[0], inverse[1] = [0, 1] 

    for i in range( 2, N + 1 ):
        g1[i] = ( g1[i-1] * i ) % M 
        inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
        g2[i] = (g2[i-1] * inverse[i]) % M 


    ans = {}
    prevs = {}
    out = [None] * n
    def sub(i, j, prev):
        prevs[i,j] = prev
        if (i,j) in ans:
            return ans[i,j]
        if len(ns[j])==1 and i in ns[j]:
            ans[i,j] = (1, 1)
            return (1, 1)

        count = 1
        sum_size = 0
        for k in ns[j]:
            if k==i:
                continue
            val, size = sub(j, k, i)
            count = (count * val) % M
            count = (count * g2[size]) % M
            sum_size += size
        count = (count * g1[sum_size]) % M
        ans[i,j] = (count, sum_size+1)
        return (count, sum_size+1)

    def sub2(i, j, q):
        for k in ns[j]:
            if k==i:
                continue
            if (k, j) in ans:
                continue
            tmp_count, tmp_size = ans[j, k]
            total_count, total_size = ans[prevs[j, k], j]
            prev_count, prev_size = ans[j, i]
            new_size = total_size - tmp_size + prev_size
            new_count = (total_count * g2[total_size-1] * g1[new_size-1]) % M
            new_count = (new_count * prev_count * pow(tmp_count, M-2, M)) % M
            new_count = (new_count * g2[prev_size] * g1[tmp_size]) % M
            ans[k, j] = (new_count, new_size)
            val = tmp_count
            val = (val * new_count * g1[new_size+tmp_size-1] * g2[tmp_size-1] * g2[new_size]) % M
            out[k] = val
            q.appendleft((j, k))
#             sub2(j, k)
    #         print("total: ", total_count, total_size)
    #         print("tmp: ", tmp_count, tmp_size)
    #         print("prev: ", prev_count, prev_size)
    #         new_count = total_count / g1[total_size-1] * g1[new_size-1] * prev_count / tmp_count / g1[prev_size] * g1[tmp_size]
    #         print(new_count)
    #         print("")

    # 0を始点として木DP
    sub(-1, 0, None)

    ans[0, -1] = (1,0)

    # 逆向きを求める
    from queue import deque
    q = deque()
    q.appendleft((-1, 0))
    while q:
        u, v = q.pop()
        sub2(u, v, q)
    
    u = 0
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] # sub(u, k, None)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    out[0] = count
    return out
out = hoge()
print("\n".join(map(str, out)))

Submission status: Time Limit Exceeded

Solution code:
def hoge():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))


    from collections import defaultdict
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        ns[u-1].add(v-1)
        ns[v-1].add(u-1)


    M = 10**9+7 # 出力の制限
    N = n # 必要なテーブルサイズ

    g1 = [None] * (N+1) # 元テーブル
    g2 = [None] * (N+1) #逆元テーブル
    inverse = [None] * (N+1) #逆元テーブル計算用テーブル
    g1[0] = g1[1] = g2[0] = g2[1] = 1
    inverse[0], inverse[1] = [0, 1] 

    for i in range( 2, N + 1 ):
        g1[i] = ( g1[i-1] * i ) % M 
        inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
        g2[i] = (g2[i-1] * inverse[i]) % M 


    ans = {}
    prevs = {}
    out = [None] * n
    def sub(i, j, prev):
        prevs[i,j] = prev
        if (i,j) in ans:
            return ans[i,j]
        if len(ns[j])==1 and i in ns[j]:
            ans[i,j] = (1, 1)
            return (1, 1)

        count = 1
        sum_size = 0
        for k in ns[j]:
            if k==i:
                continue
            val, size = sub(j, k, i)
            count = (count * val) % M
            count = (count * g2[size]) % M
            sum_size += size
        count = (count * g1[sum_size]) % M
        ans[i,j] = (count, sum_size+1)
        return (count, sum_size+1)

    def sub2(i, j):
        for k in ns[j]:
            if k==i:
                continue
            if (k, j) in ans:
                continue
            tmp_count, tmp_size = ans[j, k]
            total_count, total_size = ans[prevs[j, k], j]
            prev_count, prev_size = ans[j, i]
            new_size = total_size - tmp_size + prev_size
            new_count = (total_count * g2[total_size-1] * g1[new_size-1]) % M
            new_count = (new_count * prev_count * pow(tmp_count, M-2, M)) % M
            new_count = (new_count * g2[prev_size] * g1[tmp_size]) % M
            ans[k, j] = (new_count, new_size)
            val = tmp_count
            val = (val * new_count * g1[new_size+tmp_size-1] * g2[tmp_size-1] * g2[new_size]) % M
            out[k] = val
            sub2(j, k)
    #         print("total: ", total_count, total_size)
    #         print("tmp: ", tmp_count, tmp_size)
    #         print("prev: ", prev_count, prev_size)
    #         new_count = total_count / g1[total_size-1] * g1[new_size-1] * prev_count / tmp_count / g1[prev_size] * g1[tmp_size]
    #         print(new_count)
    #         print("")

    # 0を始点として木DP
    sub(-1, 0, None)

    ans[0, -1] = (1,0)

    # 逆向きを求める
    sub2(-1, 0)
    
    u = 0
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] # sub(u, k, None)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    out[0] = count
    print("\n".join(map(str, out)))
hoge()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

    
M = 10**9+7 # 出力の制限
N = n # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 


ans = {}
prevs = {}
def sub(i, j, prev):
    prevs[i,j] = prev
    if (i,j) in ans:
        return ans[i,j]
    if len(ns[j])==1 and i in ns[j]:
        ans[i,j] = (1, 1)
        return (1, 1)
    
    count = 1
    sum_size = 0
    for k in ns[j]:
        if k==i:
            continue
        val, size = sub(j, k, i)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    ans[i,j] = (count, sum_size+1)
    return (count, sum_size+1)

def sub2(i, j):
    
    for k in ns[j]:
        if k==i:
            continue
        if (k, j) in ans:
            continue
        tmp_count, tmp_size = ans[j, k]
        total_count, total_size = ans[prevs[j, k], j]
        prev_count, prev_size = ans[j, i]
        new_size = total_size - tmp_size + prev_size
        new_count = (total_count * g2[total_size-1] * g1[new_size-1]) % M
        new_count = (new_count * prev_count * pow(tmp_count, M-2, M)) % M
        new_count = (new_count * g2[prev_size] * g1[tmp_size]) % M
        ans[k, j] = (new_count, new_size)
        sub2(j, k)
#         print("total: ", total_count, total_size)
#         print("tmp: ", tmp_count, tmp_size)
#         print("prev: ", prev_count, prev_size)
#         new_count = total_count / g1[total_size-1] * g1[new_size-1] * prev_count / tmp_count / g1[prev_size] * g1[tmp_size]
#         print(new_count)
#         print("")

# 0を始点として木DP
sub(-1, 0, None)

ans[0, -1] = (1,0)

# 逆向きを求める
sub2(-1, 0)

for u in range(n):
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] # sub(u, k, None)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))

from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

    
M = 10**9+7 # 出力の制限
N = n # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 


ans = {}
prevs = {}
def sub(i, j, prev):
    prevs[i,j] = prev
    if (i,j) in ans:
        return ans[i,j]
    if len(ns[j])==1 and i in ns[j]:
        ans[i,j] = (1, 1)
        return (1, 1)
    
    count = 1
    sum_size = 0
    for k in ns[j]:
        if k==i:
            continue
        val, size = sub(j, k, i)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    ans[i,j] = (count, sum_size+1)
    return (count, sum_size+1)

def sub2(i, j):
    for k in ns[j]:
        if k==i:
            continue
        if (k, j) in ans:
            continue
        tmp_count, tmp_size = ans[j, k]
        total_count, total_size = ans[prevs[j, k], j]
        prev_count, prev_size = ans[j, i]
        new_size = total_size - tmp_size + prev_size
        new_count = (total_count * g2[total_size-1] * g1[new_size-1] * prev_count * pow(tmp_count, M-2, M) * g2[prev_size] * g1[tmp_size]) %M
        ans[k, j] = (new_count, new_size)
        sub2(j, k)
#         print("total: ", total_count, total_size)
#         print("tmp: ", tmp_count, tmp_size)
#         print("prev: ", prev_count, prev_size)
#         new_count = total_count / g1[total_size-1] * g1[new_size-1] * prev_count / tmp_count / g1[prev_size] * g1[tmp_size]
#         print(new_count)
#         print("")

# 0を始点として木DP
sub(-1, 0, None)

ans[0, -1] = (1,0)

# 逆向きを求める
sub2(-1, 0)

for u in range(n):
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] # sub(u, k, None)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))

from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

    
M = 10**9+7 # 出力の制限
N = n # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 


ans = {}
prevs = {}
def sub(i, j, prev):
    prevs[i,j] = prev
    if (i,j) in ans:
        return ans[i,j]
    if len(ns[j])==1 and i in ns[j]:
        ans[i,j] = (1, 1)
        return (1, 1)
    
    count = 1
    sum_size = 0
    for k in ns[j]:
        if k==i:
            continue
        val, size = sub(j, k, i)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    ans[i,j] = (count, sum_size+1)
    return (count, sum_size+1)

def sub2(i, j):
    for k in ns[j]:
        if k==i:
            continue
        tmp_count, tmp_size = ans[j, k]
        total_count, total_size = ans[prevs[j, k], j]
        prev_count, prev_size = ans[j, i]
        new_size = total_size - tmp_size + prev_size
#         print("total: ", total_count, total_size)
#         print("tmp: ", tmp_count, tmp_size)
#         print("prev: ", prev_count, prev_size)
        new_count = (total_count * g2[total_size-1] * g1[new_size-1] * prev_count * pow(tmp_count, M-2, M) * g2[prev_size] * g1[tmp_size]) %M
#         new_count = total_count / g1[total_size-1] * g1[new_size-1] * prev_count / tmp_count / g1[prev_size] * g1[tmp_size]
#         print(new_count)
#         print("")
        ans[k, j] = (new_count, new_size)
        sub2(j, k)

# 0を始点として木DP
sub(-1, 0, None)

ans[0, -1] = (1,0)

# 逆向きを求める
sub2(-1, 0)

for u in range(n):
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = ans[u, k] # sub(u, k, None)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

    
M = 10**9+7 # 出力の制限
N = n # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 


from functools import lru_cache

# ans = {}
@lru_cache(2**20)
def sub(i, j):
#     if (i,j) in ans:
#         return ans[i,j]
    if len(ns[j])==1 and i in ns[j]:
#         ans[i,j] = (1, 1)
        return (1, 1)
    
    count = 1
    sum_size = 0
    for k in ns[j]:
        if k==i:
            continue
        val, size = sub(j, k)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
#     ans[i,j] = (count, sum_size+1)
    return (count, sum_size+1)

for u in range(n):
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = sub(u, k)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

    
M = 10**9+7 # 出力の制限
N = n # 必要なテーブルサイズ

g1 = [None] * (N+1) # 元テーブル
g2 = [None] * (N+1) #逆元テーブル
inverse = [None] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 

for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 

    

ans = {}
def sub(i, j):
    if (i,j) in ans:
        return ans[i,j]
    if len(ns[j])==1 and i in ns[j]:
        ans[i,j] = (1, 1)
        return (1, 1)
    
    count = 1
    sum_size = 0
    for k in ns[j]:
        if k==i:
            continue
        val, size = sub(j, k)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    ans[i,j] = (count, sum_size+1)
    return (count, sum_size+1)

for u in range(n):
    count = 1
    sum_size = 0
    for k in ns[u]:
        val, size = sub(u, k)
        count = (count * val) % M
        count = (count * g2[size]) % M
        sum_size += size
    count = (count * g1[sum_size]) % M
    print(count)