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 sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

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

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

# C,Pを求める前処理
m = 2*10**5
mod = 10**9 + 7

fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2,m+5):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

d = [[[0,0] for j in range(N+1)] for i in range(N+1)]
finish = [[0 for j in range(N+1)] for i in range(N+1)]

@functools.lru_cache(None)
def bfs(u,v):
    if finish[u][v] == 1:
        return d[u][v]
    else:
        ps = []
        ns = []
        for w in al[v]:
            if w != u:
                n, p = bfs(v,w)
                ns.append(n)
                ps.append(p)
        if len(ns) == 0:
            return 1, 1

        nv = sum(ns) + 1
        ff = fact[nv-1]
        for k in ns:
            ff = ff * fact_inv[k] % mod
        pp = 1
        for k in ps:
            pp = pp * k % mod
        pv = (ff % mod) * pp % mod
        d[u][v] = [nv, pv]
        finish[u][v] = 1
        return nv, pv

for i in range(1,N+1):
    n, p = bfs(0,i)
    print(p % mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

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

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

# C,Pを求める前処理
m = 2*10**5
mod = 10**9 + 7

fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2,m+5):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod

d = [[[0,0] for j in range(N+1)] for i in range(N+1)]
finish = [[0 for j in range(N+1)] for i in range(N+1)]

def bfs(u,v):
    if finish[u][v] == 1:
        return d[u][v]
    else:
        ps = []
        ns = []
        for w in al[v]:
            if w != u:
                n, p = bfs(v,w)
                ns.append(n)
                ps.append(p)
        if len(ns) == 0:
            return 1, 1

        nv = sum(ns) + 1
        ff = fact[nv-1]
        for k in ns:
            ff = ff * fact_inv[k] % mod
        pp = 1
        for k in ps:
            pp = pp * k % mod
        pv = (ff % mod) * pp % mod
        d[u][v] = [nv, pv]
        finish[u][v] = 1
        return nv, pv

for i in range(1,N+1):
    n, p = bfs(0,i)
    print(p % mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

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

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

# C,Pを求める前処理
m = 2*10**5 + 5
mod = 10**9 + 7

fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2,m+5):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def multinomial(lst):
    res, i = 1, 1
    for a in lst:
        for j in range(1, a + 1):
            res *= i
            res //= j
            i += 1
    return res

@functools.lru_cache(None)
def bfs(u,v):
    ps = []
    ns = []
    for w in al[v]:
        if w != u:
            n, p = bfs(v,w)
            ns.append(n)
            ps.append(p)
    if len(ns) == 0:
        return 1, 1

    nv = sum(ns) + 1
    ff = fact[nv-1]
    for k in ns:
        ff = ff * fact_inv[k] % mod
    pp = 1
    for k in ps:
        pp = pp * k % mod
    pv = (ff % mod) * pp % mod
    return nv, pv

