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:
class ReRooting:
    def __init__(self, size, root, identDp=0, identCum=0):
        """
        identDp: 木DP用 lift(a, identDp) = a
        identCum: 累積用 merge(a, identCum) = a
        """
        self.size = size
        self.edges = [[] for _ in range(self.size + 1)]
        self.root = root
        self.identDp = identDp
        self.identCum = identCum

    def addEdge(self, fr, to):
        self.edges[fr].append(to)
        self.edges[to].append(fr)

    # 根を固定したときの木DP
    def lift(self, top, bottom):
        return (((top[0] * bottom[0]) % MOD * comb.ncr(top[1] + bottom[1] + 1, top[1])) % MOD, top[1] + bottom[1] + 1)

    # 子の累積
    def merge(self, cum, a):
        return (((cum[0] * a[0]) % MOD * comb.ncr(cum[1] + a[1], cum[1])) % MOD, cum[1] + a[1])

    def sol(self):
        # 普通に木DPをする
        # 並行して各頂点につき、子の値の累積liftを左右から求めておく
        # その後根から順番に、親からの寄与を求めていく(fromParent)
        N = self.size
        edges = self.edges

        st = [self.root]
        parent = [-1] * (N + 1)
        child = [[] for _ in range(N + 1)]
        order = []
        while st:
            v = st.pop()
            order.append(v)
            for to in edges[v]:
                if parent[v] == to:
                    continue
                parent[to] = v
                child[v].append(to)
                st.append(to)

        dp = [self.identDp] * (N + 1)
        left = [self.identCum] * (N + 1)
        right = [self.identCum] * (N + 1)
        for v in order[::-1]:
            tmp = self.identCum
            for ch in child[v]:
                left[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            tmp = self.identCum
            for ch in reversed(child[v]):
                right[ch] = tmp
                tmp = self.lift(tmp, dp[ch])
            dp[v] = tmp

        fromParent = [self.identDp] * (N + 1)
        for v in order:
            if v == self.root:
                continue
            fromParent[v] = self.lift(self.merge(left[v], right[v]), fromParent[parent[v]])
            dp[v] = self.lift(dp[v], fromParent[v])

        return dp[:N]

class Combination:
    def __init__(self, size, MOD=10**9 + 7):
        self.size = size + 2
        self.MOD = MOD
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.MOD
            self.inv[i] = -self.inv[self.MOD % i] * (self.MOD // i) % self.MOD
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.MOD

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.MOD

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.MOD) % self.MOD

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N = int(input())
MOD = 10**9 + 7
comb = Combination(2 * 10**5 + 100)

tree = ReRooting(N, 0, (1, -1), (1, 0))

for _ in range(N - 1):
    fr, to = map(int, input().split())
    tree.addEdge(fr - 1, to - 1)

ans = tree.sol()
print(*[a for a, b in ans], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size

        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod

    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod

    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod

    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)

    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]

N = int(input())
MOD = 10**9 + 7
comb = Combination(N + 100)

edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    fr, to = map(int, input().split())
    edges[fr].append(to)
    edges[to].append(fr)

parent = [0] * (N + 1)
order = []
st = [1]
while st:
    now = st.pop()
    order.append(now)
    for to in edges[now]:
        if to == parent[now]:
            continue
        st.append(to)
        parent[to] = now

size = [1] * (N + 1)
for v in order[::-1]:
    size[parent[v]] += size[v]

dp = [1] * (N + 1)
for v in order[::-1]:
    dp[v] = dp[v] * comb.fact[size[v] - 1] % MOD
    dp[parent[v]] *= dp[v] * comb.factInv[size[v]]

ans = [1] * (N + 1)
dpL = [[] for _ in range(N + 1)]
dpR = [[] for _ in range(N + 1)]
eToI = [{to: i for i, to in enumerate(edges[v])} for v in range(N + 1)]

