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: Wrong Answer

Solution code:
MOD = (10**9) + 7


class modint():
    def __init__(self, value):
        self.value = value % MOD

    def __int__(self):
        return int(self.value)

    def __float__(self):
        return float(self.value)

    def __str__(self):
        return str(self.value)

    def __repr__(self):
        return str(self.value)

    def __add__(self, other):
        return (modint(self.value + other.value) if isinstance(other, modint)
                else modint(self.value + other))

    def __sub__(self, other):
        return (modint(self.value - other.value) if isinstance(other, modint)
                else modint(self.value - other))

    def __mul__(self, other):
        return (modint(self.value * other.value) if isinstance(other, modint)
                else modint(self.value * other))

    def __truediv__(self, other):
        return (modint(self.value * pow(other.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(self.value * pow(other, MOD - 2, MOD)))

    def __pow__(self, other):
        return (modint(pow(self.value, other.value, MOD))
                if isinstance(other, modint)
                else modint(pow(self.value, other, MOD)))

    def __eq__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __ne__(self, other):
        return (self.value == other.value if isinstance(other, modint)
                else self.value == (other % MOD))

    def __radd__(self, other):
        return (modint(other.value + self.value) if isinstance(other, modint)
                else modint(other + self.value))

    def __rsub__(self, other):
        return (modint(other.value - self.value) if isinstance(other, modint)
                else modint(other - self.value))

    def __rmul__(self, other):
        return (modint(other.value * self.value) if isinstance(other, modint)
                else modint(other * self.value))

    def __rtruediv__(self, other):
        return (modint(other.value * pow(self.value, MOD - 2, MOD))
                if isinstance(other, modint)
                else modint(other * pow(self.value, MOD - 2, MOD)))

    def __rpow__(self, other):
        return (modint(pow(other.value, self.value, MOD))
                if isinstance(other, modint)
                else modint(pow(other, self.value, MOD)))

    def modinv(self):
        return modint(pow(self.value, MOD - 2, MOD))


def main():
    m = 3*(10**5)
    fac = [0] * m
    finv = [0] * m
    inv = [0] * m

    def COMBinitialize(m):
        fac[0] = 1
        finv[0] = 1
        if m > 1:
            fac[1] = 1
            finv[1] = 1
            inv[1] = 1
            for i in range(2, m):
                fac[i] = fac[i-1] * i % MOD
                inv[i] = MOD - inv[MOD % i] * (MOD // i) % MOD
                finv[i] = finv[i - 1] * inv[i] % MOD
    N = int(input())
    edge = [[] for _ in range(N)]
    deg = [0]*N
    for i in range(N-1):
        a, b = (int(i) for i in input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        deg[a-1] += 1
        deg[b-1] += 1
    COMBinitialize(m)
    maxd = max(deg)
    for i in range(N):
        ans = modint(0)
        ans += fac[deg[i]] + fac[maxd]
        print(ans/2)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000000)

def comb(n, r, fact, revfact, mod):
    return (fact[n] * (revfact[n-r] * revfact[r]) % mod) % mod

def dfs(i, parent, DP, sNum, E, fact, revfact, mod):
    Ans = 1
    sonNode = 1
    S = []
    for e in E[i]:
        if e != parent:
            mult, sn = dfs(e, i, DP, sNum, E, fact, revfact, mod)
            S.append(sn)
            Ans *= mult
            Ans %= mod
            sonNode += sn
    stotal = sonNode - 1
    for s in S:
        Ans *= comb(stotal, s, fact, revfact, mod)
        Ans %= mod
        stotal -= s
    DP[i] = Ans
    sNum[i] = sonNode - 1
    return Ans, sonNode

def solve():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)
    mod = 7 + 10 ** 9
    fact = [1] * (N + 1)
    for i in range(N): fact[i+1] = ((i + 1) * fact[i]) % mod
    revfact = [1] * (N + 1)
    revfact[N] = pow(fact[N], mod - 2, mod)
    for i in reversed(range(N)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    DP = [1] * N
    sNum = [0] * N
    usNum = [0] * N
    Ans = [1] * N
    dfs(0, 0, DP, sNum, E, fact, revfact, mod)
    q = deque()
    for e in E[0]: q.append((e, 0))
    Ans[0] = DP[0]
    while q:
        nn, parn = q.popleft()
        upperMult = DP[parn] * pow(DP[nn], mod - 2, mod)
        usNum[nn] = upperNum = sNum[parn] - sNum[nn] + usNum[parn]
        Ans[nn] = (DP[nn] * upperMult) % mod
        totalN = upperNum
        edgeOut = [upperNum]
        for e in E[nn]:
            if e != parn:
                q.append((e, nn))
                totalN += sNum[e] + 1
                edgeOut.append(sNum[e] + 1)
        for o in edgeOut:
            Ans[nn] *= comb(totalN, o, fact, revfact, mod)
            Ans[nn] %= mod
            totalN -= o
    print("\n".join(map(str, Ans)))
    
    return 0

if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

mod = 10**9+7

class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

n = int(input())
G = [[] for i 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)
PCM = PERM_COMB_MOD(2*n)
root = n//2

tmp = [[] for i in range(n)]
cost = [1]*n
size = [1]*n
def bfs1(root):
    rev = [(root, -1)]
    for i in range(n):
        cur, par = rev[i]
        for to in G[cur]:
            if to != par:
                rev.append((to, cur))
    for i in reversed(range(1,n)):
        cur, par = rev[i]
        size[par] += size[cur]
        if len(tmp[cur]) == 0:
            pass
        elif len(tmp[cur]) == 1:
            cost[cur] = tmp[cur][0]
        else:
            size_sum = 0
            inv_sum = 1
            count_sum = 1
            for to in G[cur]:
                if to != par:
                    size_sum += size[to]
                    inv_sum *= PCM.finv[size[to]]
                    inv_sum %= mod
                    count_sum *= cost[to]
                    count_sum %= mod
            cost[cur] = PCM.fac[size_sum] * inv_sum * count_sum % mod
        tmp[par].append(cost[cur])

bfs1(root)

ans = [0]*n
def bfs2(root):
    rev = [(root, -1, 1)]
    for i in range(n):
        cur, par, d_par = rev[i]
        size_par = n - size[cur]
        size_sum = 0
        inv_sum = 1
        count_sum = 1
        for to in G[cur]:
            if to != par:
                size_sum += size[to]
                inv_sum *= PCM.finv[size[to]]
                count_sum *= cost[to]
            else:
                size_sum += size_par
                inv_sum *= PCM.finv[size_par]
                count_sum *= d_par
            inv_sum %= mod
            count_sum %= mod
        ans_i = PCM.fac[size_sum]*inv_sum*count_sum % mod
        ans[i] = ans_i
        for to in G[cur]:
            if to == par:
                continue
            b = size[to]
            bb = cost[to]
            d_nxt = ans_i * PCM.fac[b] * pow(bb, mod-2, mod) * PCM.fac[size_sum-b] * PCM.finv[size_sum] % mod
            rev.append((to, cur, d_nxt))
bfs2(root)
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys

class nCrMod():
    def __init__(self, mod):
        self.mod = mod
        self.fac = [1, 1]
        self.finv = [1, 1]
        self.inv = [0, 1]

    def prep(self, n):
        mod = self.mod
        f, fi = self.fac[-1], self.finv[-1]
        for i in range(len(self.fac), n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac.append(f)
            self.finv.append(fi)
            self.inv.append(v)

    def __call__(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod

    def rev(self, n, r):
        if len(self.fac) <= n:
            self.prep(n)
        return self.finv[n] * self.fac[r] * self.fac[n - r] % self.mod

def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    mod = 10 ** 9 + 7
    nCr = nCrMod(mod)
    T = [{} for _ in range(N)]

    def h(n, f):
        if f in T[n]:
            return T[n][f]
        r = 1
        cc = 0
        for i in E[n]:
            if i == f:
                continue
            p, c = h(i, n)
            cc += c
            r = r * p * nCr(cc, c) % mod
        T[n][f] = (r, cc + 1)
        return (r, cc + 1)

    R = [0] * N
    for i in range(N):
        if len(T[i]):
            f, (p, c) = next(iter(T[i].items()))
            pp, cc = h(f, i)
            R[i] = str(p * pp * nCr(N - 1, cc))
        else:
            R[i] = str(h(i, -1)[0])
    print('\n'.join(R))

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

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

mod = 10**9+7

class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

n = int(input())
G = [[] for i 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)
PCM = PERM_COMB_MOD(2*n)

tmp = [[] for i in range(n)]
cost = [1]*n
size = [1]*n
def bfs1(root):
    rev = [(root, -1)]
    for i in range(n):
        cur, par = rev[i]
        for to in G[cur]:
            if to != par:
                rev.append((to, cur))
    for i in reversed(range(1,n)):
        cur, par = rev[i]
        size[par] += size[cur]
        if len(tmp[cur]) == 0:
            pass
        elif len(tmp[cur]) == 1:
            cost[cur] = tmp[cur][0]
        else:
            size_sum = 0
            inv_sum = 1
            count_sum = 1
            for to in G[cur]:
                if to != par:
                    size_sum += size[to]
                    inv_sum *= PCM.finv[size[to]]
                    inv_sum %= mod
                    count_sum *= cost[to]
                    count_sum %= mod
            cost[cur] = PCM.fac[size_sum] * inv_sum * count_sum % mod
        tmp[par].append(cost[cur])

bfs1(0)

ans = [0]*n
def bfs2(root):
    rev = [(root, -1, 0)]
    for i in range(n):
        cur, par, d_par = rev[i]
        size_par = n - size[cur]
        size_sum = 0
        inv_sum = 1
        count_sum = 1
        for to in G[cur]:
            if to != par:
                size_sum += size[to]
                inv_sum *= PCM.finv[size[to]]
                count_sum *= cost[to]
            else:
                size_sum += size_par
                inv_sum *= PCM.finv[size_par]
                count_sum *= d_par
            inv_sum %= mod
            count_sum %= mod
        ans_i = PCM.fac[size_sum]*inv_sum*count_sum % mod
        ans[i] = ans_i
        for to in G[cur]:
            if to == par:
                continue
            d_nxt = ans_i
            b = size[to]
            bb = cost[to]
            d_nxt = d_nxt * PCM.fac[b] * pow(bb, mod-2, mod) * PCM.fac[size_sum-b] * PCM.finv[size_sum] % mod
            rev.append((to, cur, d_nxt))
bfs2(0)
print(*ans, sep="\n")

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque

nn = 202020
mod = 10 ** 9 + 7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % mod
fainv[-1] = pow(fa[-1], mod-2, mod)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % mod

C = lambda a, b: fa[a] * fainv[b] * fainv[a-b] % mod if 0 <= b <= a else 0

N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 0
    for j in X[i]:
        a = a * BU[j] * fainv[SI[j]] % mod
        s += SI[j]
    SI[i] = s + 1
    BU[i] = fa[s] * a % mod

for i in R[1:]:
    a = TD[i] * fainv[N - SI[i]]
    for j in X[i]:
        a = a * BU[j] * fainv[SI[j]] % mod
    for j in X[i]:
        TD[j] = a * pow(BU[j], mod-2, mod) % mod * fa[SI[j]] % mod * fa[N - 1 - SI[j]] % mod

for i in range(N):
    print(BU[i] * TD[i] % mod * C(N-1, SI[i] - 1) % mod)

Submission status: Wrong Answer

Solution code:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

class PERM_COMB_MOD():
    def __init__(self, max_n=510000, mod=10**9+7):
        self.fac = [0]*max_n
        self.finv = [0]*max_n
        self.inv = [0]*max_n
        self.fac[0] = self.fac[1] = 1
        self.finv[0] = self.finv[1] = 1
        self.inv[1] = 1
        self.max = max_n
        self.mod = mod
        self._maesyori()

    def _maesyori(self):
        for i in range(2,self.max):
            self.fac[i] = self.fac[i-1] * i % self.mod
            self.inv[i] = self.mod - self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.finv[i] = self.finv[i-1] * self.inv[i] % self.mod

n = int(input())
G = [[] for i 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)
PCM = PERM_COMB_MOD(2*n)
mod = 10**9+7

tmp = [[] for i in range(n)]
cost = [1]*n
size = [1]*n
def bfs1(root):
    rev = [(root, -1)]
    for i in range(n):
        cur, par = rev[i]
        for to in G[cur]:
            if to != par:
                rev.append((to, cur))
    for i in reversed(range(1,n)):
        cur, par = rev[i]
        size[par] += size[cur]
        if len(tmp[cur]) == 0:
            pass
        elif len(tmp[cur]) == 1:
            cost[cur] = tmp[cur][0]
        else:
            size_sum = 0
            inv_sum = 1
            count_sum = 1
            for to in G[cur]:
                if to != par:
                    size_sum += size[to]
                    inv_sum *= PCM.finv[size[to]]
                    inv_sum %= mod
                    count_sum *= cost[to]
                    count_sum %= mod
            cost[cur] = PCM.fac[size_sum] * inv_sum * count_sum % mod
        tmp[par].append(cost[cur])

bfs1(0)

ans = [0]*n
def bfs2(root):
    rev = [(root, -1, 0)]
    for i in range(n):
        cur, par, d_par = rev[i]
        size_par = n - size[cur]
        size_sum = 0
        inv_sum = 1
        count_sum = 1
        for to in G[cur]:
            if to != par:
                size_sum += size[to]
                inv_sum *= PCM.finv[size[to]]
                count_sum *= cost[to]
            else:
                size_sum += size_par
                inv_sum *= PCM.finv[size_par]
                count_sum *= d_par
            inv_sum %= mod
            count_sum %= mod
        ans_i = PCM.fac[size_sum]*inv_sum*count_sum % mod
        ans[i] = ans_i
        for to in G[cur]:
            if to == par:
                continue
            d_nxt = ans_i
            b = size[to]
            bb = cost[to]
            d_nxt = d_nxt * PCM.fac[b] * pow(bb, mod-2, mod) * PCM.fac[size_sum-b] * PCM.finv[size_sum] % mod
            rev.append((to, cur, d_nxt))
bfs2(0)
print(*ans)

Submission status: Wrong Answer

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

nn = 202020
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
for i in range(nn):
    fa[i+1] = fa[i] * (i+1) % mod
fainv[-1] = pow(fa[-1], mod-2, mod)
for i in range(nn)[::-1]:
    fainv[i] = fainv[i+1] * (i+1) % mod

C = lambda a, b: fa[a] * fainv[b] * fainv[a-b] % mod if 0 <= b <= a else 0

N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 0
    for j in X[i]:
        a = a * BU[j] * fainv[SI[j]] % mod
        s += SI[j]
        SI[i] += SI[j]
    BU[i] = fa[s] * a % mod

for i in R[1:]:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    s = N - SI[i] + sum([SI[j] for j in X[i]])
    for j in range(c):
        AL[j+1] = AL[j] * BU[X[i][j]] * fainv[SI[X[i][j]]] % mod
    for j in range(c)[::-1]:
        AR[j] = AR[j+1] * BU[X[i][j]] * fainv[SI[X[i][j]]] % mod
    for j in range(c):
        TD[X[i][j]] = TD[i] * fainv[N - SI[i]] * AL[j] * AR[j+1] * fa[s - SI[X[i][j]]] % mod

for i in range(N):
    print(BU[i] * TD[i] * C(N-1, SI[i] - 1) % mod)

Submission status: Time Limit Exceeded

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

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7
def comb_mod(n,r):
  ans = 1
  for i in range(r):
    ans *= (n-i)*pow(i+1,mod-2,mod)
    ans %= mod
  return ans
def combs_mod(n,k):
  #nC0からnCkまで
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*pow(i,mod-2,mod)%mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u] = v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= comb_mod(part_num[v]-1, part_num[u])*ans[u]%mod
        ans[v] %= mod
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  combs = combs_mod(N-1,N-1)
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*combs[part_num[u]],mod-2,mod)%mod
      ans[u] *= combs[part_num[u]-1]*p_value[u]
      ans[u] %= mod
      stack.append(u)
    ans[v] %= mod
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7
def comb_mod(n,r):
  ans = 1
  for i in range(r):
    ans *= (n-i)*pow(i+1,mod-2,mod)
    ans %= mod
  return ans
def combs_mod(n,k):
  #nC0からnCkまで
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*pow(i,mod-2,mod)%mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u] = v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= comb_mod(part_num[v]-1, part_num[u])*ans[u]
        ans[v] %= mod
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  combs = combs_mod(N-1,N-1)
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*combs[part_num[u]],mod-2,mod)%mod
      ans[u] *= combs[part_num[u]-1]*p_value[u]
      ans[u] %= mod
      stack.append(u)
    ans[v] %= mod
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7
def comb_mod(n,r):
  ans = 1
  for i in range(r):
    ans *= (n-i)*pow(i+1,mod-2,mod)
    ans %= mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u]=v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= comb_mod(part_num[v]-1,part_num[u])*ans[u]
        ans[v] %= mod
    if marker==0:
      stack.pop()
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*comb_mod(N-1, part_num[u]),mod-2,mod)%mod
      ans[u] *= comb_mod(N-1,part_num[u]-1)*p_value[u]
      ans[u] %= mod
      stack.append(u)
    ans[v] %= mod
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

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