for i in range(1,N+1):
    n, p = bfs(0,i)
    print(p % mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

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

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

# C,Pを求める前処理
m = 2*10**5 + 5
mod = 10**9 + 7

fact = [0]*(m+5)
fact_inv = [0]*(m+5)
inv = [0]*(m+5)

fact[0] = fact[1] = 1
fact_inv[0] = fact_inv[1] = 1
inv[1] = 1

for i in range(2,m+5):
    fact[i] = fact[i-1] * i % mod
    inv[i] = mod - inv[mod % i] * (mod // i) % mod
    fact_inv[i] = fact_inv[i-1] * inv[i] % mod


def multinomial(lst):
    res, i = 1, 1
    for a in lst:
        for j in range(1, a + 1):
            res *= i
            res //= j
            i += 1
    return res

@functools.lru_cache(None)
def bfs(u,v):
    ps = []
    ns = []
    for w in al[v]:
        if w != u:
            n, p = bfs(v,w)
            ns.append(n)
            ps.append(p)
    if len(ns) == 0:
        return 1, 1

    nv = sum(ns) + 1
    ff = fact[nv-1]
    for k in ns:
        ff = ff * fact_inv[k] % mod
    pv = (ff % mod) * reduce(mul, ps) % mod
    return nv, pv

for i in range(1,N+1):
    n, p = bfs(0,i)
    print(p % mod)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter,defaultdict
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq
sys.setrecursionlimit(10**6)
INF =  float("inf")
import bisect
import statistics
mod = 10**9+7

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

for i in range(N-1):
    a, b = list(map(int, input().split()))

    al[a].append(b)
    al[b].append(a)

def multinomial(lst):
    res, i = 1, 1
    for a in lst:
        for j in range(1, a + 1):
            res *= i
            res //= j
            i += 1
    return res

@functools.lru_cache(None)
def bfs(u,v):
    ps = []
    ns = []
    for w in al[v]:
        if w != u:
            n, p = bfs(v,w)
            ns.append(n)
            ps.append(p)
    if len(ns) == 0:
        return 1, 1

    nv = sum(ns) + 1
    pv = ((multinomial(ns) % mod) * (reduce(mul, ps) % mod)) % mod
    return nv, pv

for i in range(1,N+1):
    n, p = bfs(0,i)
    print(p % mod)

Submission status: Time Limit Exceeded

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


def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    MOD = 10**9 + 7
    N = int(input())
    adj = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        adj[a].append(b)
        adj[b].append(a)

    # 有向枝(p, n)の先にあるnodeの数
    node_nums = defaultdict(int)

    def node_num_search(p, n):
        ret = 1
        for c in adj[n]:
            if c == p:
                continue
            ret += node_num_search(n, c)
        if p is not None:
            node_nums[(p, n)] = ret
            node_nums[(n, p)] = N - ret
        return ret

    node_num_search(None, 0)

    # mod factorialとその逆元の値を事前計算しておく
    mod_facts = [1] * (N + 1)
    mod_facts_invs = [1] * (N + 1)
    for n in range(1, N + 1):
        mod_facts[n] = n * mod_facts[n - 1] % MOD
        mod_facts_invs[n] = mod_inv(mod_facts[n], MOD)

    # 有向枝(p, n)以降のノードについての番号の決め方
    pat_nums = defaultdict(int)

    def pat_num_search(p, n):
        v = pat_nums[(p, n)]
        if v > 0:
            return v
        coef, rest_node_num = 1, 0
        ret = 1
        for c in adj[n]:
            if c == p:
                continue
            ret *= pat_num_search(n, c)
            ret %= MOD
            nn = node_nums[(n, c)]
            rest_node_num += nn
            coef *= mod_facts_invs[nn]
            coef %= MOD
        coef *= mod_facts[rest_node_num]
        coef %= MOD
        ret *= coef
        ret %= MOD
        pat_nums[(p, n)] = ret
        return ret

    # 答えを計算
    ans = [1] * N
    for n in range(N):
        a = mod_facts[N - 1]
        for c in adj[n]:
            a *= pat_num_search(n, c)
            a %= MOD
            a *= mod_facts_invs[node_nums[(n, c)]]
            a %= MOD
        ans[n] = a
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10**6)


def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    MOD = 10**9 + 7
    N = int(input())
    adj = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        adj[a].append(b)
        adj[b].append(a)

    # 有向枝(p, n)の先にあるnodeの数
    node_nums = defaultdict(int)

    def node_num_search(p, n):
        ret = 1
        for c in adj[n]:
            if c == p:
                continue
            ret += node_num_search(n, c)
        if p is not None:
            node_nums[(p, n)] = ret
            node_nums[(n, p)] = N - ret
        return ret

    node_num_search(None, 0)

    # mod factorialとその逆元の値を事前計算しておく
    mod_facts = [1] * (N + 1)
    mod_facts_invs = [1] * (N + 1)
    for n in range(1, N + 1):
        mod_facts[n] = n * mod_facts[n - 1] % MOD
        mod_facts_invs[n] = mod_inv(mod_facts[n], MOD)

    # 有向枝(p, n)以降のノードについての番号の決め方
    pat_nums = defaultdict(int)

    def pat_num_search(p, n):
        v = pat_nums[(p, n)]
        if v > 0:
            return v
        coef, rest_node_num = 1, 0
        ret = 1
        for c in adj[n]:
            if c == p:
                continue
            ret *= pat_num_search(n, c)
            ret %= MOD
            nn = node_nums[(n, c)]
            rest_node_num += nn
            coef *= mod_facts_invs[nn]
            coef %= MOD
        coef *= mod_facts[rest_node_num]
        ret = ret * coef % MOD
        pat_nums[(p, n)] = ret
        return ret

    # 答えを計算
    ans = [1] * N
    for n in range(N):
        a = mod_facts[N - 1]
        for c in adj[n]:
            a *= pat_num_search(n, c)
            a *= mod_facts_invs[node_nums[(n, c)]]
            a %= MOD
        ans[n] = a
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10**6)