for v in order:
    pr = parent[v]
    M = len(edges[v])
    L = [1] * (M + 1)
    R = [1] * (M + 1)

    for i, to in enumerate(edges[v]):
        if to == pr:
            j = eToI[pr][v]
            L[i + 1] = L[i] * dpL[pr][j] * dpR[pr][j + 1] * comb.fact[N - size[v] - 1] * comb.factInv[N - size[v]] % MOD
        else:
            L[i + 1] = L[i] * dp[to] * comb.factInv[size[to]] % MOD
    for i, to in enumerate(edges[v][::-1]):
        if to == pr:
            j = eToI[pr][v]
            R[i + 1] = R[i] * dpL[pr][j] * dpR[pr][j + 1] * comb.fact[N - size[v] - 1] * comb.factInv[N - size[v]] % MOD
        else:
            R[i + 1] = R[i] * dp[to] * comb.factInv[size[to]] % MOD

    dpL[v] = L
    dpR[v] = R[::-1]
    ans[v] = R[-1] * comb.fact[N - 1] % MOD

print(*ans[1:], sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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

mod = 10**9+7 #出力の制限
N = 10**6
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 )

# topological sort
s = []
s.append(0)
parent = [-1]*n
order = []
while s:
    v = s.pop()
    order.append(v)
    for u in g[v]:
        if u == parent[v]:
            continue
        parent[u] = v
        s.append(u)

dp = [1]*n
c = [0]*n
order.reverse()
for v in order:
    dp[v] *= g1[c[v]]
    dp[v] %= mod
    c[v] += 1
    if parent[v] == -1:
        continue
    c[parent[v]] += c[v]
    dp[parent[v]] *= (dp[v]*g2[c[v]])
    dp[parent[v]] %= mod

order.reverse()
ans = [0]*n
for v in order:
    ans[v] = dp[v]
    for u in g[v]:
        if u == parent[v]:
            continue
        dp[u] *= ans[v]*g2[c[v]-1]*g1[c[v]-1-c[u]]*g1[c[u]]*pow(dp[u],(mod-2),mod)
        dp[u] *= g2[c[u]-1]
        dp[u] *= g1[c[v]-1]
        dp[u] *= g2[c[v]-c[u]]
        dp[u] %= mod
        c[u] = c[v]
for i in range(n):
    print(ans[i]%mod)

Submission status: Time Limit Exceeded

Solution code:
from functools import *
from collections import *
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)

M = 10**9+7

@lru_cache(maxsize=None)
def mod_inv(a):
  b, x, y = M, 1, 0
  while a != 1:
    (d, a), b = divmod(b, a), a
    x, y = y-d*x, x
  return x%M

cache = defaultdict(dict)
def calc_cache(root, parent):
  c = cache[root]
  if not c or parent in c:
    return
  
  if c and None not in c:
    for p, (r2, t2, s2) in c.items():
      r3, t3, s3 = calc_subtree(p, root)
      r = r2 * t3
      s = s2 + s3
      c[None] = r, None, s
      break
  
  if parent is None:
    return
  
  if None in c:
    r0, t0, s0 = c[None]
    r1, t1, s1 = calc_subtree(parent, root)
    r = r0 * mod_inv(t1) % M
    s = s0 - s1
    c[parent] = r, r * mod_inv(s) % M, s

  
def calc_subtree(root, parent):
  calc_cache(root, parent)
  
  if parent in cache[root]:
    return cache[root][parent]
  
  ret = 1
  size = 1
  for child in (Edge[root] - {parent}):
    r, t, s = calc_subtree(child, root)
    ret = ret * t % M
    size += s
  cache[root][parent] = ret, ret * mod_inv(size) % M if parent else None, size
  return cache[root][parent]

N = int(input())
Edge = defaultdict(set)
fact = 1
for i in range(1, N):
  fact = fact * i % M
  a, b = map(int, input().split())
  Edge[a].add(b)
  Edge[b].add(a)

for i in range(1, N+1):
  print(calc_subtree(i, None)[0] * fact % M)

Submission status: Time Limit Exceeded

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

M = 10**9+7

@lru_cache(maxsize=None)
def mod_inv(a):
  b, x, y = M, 1, 0
  while a != 1:
    (d, a), b = divmod(b, a), a
    x, y = y-d*x, x
  return x%M

cache = defaultdict(dict)
def calc_cache(root, parent):
  c = cache[root]
  if not c or parent in c:
    return
  
  if c and None not in c:
    for p, (r2, t2, s2) in c.items():
      r3, t3, s3 = calc_subtree(p, root)
      r = r2 * t3
      s = s2 + s3
      c[None] = r, None, s
      break
  
  if parent is None:
    return
  
  if None in c:
    r0, t0, s0 = c[None]
    r1, t1, s1 = calc_subtree(parent, root)
    r = r0 * mod_inv(t1) % M
    s = s0 - s1
    c[parent] = r, r * mod_inv(s) % M, s

  