def facinv(N):
    fac,finv,inv=[0]*(N+1),[0]*(N+1),[0]*(N+1)
    fac[0]=1;fac[1]=1;finv[0]=1;finv[1]=1;inv[1]=1
    for i in range(2,N+1):
        fac[i]=fac[i-1]*i%MOD
        inv[i]=MOD-inv[MOD%i]*(MOD//i)%MOD
        finv[i]=finv[i-1]*inv[i]%MOD
    return fac,finv,inv

def dfs(v,p):
    connect[v]=len(G[v])
    dp[v]=[1]*connect[v]
    sizdp[v]=[0]*connect[v]
    for i in range(connect[v]):
        nv=G[v][i]
        if nv==p:
            p_i[v]=i
            continue
        R,siz=dfs(nv,v)
        dp[v][i]=R
        size[v]+=siz
        sizdp[v][i]=siz
    res=fac[size[v]-1]
    for i in range(connect[v]):
        if G[v][i]==p:
            continue
        res=res*dp[v][i]%MOD*finv[sizdp[v][i]]%MOD
    return res,size[v]
    
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][p_i[v]]=res_p
        sizdp[v][p_i[v]]=N-size[v]
    ans[v]=fac[N-1]
    for i in range(connect[v]):
        ans[v]=ans[v]*dp[v][i]%MOD*finv[sizdp[v][i]]%MOD
    dp_L=[1]*(connect[v]+1)
    dp_R=[1]*(connect[v]+1)
    for i in range(connect[v]):
        dp_L[i+1]=dp_L[i]*dp[v][i]%MOD*finv[sizdp[v][i]]%MOD
    for i in reversed(range(connect[v])):
        dp_R[i]=dp_R[i+1]*dp[v][i]%MOD*finv[sizdp[v][i]]%MOD
        
    for i in range(connect[v]):
        nv=G[v][i]
        if nv==p:
            continue

        reroot(nv,fac[N-size[nv]-1]*dp_L[i]*dp_R[i+1]%MOD,v)