def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    MOD = 10**9 + 7
    N = int(input())
    adj = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        adj[a].append(b)
        adj[b].append(a)

    # 有向枝(p, n)の先にあるnodeの数
    node_nums = defaultdict(int)

    def node_num_search(p, n):
        ret = 1
        for c in adj[n]:
            if c == p:
                continue
            ret += node_num_search(n, c)
        if p is not None:
            node_nums[(p, n)] = ret
            node_nums[(n, p)] = N - ret
        return ret

    node_num_search(None, 0)

    # mod factorialとその逆元の値を事前計算しておく
    mod_facts = [1] * (N + 1)
    mod_facts_invs = [1] * (N + 1)
    for n in range(1, N + 1):
        mod_facts[n] = n * mod_facts[n - 1] % MOD
        mod_facts_invs[n] = mod_inv(mod_facts[n], MOD)

    # 有向枝(p, n)以降のノードについての番号の決め方
    pat_nums = defaultdict(int)

    def pat_num_search(p, n):
        if pat_nums[(p, n)] > 0:
            return pat_nums[(p, n)]
        rest_node_num = sum([node_nums[(n, c)] for c in adj[n] if c != p])
        coef = mod_facts[rest_node_num]
        ret = 1
        for c in adj[n]:
            if c == p:
                continue
            ret *= pat_num_search(n, c)
            ret %= MOD
            coef *= mod_facts_invs[node_nums[(n, c)]]
            coef %= MOD
        ret = ret * coef % MOD
        pat_nums[(p, n)] = ret
        return ret

    # 答えを計算
    ans = [1] * N
    for n in range(N):
        a = mod_facts[N - 1]
        for c in adj[n]:
            a *= pat_num_search(n, c)
            a *= mod_facts_invs[node_nums[(n, c)]]
            a %= MOD
        ans[n] = a
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10**6)


def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    MOD = 10**9 + 7
    N = int(input())
    adj = defaultdict(list)
    for _ in range(N - 1):
        a, b = list(map(lambda x: int(x) - 1, input().split()))
        adj[a].append(b)
        adj[b].append(a)

    # 有向枝(p, n)の先にあるnodeの数
    node_nums = defaultdict(int)

    def node_num_search(p, n):
        ret = 1
        for c in adj[n]:
            if c == p:
                continue
            ret += node_num_search(n, c)
        if p is not None:
            node_nums[(p, n)] = ret
            node_nums[(n, p)] = N - ret
        return ret

    node_num_search(None, 0)

    # mod factorialとその逆元の値を事前計算しておく
    mod_facts = [1] * (N + 1)
    mod_facts_invs = [1] * (N + 1)
    for n in range(1, N + 1):
        mod_facts[n] = n * mod_facts[n - 1] % MOD
        mod_facts_invs[n] = mod_inv(mod_facts[n], MOD)

    # 有向枝(p, n)以降のノードについての番号の決め方
    pat_nums = defaultdict(int)

    def pat_num_search(p, n):
        if pat_nums[(p, n)] > 0:
            return pat_nums[(p, n)]
        rest_node_num = sum([node_nums[(n, c)] for c in adj[n] if c != p])
        coef = mod_facts[rest_node_num]
        ret = 1
        for c in adj[n]:
            if c == p:
                continue
            ret *= pat_num_search(n, c)
            ret %= MOD
            coef *= mod_facts_invs[node_nums[(n, c)]]
            coef %= MOD
        ret = ret * coef % MOD
        pat_nums[(p, n)] = ret
        return ret

    # 答えを計算
    ans = [1] * N
    for n in range(N):
        a = mod_facts[N - 1]
        for c in adj[n]:
            a *= pat_num_search(n, c)
            a *= mod_facts_invs[node_nums[(n, c)]]
            a %= MOD
        ans[n] = a
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import copy
import math