def calc_subtree(root, parent):
  calc_cache(root, parent)
  
  if parent in cache[root]:
    return cache[root][parent]
  
  ret = 1
  size = 1
  for child in (Edge[root] - {parent}):
    r, t, s = calc_subtree(child, root)
    ret = ret * t % M
    size += s
  cache[root][parent] = ret, ret * mod_inv(size) % M if parent else None, size
  return cache[root][parent]

N = int(input())
Edge = defaultdict(set)
fact = 1
for i in range(1, N):
  fact = fact * i % M
  a, b = map(int, input().split())
  Edge[a].add(b)
  Edge[b].add(a)

for i in range(1, N+1):
  print(calc_subtree(i, None)[0] * fact % M)

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
N=10**5*2
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
o=[]
s=[0]
f=[1]*n
while s:
    v=s.pop()
    f[v]=0
    o+=v,
    l=[]
    for w in e[v]:
        if f[w]:
            l+=w,
            s+=w,
    e[v]=l
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
for v in o[::-1]:
    s=b=1
    c1,c2=[1],[1]
    for w in e[v]:
        u=sz1[w]
        b=b*dp1[w]*inv[u]%M
        c1+=b,
        s+=u
    b=1
    for w in e[v][::-1]:
        b=b*dp1[w]*inv[sz1[w]]%M
        c2+=b,
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=b*fac[s-1]%M
# print(dp1)
sz2[0]=1
dp2[0]=1
for v in o:
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
# print(dp2)
a=[]
for dp1,dp2,sz1,sz2 in zip(dp1,dp2,sz1,sz2):
    sz1-=1
    sz2-=1
    a+=str(dp1*dp2*inv[sz1]*inv[sz2]*fac[sz1+sz2]%M),
print('\n'.join(a))

Submission status: Time Limit Exceeded