N=int(input())
fac,finv,inv=facinv(N)
G=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
dp=[[] for i in range(N)]
sizdp=[[] for i in range(N)]
connect=[-1]*N
size=[1]*N
p_i=[-1]*N
dp_L=[[] for i in range(N)]
dp_R=[[] for i in range(N)]
ans=[1]*N
dfs(0,-1)
reroot(0,1,-1)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
def rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    G = [[] for _ in range(n)]
    G_idxs = [[] for _ in range(n)]  # 自分を指すノードのインデックス
    for a, b in edges:
        G_idxs[a].append(len(G[b]))
        G_idxs[b].append(len(G[a]))
        G[a].append(b)
        G[b].append(a)
    # step 1
    parents = [0] * n
    order = []  # 行きがけ順
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order.append(v)
        for u in G[v]:
            if p != u:
                stack.append(u)
                parents[u] = v
    subtree_res = [[0]*len(Gv) for Gv in G]
    # 下から登る
    for v in order[:0:-1]:
        p = parents[v]
        result = identity
        for idx_Gv, (u, subtree_res_v_i) in enumerate(zip(G[v], subtree_res[v])):
            if p == u:
                parent_idx = idx_Gv
            else:
                result = merge(result, subtree_res_v_i)
        idx_p2v = G_idxs[v][parent_idx]
        subtree_res[p][idx_p2v] = add_node(result, v)
    # step 2
    # 上から降りる
    results = [0] * n
    for v in order:
        subtree_res_v = subtree_res[v]
        cum = identity
        cum_from_tail = [identity]
        for r in subtree_res_v[:0:-1]:
            cum = merge(r, cum)
            cum_from_tail.append(cum)
        cum_from_tail.reverse()
        cum = identity
        for r, cum_t, u, idx_u2v in zip(subtree_res_v, cum_from_tail, G[v], G_idxs[v]):
            result = add_node(merge(cum, cum_t), v)
            subtree_res[u][idx_u2v] = result
            cum = merge(cum, r)
        results[v] = add_node(cum, v)
    return results

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

N = int(input())
AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
mod = 10**9 + 7
comb = Combination(202020)
identity = (1, 0)
merge = lambda a, b: (a[0] * b[0] % mod * comb(a[1]+b[1], a[1]) % mod, a[1] + b[1])
add_node = lambda value, idx: (value[0], value[1]+1)
Ans = rerooting(N, AB, identity, merge, add_node)
print("\n".join(str(ans) for ans, _ in Ans))

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)