n = int(input())

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

ans = [0] * n

def tree_search(t, n):
  if len(t[n]) == 0:
    return 1, 1
  else:
    cases = 1
    nodes = 1
    s = 0
    for i in t[n]:
      t_tmp = copy.deepcopy(t)
      t_tmp[i].remove(n)
      t_tmp[n].remove(i)
      n_of_cases, n_of_nodes = tree_search(t_tmp,i)
      cases *= n_of_cases
      nodes *= math.factorial(n_of_nodes)
      s += n_of_nodes


    return (math.factorial(s)*cases)/nodes, s+1


for i in range(n):
  t = copy.deepcopy(tree)
  ans[i], _ = tree_search(t,i)

for item in ans:
  print(int(item))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.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

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

while Q:
    x=Q.pop()
    TOP_SORT.append(x)

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

Children=[1]*(N+1)
ANS_UP=[1]*(N+1)

for x in TOP_SORT[::-1]:
    sumchild=0
    for to in E[x]:
        if to==P[x]:
            continue
        sumchild+=Children[to]
        ANS_UP[x]=ANS_UP[x]*Combi(sumchild,Children[to])%mod
                    
    Children[P[x]]+=Children[x]
    ANS_UP[P[x]]=ANS_UP[P[x]]*ANS_UP[x]%mod

ANS_DOWN=[1]*(N+1)

for x in TOP_SORT:
    
    sumchild=0
    for to in E[P[x]]:
        if to==x:
            continue
        if to==P[P[x]]:
            sumchild+=N-Children[P[x]]
            ANS_DOWN[x]=ANS_DOWN[x]*ANS_DOWN[P[x]]*Combi(sumchild,N-Children[P[x]])%mod
        else:
            sumchild+=Children[to]
            ANS_DOWN[x]=ANS_DOWN[x]*ANS_UP[to]*Combi(sumchild,Children[to])%mod

for i in range(1,N+1):
    if i==1:
        print(ANS_UP[1])
    else:
        ANS=ANS_DOWN[i]%mod

        sumchild=0
        for to in E[i]:
            if to==P[i]:
                sumchild+=N-Children[i]
                ANS=ANS*Combi(sumchild,N-Children[i])%mod
            else:                  
                sumchild+=Children[to]
                ANS=ANS*ANS_UP[to]*Combi(sumchild,Children[to])%mod

        print(ANS)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
input=sys.stdin.readline


class Reroot:
    def __init__(self, N, e, merge, f, g):
        self.G = defaultdict(list)
        self.parents = [-1]*(N+1)
        self.dp = defaultdict(lambda: defaultdict(int))
        self.ans = [0]*(N+1)
        self.merge = merge
        self.f = f
        self.g = g
        self.e = e
        self.N = N

    def add_edge(self, s, t):
        self.G[s].append(t)

    @lru_cache(maxsize=None)
    def tree_size(self, s, par=-1):
        ans = 1
        for t in self.G[s]:
            if t==par:continue
            ans += self.tree_size(t, s)
        return ans

    def build(self):
        self.dfs1(1)
        self.dfs2(1)
        return self.ans

    def dfs1(self, s):
        l = []
        q = [1]
        while q:
            s = q.pop()
            l.append(s)
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                self.parents[t] = s
                q.append(t)

        for s in l[::-1]:
            v = self.e
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                v = self.merge(v, self.f(self.dp[s][t], self.tree_size(t, s)))
            
            self.dp[self.parents[s]][s] = self.g(v, self.tree_size(s, self.parents[s]))

    def dfs2(self, s):
        q = [(s, self.e)]
        while q:
            s, dp_p = q.pop()
            par = self.parents[s]
            for t in self.G[s]:
                if t == par:
                    self.dp[s][t] = dp_p

            size = len(self.G[s])
            ac_l = [self.e] * (size+1)
            ac_r = [self.e] * (size+1)
            for i, t in enumerate(self.G[s]):
                ac_l[i+1] = self.merge(ac_l[i], self.f(self.dp[s][t], self.tree_size(t, s)))
            for i, t in enumerate(self.G[s][::-1]):
                ac_r[size-i-1] = self.merge(ac_r[size-i], self.f(self.dp[s][t], self.tree_size(t, s)))
            self.ans[s] = self.g(ac_l[size], self.N)
            for i, t in enumerate(self.G[s]):
                if t == par:
                    continue
                q.append((t, self.g(self.merge(ac_l[i], ac_r[i+1]), self.N-self.tree_size(t, s))))