Solution code:
M=10**9+7
N=10**5*2
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
o=[]
s=[0]
f=[1]*n
while s:
    v=s.pop()
    f[v]=0
    o+=v,
    l=[]
    for w in e[v]:
        if f[w]:
            l+=w,
            s+=w,
    e[v]=l
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
for v in o[::-1]:
    s=1
    c1,c2=[1],[1]
    for w in e[v]:
        u=sz1[w]
        c1+=c1[-1]*dp1[w]*inv[u]%M,
        s+=u
    for w in e[v][::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=c1[-1]*fac[s-1]%M
# print(dp1)
sz2[0]=1
dp2[0]=1
for v in o:
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
# print(dp2)
a=[]
for dp1,dp2,sz1,sz2 in zip(dp1,dp2,sz1,sz2):
    sz1-=1
    sz2-=1
    a+=str(dp1*dp2*inv[sz1]*inv[sz2]*fac[sz1+sz2]%M),
print('\n'.join(a))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
M=10**9+7
N=10**5*2
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
def dfs1(v,p):
    s=1
    l=[]
    c1,c2=[1],[1]
    for w in e[v]:
        if w==p:continue
        l+=w,
        dfs1(w,v)
        u=sz1[w]
        c1+=c1[-1]*dp1[w]*inv[u]%M,
        s+=u
    for w in l[::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    e[v]=l
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=c1[-1]*fac[s-1]%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
dfs1(0,-1)
# print(dp1)
sz2[0]=1
dp2[0]=1
s=[0]
while s:
    v=s.pop()
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
        s+=w,
# print(dp2)
a=[]
for dp1,dp2,sz1,sz2 in zip(dp1,dp2,sz1,sz2):
    sz1-=1
    sz2-=1
    a+=str(dp1*dp2*inv[sz1]*inv[sz2]*fac[sz1+sz2]%M),
print('\n'.join(a))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
M=10**9+7
N=10**5*2
fac=[0]*(N+1)
fac[0]=b=1
for i in range(1,N+1):fac[i]=b=b*i%M
inv=[0]*(N+1)
inv[N]=b=pow(fac[N],M-2,M)
for i in range(N,0,-1):inv[i-1]=b=b*i%M
def dfs1(v,p):
    s=1
    l=[]
    c1,c2=[1],[1]
    for w in e[v]:
        if w==p:continue
        l+=w,
        dfs1(w,v)
        u=sz1[w]
        c1+=c1[-1]*dp1[w]*inv[u]%M,
        s+=u
    for w in l[::-1]:
        c2+=c2[-1]*dp1[w]*inv[sz1[w]]%M,
    e[v]=l
    c[v]=c1,c2[::-1]
    sz1[v]=s
    dp1[v]=c1[-1]*fac[s-1]%M
n,*t=open(0).read().split()
n=int(n)
e=[[]for _ in range(n)]
for a,b in zip(*[map(int,t)]*2):
    e[a-1]+=b-1,
    e[b-1]+=a-1,
sz1,sz2=[0]*n,[0]*n
dp1,dp2=[0]*n,[0]*n
c=[[]for _ in range(n)]
dfs1(0,-1)
# print(dp1)
sz2[0]=1
dp2[0]=1
s=[0]
while s:
    v=s.pop()
    l=len(e[v])
    c1,c2=c[v]
    uv=sz2[v]-1
    tv=dp2[v]*inv[uv]
    for i,w in enumerate(e[v]):
        tw=c1[i]*c2[i+1]%M
        uw=uv+sz1[v]-sz1[w]-1
        dp2[w]=tv*tw*fac[uw]%M
        sz2[w]=uw+2
        s+=w,
# print(dp2)
for i in range(n):
    u1=sz1[i]-1
    u2=sz2[i]-1
    print(dp1[i]*dp2[i]*inv[u1]*inv[u2]*fac[u1+u2]%M)

Submission status: Time Limit Exceeded

Solution code:
# 全方位DP
import sys
input = sys.stdin.readline
sys.setrecursionlimit(20000000)
from collections import defaultdict, deque
from math import factorial

MOD = 10**9+7
class Facts():
    def __init__(self, max_num=10**5, p=10**9 + 7):
        self.p = p
        self.max_num = max_num
        self.fact = [1] * (self.max_num + 1)
        for i in range(1, self.max_num + 1):
            self.fact[i] = self.fact[i-1] * i
            self.fact[i] %= self.p

    def comb(self, n, k):
        if n < 0 or k < 0 or n < k:
            return 0
        if n == 0 or k == 0:
            return 1
        a = self.fact[n]
        b = self.fact[k]
        c = self.fact[n-k]
        return (a*self.power_func(b, self.p-2) *
                self.power_func(c, self.p-2)) % self.p

    def power_func(self, a, b):
        ans = 1
        while b > 0:
            if b & 1:
                ans = ans * a % self.p
            a = a * a % self.p
            b >>= 1
        return ans

    def fact_inv(self, a):
        return self.power_func(a, self.p-2) % self.p

n = int(input())
fact = Facts(max_num=200000)
edges = defaultdict(lambda: [])

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

# step1 吸い上げ
size = [1 for _ in range(n+1)]
def dfs1(n, par=-1):
    res = 1
    for node in edges[n]:
        if node == par:
            continue
        else:
            res += dfs1(node, n)
    res %= MOD
    size[n] = res
    return res
dfs1(1)
# print(size)
dp = [0 for _ in range(n+1)]
def dfs2(n, par=-1):
    res = fact.fact[size[n] - 1]
    for node in edges[n]:
        if node == par:
            continue
        else:
            res *= dfs2(node, n) * fact.fact_inv(fact.fact[size[node]])
    res %= MOD
    dp[n] = res
    return res
dfs2(1)
# print(dp)

# step2 還元
ans = [0 for _ in range(n+1)]
def dfs3(num, par=-1):
    if par != -1:
        d_par = ans[par] * fact.fact_inv(fact.fact[n-1]) * fact.fact[n-size[num]-1] * fact.fact[size[num]] * fact.fact_inv(dp[num]) % MOD
        res = dp[num] * fact.fact_inv(fact.fact[size[num] - 1]) * fact.fact[n-1] * d_par * fact.fact_inv(fact.fact[n-size[num]]) % MOD
        ans[num] = res
    else:
        ans[num] = dp[num]
    for node in edges[num]:
        if node == par:
            continue
        dfs3(node, num)
dfs3(1)
print("\n".join(list(map(str, ans[1:]))))

Submission status: Time Limit Exceeded

Solution code:
import sys
from functools import lru_cache
from collections import defaultdict
sys.setrecursionlimit(2 * 10 ** 5 + 1)

MOD = 10**9 + 7

N, = [int(x) for x in input().split()]
edges = [[int(x) for x in input().split()] for i in range(N - 1)]

graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)


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


@lru_cache(maxsize=None)
def modInverse(a, p):
    # Fermat's little theorem, a**(p-1) = 1 mod p
    return pow(a, p - 2, p)


@lru_cache(maxsize=None)
def brute(node, parent=None):
    counts = []
    ways = 1
    for nbr in graph[node]:
        if nbr != parent:
            childCount, childWays = brute(nbr, node)
            counts.append(childCount)
            ways *= childWays

    denominator = 1
    for c in counts:
        denominator *= factMod[c]
    ways = (ways * factMod[sum(counts)] * modInverse(denominator, MOD)) % MOD

    return 1 + sum(counts), ways % MOD


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

Submission status: Time Limit Exceeded

Solution code:
from fractions import gcd
import sys
sys.setrecursionlimit(4100000)

def os(): return input()
def oi(): return int(input())
def oli(): return map(int, input().split())
def olai(): return list(map(int, input().split()))
def olas(): return list(input().split())
def mlai(L): return [int(input()) for _ in range(L)]
def mlas(L): return [input() for _ in range(L)]

def ar(a, b, c=-1, d=-1, INIT=0):
    if(c==-1): return [[INIT]*b for _ in range(a)]
    if(d==-1): return [[[INIT]*c for _ in range(b)] for __ in range(a)]
    return [[[[INIT]*d for _ in range(c)] for __ in range(b)] for ___ in range(a)]

def lcm(a, b): return (a*b)//gcd(a, b)

#MOD
P = 10**9 + 7
N = 200001 #使う最大値+1以上にする、値に注意3*10^5とかにしとくと安心
inv = [0] + [1] # 1/x
finv = [1] + [1] # 1/x!
fac = [1] + [1] # x!
for i in range(2, N):
  inv += [inv[P % i] * (P - int(P / i)) % P]
  fac += [(fac[i-1] * i) % P]
  finv += [(finv[i-1] * inv[i]) % P]

def comb(a, b):
    if a<b or b < 0: return 0 # error
    return (fac[a] * ((finv[b] * finv[a-b]) % P)) %P




class T:
    num = 1
    child = 0

    def __init__(self, a, b):
        self.num = a
        self.child = b

def step(x):
    return T(x.num, x.child+1)
def merge(x, y):
    if(x.num==-1): return y
    if(y.num==-1): return x
    return T((x.num*y.num*comb(x.child+y.child, x.child))%P, x.child+y.child)

G = [[] for _ in range(200001)]
down_data = [T(-1, -1) for _ in range(200001)]
dat = [T(-1, -1) for _ in range(200001)]
def dfs(now, parent):
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        cnt += 1
        dfs(to, now)
        down_data[now] = merge(down_data[now], step(down_data[to]))
    if(cnt==0): down_data[now] = T(1, 0)

def dfs_rev(now, parent, rev):
    left = []
    right = []
    cnt = 0
    for to in G[now]:
        if(to==parent): continue
        if(len(left)==0): left.append(step(down_data[to]))
        else: left.append(merge(left[cnt-1], step(down_data[to])))
        cnt += 1

    cnt = 0
    for to in reversed(G[now]):
        if(to==parent): continue
        if(len(right)==0): right.append(step(down_data[to]))
        else: right.append(merge(right[cnt-1], step(down_data[to])))
        cnt += 1

    cnt = 0
    dat[now] = merge(rev, down_data[now])

    for to in G[now]:
        if(to==parent): continue
        x = T(-1, -1) if cnt==0 else left[cnt-1]
        y = T(-1, -1) if cnt==len(right)-1 else right[len(right)-2-cnt]
        dfs_rev(to, now, step(merge(rev, merge(x, y))))
        cnt += 1

def main():
    n = oi()
    for i in range(n-1):
        a, b = oli()
        G[a].append(b)
        G[b].append(a)

    root = -1
    for i in range(1, n+1):
        if(len(G[i]) == 1):
            root = i
            break
    dfs(root, -1)
    dfs_rev(root, -1, T(1, 0))

    for i in range(1, n+1):
        print(dat[i].num)



if __name__ == "__main__": main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline
    sys.setrecursionlimit(1000000)

    n = int(input())

    E = [[] for i in range(n)]
    for i 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
    N = n + 1

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

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

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

    down = [{} for i in range(n+1)]
    up = [0 for i in range(n+1)]

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]

    def dfs_up(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ns = []
                cnt = 1
                ns_append = ns.append
                if up[pre]:
                    ni, cnti = up[pre]
                    ns_append(ni)
                    cnt = cnt * cnti % mod
                bros = down[pre]
                for bro in bros:
                    if bro != cur:
                        ni, cnti = bros[bro]
                        ns_append(ni)
                        cnt = cnt * cnti % mod
                s = sum(ns)
                S = s
                for ni in ns:
                    cnt = cnt * cmb(s, ni) % mod
                    s -= ni
                up[cur] = [S+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])


    dfs_down(0, n)
    dfs_up(0, n)


    for i in range(n):
        ns = []
        cnt = 1
        ns_append = ns.append
        if up[i]:
            ni, cnti = up[i]
            ns_append(ni)
            cnt = cnt * cnti % mod
        for bro in down[i]:
            ni, cnti = down[i][bro]
            ns_append(ni)
            cnt = cnt * cnti % mod
        s = sum(ns)
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    from collections import deque

    input = sys.stdin.readline
    sys.setrecursionlimit(1000000)

    mod = 10 ** 9 + 7
    N = 200001

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

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

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

    n = int(input())

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

    down = [{} for i in range(n+1)]
    up = [0 for i in range(n+1)]

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]

    def dfs_up(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ns = []
                cnt = 1
                ns_append = ns.append
                if up[pre]:
                    ni, cnti = up[pre]
                    ns_append(ni)
                    cnt = cnt * cnti % mod
                bros = down[pre]
                for bro in bros:
                    if bro != cur:
                        ni, cnti = bros[bro]
                        ns_append(ni)
                        cnt = cnt * cnti % mod
                s = sum(ns)
                S = s
                for ni in ns:
                    cnt = cnt * cmb(s, ni) % mod
                    s -= ni
                up[cur] = [S+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])


    dfs_down(0, n)
    dfs_up(0, n)


    for i in range(n):
        ns = []
        cnt = 1
        ns_append = ns.append
        if up[i]:
            ni, cnti = up[i]
            ns_append(ni)
            cnt = cnt * cnti % mod
        for bro in down[i]:
            ni, cnti = down[i][bro]
            ns_append(ni)
            cnt = cnt * cnti % mod
        s = sum(ns)
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