def solve():
    N = int(input())

    MOD = 10**9+7
    n = N
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)

    merge = lambda x,y:(x*y)%MOD
    f = lambda x, size:(x*rev[size])%MOD
    g = lambda x, size:(x*fac[size-1])%MOD
    e = 1
    tree = Reroot(N, e, merge, f, g)

    for _ in range(N-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
        tree.add_edge(b, a)

    ans = tree.build()
    for i in range(1, N+1):
        print(ans[i])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
input=sys.stdin.readline


class Reroot:
    def __init__(self, N, e, merge, f, g):
        self.G = defaultdict(list)
        self.parents = [-1]*(N+1)
        self.dp = defaultdict(lambda: defaultdict(int))
        self.ans = [0]*(N+1)
        self.merge = merge
        self.f = f
        self.g = g
        self.e = e
        self.N = N

    def add_edge(self, s, t):
        self.G[s].append(t)

    @lru_cache(maxsize=None)
    def tree_size(self, s, par=-1):
        ans = 1
        for t in self.G[s]:
            if t==par:continue
            ans += self.tree_size(t, s)
        return ans

    def build(self):
        self.dfs1(1)
        self.dfs2(1)
        return self.ans

    def dfs1(self, s):
        l = []
        q = [1]
        while q:
            s = q.pop()
            l.append(s)
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                self.parents[t] = s
                q.append(t)

        for s in l[::-1]:
            v = self.e
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                v = self.merge(v, self.f(self.dp[s][t], self.tree_size(t, s)))
            
            self.tree_size(s, self.parents[s])
            self.dp[self.parents[s]][s] = self.g(v, self.tree_size(s, self.parents[s]))

    def dfs2(self, s):
        q = [(s, self.e)]
        while q:
            s, dp_p = q.pop()
            par = self.parents[s]
            for t in self.G[s]:
                if t == par:
                    self.dp[s][t] = dp_p

            size = len(self.G[s])
            ac_l = [self.e] * (size+1)
            ac_r = [self.e] * (size+1)
            for i, t in enumerate(self.G[s]):
                ac_l[i+1] = self.merge(ac_l[i], self.f(self.dp[s][t], self.tree_size(t, s)))
            for i, t in enumerate(self.G[s][::-1]):
                ac_r[size-i-1] = self.merge(ac_r[size-i], self.f(self.dp[s][t], self.tree_size(t, s)))
            self.ans[s] = self.g(ac_l[size], self.tree_size(s, -1))
            for i, t in enumerate(self.G[s]):
                if t == par:
                    continue
                q.append((t, self.g(self.merge(ac_l[i], ac_r[i+1]), self.N-self.tree_size(t, s))))


def solve():
    N = int(input())

    MOD = 10**9+7
    n = N
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)

    merge = lambda x,y:(x*y)%MOD
    f = lambda x, size:(x*rev[size])%MOD
    g = lambda x, size:(x*fac[size-1])%MOD
    e = 1
    tree = Reroot(N, e, merge, f, g)

    for _ in range(N-1):
        a, b = map(int, input().split())
        tree.add_edge(a, b)
        tree.add_edge(b, a)

    ans = tree.build()
    for i in range(1, N+1):
        print(ans[i])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
input=sys.stdin.readline