input = sys.stdin.readline
sys.setrecursionlimit(1000000)

mod = 10 ** 9 + 7
N = 200001

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

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

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

n = int(input())

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

down = [{} for i in range(n+1)]
up = [0 for i in range(n+1)]

def dfs_down(cur, pre):
    if E[cur] == [pre]:
        down[pre][cur] = [1, 1]
    ns = []
    cnt = 1
    ns_append = ns.append
    for e in E[cur]:
        if e != pre:
            if e not in down[cur]:
                dfs_down(e, cur)
            ni, cnti = down[cur][e]
            ns_append(ni)
            cnt = cnt * cnti % mod
    s = sum(ns)
    S = s
    for ni in ns:
        cnt = cnt * cmb(s, ni) % mod
        s -= ni
    down[pre][cur] = [S+1, cnt]

def dfs_up(cur, pre):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop() 
        if cur != 0:
            ns = []
            cnt = 1
            ns_append = ns.append
            if up[pre]:
                ni, cnti = up[pre]
                ns_append(ni)
                cnt = cnt * cnti % mod
            bros = down[pre]
            for bro in bros:
                if bro != cur:
                    ni, cnti = bros[bro]
                    ns_append(ni)
                    cnt = cnt * cnti % mod
            s = sum(ns)
            S = s
            for ni in ns:
                cnt = cnt * cmb(s, ni) % mod
                s -= ni
            up[cur] = [S+1, cnt]
        for e in E[cur]:
            if e != pre:
                stack.append([e, cur])


dfs_down(0, n)
dfs_up(0, n)


for i in range(n):
    ns = []
    cnt = 1
    ns_append = ns.append
    if up[i]:
        ni, cnti = up[i]
        ns_append(ni)
        cnt = cnt * cnti % mod
    for bro in down[i]:
        ni, cnti = down[i][bro]
        ns_append(ni)
        cnt = cnt * cnti % mod
    s = sum(ns)
    for ni in ns:
        cnt = cnt * cmb(s, ni) % mod
        s -= ni
    print(cnt)