class Reroot:
    def __init__(self, N, e, merge, f, g):
        self.G = defaultdict(list)
        self.parents = [-1]*(N+1)
        self.dp = defaultdict(lambda: defaultdict(int))
        self.ans = [0]*(N+1)
        self.merge = merge
        self.f = f
        self.g = g
        self.e = e

    def add_edge(self, s, t):
        self.G[s].append(t)

    def build(self):
        self.dfs1(1)
        self.dfs2(1)
        return self.ans

    def dfs1(self, s):
        l = []
        q = [1]
        while q:
            s = q.pop()
            l.append(s)
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                self.parents[t] = s
                q.append(t)

        for s in l[::-1]:
            v = self.e
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                v = self.merge(v, self.f(self.dp[s][t], s, t))
            self.dp[self.parents[s]][s] = self.g(v, self.parents[s], s)

    def dfs2(self, s):
        q = [(s, self.e)]
        while q:
            s, dp_p = q.pop()
            par = self.parents[s]
            for t in self.G[s]:
                if t == par:
                    self.dp[s][t] = dp_p

            size = len(self.G[s])
            ac_l = [self.e] * (size+1)
            ac_r = [self.e] * (size+1)
            for i, t in enumerate(self.G[s]):
                ac_l[i+1] = self.merge(ac_l[i], self.f(self.dp[s][t], s, t))
            for i, t in enumerate(self.G[s][::-1]):
                ac_r[size-i-1] = self.merge(ac_r[size-i], self.f(self.dp[s][t], s, t))
            self.ans[s] = self.g(ac_l[size], -1, s)
            for i, t in enumerate(self.G[s]):
                if t == par:
                    continue
                q.append((t, self.g(self.merge(ac_l[i], ac_r[i+1]), t, s)))


def solve():
    N = int(input())

    MOD = 10**9+7
    n = N
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    d = defaultdict(list)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)

    @lru_cache(maxsize=None)
    def tree_size(s, par=-1):
        ans = 1
        for t in d[s]:
            if t==par:continue
            ans += tree_size(t, s)
        return ans

    merge = lambda x,y:(x*y)%MOD
    f = lambda x, par, s:(x*rev[tree_size(s, par)])
    g = lambda x, par, s:(x*fac[tree_size(s, par)-1])%MOD
    e = 1
    tree = Reroot(N, e, merge, f, g)

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

    ans = tree.build()
    for i in range(1, N+1):
        print(ans[i])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
input=sys.stdin.readline


class Reroot:
    def __init__(self, N, e, merge, f, g):
        self.G = defaultdict(list)
        self.parents = [-1]*(N+1)
        self.dp = defaultdict(lambda: defaultdict(int))
        self.ans = [0]*(N+1)
        self.merge = merge
        self.f = f
        self.g = g
        self.e = e

    def add_edge(self, s, t):
        self.G[s].append(t)

    def build(self):
        self.dfs1(1)
        self.dfs2(1)
        return self.ans

    def dfs1(self, s):
        l = []
        q = [1]
        while q:
            s = q.pop()
            l.append(s)
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                self.parents[t] = s
                q.append(t)

        for s in l[::-1]:
            v = self.e
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                v = self.merge(v, self.f(self.dp[s][t], s, t))
            self.dp[self.parents[s]][s] = self.g(v, self.parents[s], s)

    def dfs2(self, s):
        q = [(s, self.e)]
        while q:
            s, dp_p = q.pop()
            par = self.parents[s]
            for t in self.G[s]:
                if t == par:
                    self.dp[s][t] = dp_p

            size = len(self.G[s])
            ac_l = [self.e] * (size+1)
            ac_r = [self.e] * (size+1)
            for i, t in enumerate(self.G[s]):
                ac_l[i+1] = self.merge(ac_l[i], self.f(self.dp[s][t], s, t))
            for i, t in enumerate(self.G[s][::-1]):
                ac_r[size-i-1] = self.merge(ac_r[size-i], self.f(self.dp[s][t], s, t))
            self.ans[s] = self.g(ac_l[size], -1, s)
            for i, t in enumerate(self.G[s]):
                if t == par:
                    continue
                q.append((t, self.g(self.merge(ac_l[i], ac_r[i+1]), t, s)))


def solve():
    N = int(input())

    MOD = 10**9+7
    n = N
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    d = defaultdict(list)
    
    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)

    @lru_cache(maxsize=None)
    def tree_size(s, par=-1):
        ans = 1
        for t in d[s]:
            if t==par:continue
            ans += tree_size(t, s)
        return ans

    merge = lambda x,y:(x*y)%MOD
    f = lambda x, par, s:(x*rev[tree_size(s, par)])%MOD
    g = lambda x, par, s:(x*fac[tree_size(s, par)-1])%MOD
    e = 1
    tree = Reroot(N, e, merge, f, g)

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

    ans = tree.build()
    for i in range(1, N+1):
        print(ans[i])


if __name__ == "__main__":
    solve()