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:
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
    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
            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
    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)

Submission status: Time Limit Exceeded

Solution code:
import sys
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
    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):
    if cur != 0:
        ns = []
        cnt = 1
        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 and not up[e]:
            dfs_up(e, cur)


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


for i in range(n):
    ns = []
    cnt = 1
    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)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

mod = 10 ** 9 + 7
N = 1000000

#逆元テーブル
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]
        return 1, 1
    ns = []
    cnt = 1
    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):
    if cur != 0:
        ns = []
        cnt = 1
        if up[pre]:
            ni, cnti = up[pre]
            ns.append(ni)
            cnt = cnt * cnti % mod
        for bro in down[pre]:
            if bro != cur:
                ni, cnti = down[pre][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 and not up[e]:
            dfs_up(e, cur)


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


for i in range(n):
    ns = []
    cnt = 1
    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)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def SI(): return sys.stdin.readline()[:-1]


vert = [[]]
dp = {}
was = {}
sons = {}
mod = int(1e9 + 7)
fact = {}
invfact = {}
ans = {}


def dfs(v):
    was[v] = 1
    ans = 1
    kolvo = 1
    for son in vert[v]:
        if was[son] == 1: continue
        dfs(son)
        kolvo += sons[son]
        ans *= dp[son]
        ans %= mod
        ans *= invfact[sons[son]]
        ans %= mod
    sons[v] = kolvo
    ans *= fact[kolvo - 1]
    ans %= mod
    dp[v] = ans


def pwn(kek, pow, MD):
    mlt = 1
    while (pow):
        if (pow & 1):
            mlt *= kek
            mlt %= MD
        kek *= kek
        pow >>= 1
        kek %= MD
    return mlt


def dfs2(v, p, last):
    was[v] = 1
    if p!=-1 :
       # print(p," ",v, " ", last)
        ans[v]=dp[v]*last
        ans[v]*=invfact[sons[v]-1]
        ans[v]*=fact[sons[1]-1]
        ans[v]*=invfact[sons[1]-sons[v]]
        ans[v]%=mod
    for son in vert[v]:
        if was[son] == 1: continue
        kek=ans[v]
        kek*=pwn(dp[son], mod-2, mod)
        kek*=fact[sons[son]]
        kek*=invfact[sons[1]-1]
        kek*=fact[sons[1]-sons[son]-1]
        kek%=mod
        dfs2(son, v, kek)

def main():
    n = II()
    for i in range(0, n + 1):
        vert.append([])
        ans[i] = 0
    for i in range(0, n + 1):
        vert[i] = []
        dp[i] = 0
        was[i] = 0
        sons[i] = 0
    fact[0] = 1
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        fact[i] %= mod
    invfact[n]=pwn(fact[n], mod-2, mod)
    for i in range(n-1,-1,-1):
        invfact[i]=invfact[i+1]*(i+1)
        invfact[i]%=mod
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        fact[i] %= mod

    for i in range(0, n - 1):
        a = LI()
        vert[a[0]].append(a[1])
        vert[a[1]].append(a[0])
    dfs(1)
    ans[1] = dp[1]
    for i in range(n + 1):
        was[i] = 0
    dfs2(1, -1, 1)
    for i in range(1, n+1):
        print(ans[i])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def LLI(rows_number): return [LI() for _ in range(rows_number)]


def SI(): return sys.stdin.readline()[:-1]


vert = [[]]
dp = {}
was = {}
sons = {}
mod = int(1e9 + 7)
fact = {}
invfact = {}
ans = {}


def dfs(v):
    was[v] = 1
    ans = 1
    kolvo = 1
    for son in vert[v]:
        if was[son] == 1: continue
        dfs(son)
        kolvo += sons[son]
        ans *= dp[son]
        ans %= mod
        ans *= invfact[sons[son]]
        ans %= mod
    sons[v] = kolvo
    ans *= fact[kolvo - 1]
    ans %= mod
    dp[v] = ans


def pwn(kek, pow, MD):
    mlt = 1
    while (pow):
        if (pow & 1):
            mlt *= kek
            mlt %= MD
        kek *= kek
        pow >>= 1
        kek %= MD
    return mlt


def dfs2(v, p, last):
    was[v] = 1
    if p!=-1 :
       # print(p," ",v, " ", last)
        ans[v]=dp[v]*last
        ans[v]%=mod
        ans[v]*=invfact[sons[v]-1]
        ans[v]%=mod
        ans[v]*=fact[sons[1]-1]
        ans[v]%=mod
        ans[v]*=invfact[sons[1]-sons[v]]
        ans[v]%=mod
    for son in vert[v]:
        if was[son] == 1: continue
        kek=ans[v]
        kek*=pwn(dp[son], mod-2, mod)
        kek%=mod
        kek*=fact[sons[son]]
        kek%=mod
        kek*=invfact[sons[1]-1]
        kek%=mod
        kek*=fact[sons[1]-sons[son]-1]
        kek%=mod
        dfs2(son, v, kek)

def main():
    n = II()
    for i in range(0, n + 1):
        vert.append([])
        ans[i] = 0
    for i in range(0, n + 1):
        vert[i] = []
        dp[i] = 0
        was[i] = 0
        sons[i] = 0
    fact[0] = 1
    invfact[0] = 1
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        invfact[i] = invfact[i - 1] * pwn(i, mod - 2, mod)
        fact[i] %= mod
        invfact[i] %= mod
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i
        fact[i] %= mod

    for i in range(0, n - 1):
        a = LI()
        vert[a[0]].append(a[1])
        vert[a[1]].append(a[0])
    dfs(1)
    ans[1] = dp[1]
    for i in range(n + 1):
        was[i] = 0
    dfs2(1, -1, 1)
    for i in range(1, n+1):
        print(ans[i])

main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline


def solve(g, f, fi, m):
    def dfs(pre, cur, memo, m):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt, memo, m)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre, cur] = num, ways
        return num, ways

    memo = {}
    print(*[dfs(None, i, memo, m)[1] for i in range(1, len(g))], sep='\n')


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]
    mod = 10**9 + 7

    fact = [1] * (n+1)
    fact_inv = [1] * (n+1)

    for i in range(1, n+1):
        fact[i] = fact[i-1] * i % mod

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(1, n)[::-1]:
        fact_inv[i] = fact_inv[i+1] * (i+1) % mod

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

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline


def solve(g, f, fi, m):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre, cur] = num, ways
        return num, ways

    memo = {}
    print(*[dfs(None, i)[1] for i in range(1, len(g))], sep='\n')


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]
    mod = 10**9 + 7

    fact = [1] * (n+1)
    fact_inv = [1] * (n+1)

    for i in range(1, n+1):
        fact[i] = fact[i-1] * i % mod

    fact_inv[-1] = pow(fact[-1], mod-2, mod)

    for i in range(1, n)[::-1]:
        fact_inv[i] = fact_inv[i+1] * (i+1) % mod

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

    solve(g, fact, fact_inv, mod)


if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline


N = 2 * (10**5) + 1
MOD = 10**9 + 7

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if pre in memo and cur in memo[pre]:
            return memo[pre][cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre][cur] = num, ways
        return num, ways

    m = MOD
    memo = defaultdict(dict)
    f, fi = fact, fact_inv
    print(*[dfs(None, i)[1] for i in range(1, len(g))], sep='\n')


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

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

    solve(g)


if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n = int(input())
g = [[] for _ in range(n+1)]

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

MOD = 10**9 + 7

fact = [1] * (n+1)
fact_inv = [0] * (n+1)

for i in range(1, n + 1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def dfs(memo, pre, cur, f, fi, m=MOD):
    if pre in memo and cur in memo[pre]:
        return memo[pre][cur]

    num, ways = 1, 1

    for nxt in g[cur]:
        if nxt == pre:
            continue
        n, w = dfs(memo, cur, nxt, f, fi)
        num += n
        ways = ways * w % m * fi[n] % m

    ways = ways * f[num-1] % m
    memo[pre, cur] = num, ways
    return num, ways

memo = defaultdict(dict)

for i in range(1, len(g)):
    print(dfs(memo, None, i, fact, fact_inv)[1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

mod = 10 ** 9 + 7
N = 1000000

#逆元テーブル
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)]

def dfs(cur, pre):
    if E[cur] == [pre]:
        down[pre][cur] = [1, 1]
        return 1, 1
    ns = []
    cnt = 1
    for e in E[cur]:
        if e != pre:
            if e not in down[cur]:
                ni, cnti = dfs(e, cur)
            else:
                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]
    return S+1, cnt

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline

n = int(input())
g = [[] for _ in range(n+1)]

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

MOD = 10**9 + 7

fact = [1] * (n+1)
fact_inv = [0] * (n+1)

for i in range(1, n + 1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def dfs(pre, cur):
    if pre in memo and cur in memo[pre]:
        return memo[pre][cur]

    num, ways = 1, 1

    for nxt in g[cur]:
        if nxt == pre:
            continue
        n, w = dfs(cur, nxt)
        num += n
        ways = ways * w % m * fi[n] % m

    ways = ways * f[num-1] % m
    memo[pre, cur] = num, ways
    return num, ways


m = MOD
memo = defaultdict(dict)
f, fi = fact, fact_inv

for i in range(1, len(g)):
    print(dfs(None, i)[1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)

mod = 10 ** 9 + 7
N = 1000000

#逆元テーブル
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)]

def dfs(cur, pre):
    if E[cur] == [pre]:
        down[pre][cur] = [1, 1]
        return 1, 1
    ns = []
    cnt = 1
    for e in E[cur]:
        if e != pre:
            ni, cnti = dfs(e, cur)
            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]
    return S+1, cnt

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict


MAX_INT = 2**62-1
sys.setrecursionlimit(10**6)

input = sys.stdin.readline


N = 2 * (10**5) + 1
MOD = 10**9 + 7

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if pre in memo and cur in memo[pre]:
            return memo[pre][cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre][cur] = num, ways
        return num, ways

    m = MOD
    memo = defaultdict(dict)
    f, fi = fact, fact_inv

    for i in range(1, len(g)):
        print(dfs(None, i)[1])


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

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

    solve(g)


if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200001):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class DP():
        def __init__(self, dp=1, t=0):
            self.dp = dp
            self.t = t

        def __add__(self, other):
            return DP(self.dp*other.dp*nCr(self.t+other.t, self.t) % mod, self.t+other.t)

        def addRoot(self):
            return DP(self.dp, self.t+1)

    dp = [[DP() for _ in [0]*len(g[v])] for v in range(n)]
    dpSum = [DP() for _ in [0]*n]
    ans = [0]*n

    def dfs():
        visited = [0]*n
        q = [-1, 0]
        while len(q) > 1:
            v = q[-1]
            p = q[-2]
            flag = False
            while visited[v] < len(g[v]):
                i = visited[v]
                u = g[v][i]
                visited[v] += 1
                if u == p:
                    continue
                if visited[u]:
                    continue
                q.append(u)
                flag = True
                break
            if flag is False:
                if p != -1:
                    i = visited[p]-1
                    dp[p][i] = dpSum[v].addRoot()
                    dpSum[p] = dpSum[p]+dp[p][i]
                q.pop()

    def bfs():
        q = [(0, DP(), -1)]
        while q:
            v, dpP, p = q.pop()
            deg = len(g[v])
            for i in range(deg):
                if g[v][i] == p:
                    dp[v][i] = dpP
            dpLeft = [DP() for _ in range(deg+1)]
            dpRight = [DP() for _ in range(deg+1)]
            for i in range(deg):
                dpLeft[i+1] = dpLeft[i]+dp[v][i]
            for i in range(deg-1, -1, -1):
                dpRight[i] = dpRight[i+1]+dp[v][i]
            ans[v] = dpLeft[deg].addRoot()
            for i in range(deg):
                u = g[v][i]
                if u == p:
                    continue
                d = dpLeft[i]+dpRight[i+1]
                q.append((u, d.addRoot(), v))

    dfs()
    bfs()
    for i in range(n):
        print(ans[i].dp)


main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

MAX_INT = 2**62-1
sys.setrecursionlimit(10**5)

input = sys.stdin.readline


def n_input():
    return input().split()


# class ModOperation:

#     def __init__(self, mod):
#         self.mod = mod

#     def add(self, a, b):
#         return (a + b) % self.mod

#     def sub(self, a, b):
#         return (a - b) % self.mod

#     def mul(self, a, b):
#         m = self.mod
#         return ((a % m) * (b % m)) % m

#     def div(self, a, b):
#         m = self.mod
#         return self.mul(a, pow(b, m-2, m))


N = 2 * (10**5) + 1
MOD = 10**9 + 7

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = fact[i-1] * i % MOD
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w % m * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre, cur] = num, ways
        return num, ways

    m = MOD
    f, fi = fact, fact_inv
    memo = {}

    for i in range(1, len(g)):
        print(dfs(None, i)[1])


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

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

    solve(g)


if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys

MAX_INT = 2**62-1
sys.setrecursionlimit(10**5)

input = sys.stdin.readline

def n_input():
    return input().split()


class ModOperation:

    def __init__(self, mod):
        self.mod = mod

    def add(self, a, b):
        return (a + b) % self.mod

    def sub(self, a, b):
        return (a - b) % self.mod

    def mul(self, a, b):
        m = self.mod
        return ((a % m) * (b % m)) % m

    def div(self, a, b):
        m = self.mod
        return self.mul(a, pow(b, m-2, m))


N = 2 * (10**5) + 1
MOD = 10**9 + 7
mod = ModOperation(MOD)

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = mod.mul(fact[i-1], i)
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = ways * w * fi[n] % m

        ways = ways * f[num-1] % m
        memo[pre, cur] = num, ways
        return num, ways

    m = MOD
    f, fi = fact, fact_inv
    memo = {}
    write = sys.stdout.write

    for i in range(1, len(g)):
        write(str(dfs(None, i)[1]))
        write('\n')


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

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

    solve(g)


if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import (chain, combinations, combinations_with_replacement,
                       permutations, product)
from operator import add, mul, sub

sys.setrecursionlimit(10**5)
MAX_INT = 2**62-1

input = sys.stdin.readline


def n_input():
    return input().split()


class ModOperation:

    def __init__(self, mod):
        self.mod = mod

    def add(self, a, b):
        return (a + b) % self.mod

    def sub(self, a, b):
        return (a - b) % self.mod

    def mul(self, a, b):
        m = self.mod
        return ((a % m) * (b % m)) % m

    def div(self, a, b):
        m = self.mod
        return self.mul(a, pow(b, m-2, m))

N = 2 * (10**5) + 1
MOD = 10**9 + 7
mod = ModOperation(MOD)

fact = [1] * N
fact_inv = [0] * N

for i in range(1, 2 * (10**5)+1):
    fact[i] = mod.mul(fact[i-1], i)
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = m.mul(ways, m.mul(w, fi[n]))

        ways = m.mul(ways, f[num-1])
        memo[pre, cur] = num, ways
        return num, ways

    m, f, fi = mod, fact, fact_inv
    memo = {}

    for i in range(1, len(g)):
        print(dfs(None, i)[1])

    # print(memo)


def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

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

    solve(g)


if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import (combinations, combinations_with_replacement, chain,
                       permutations, product)
from operator import add, mul, sub

sys.setrecursionlimit(10**5)
MAX_INT = 2**62-1

input = sys.stdin.readline

def n_input():
    return input().split()


class ModOperation:

    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))


MOD = 10**9 + 7
mod = ModOperation(MOD)

fact = [1] * (2 * (10**5) + 1)
# fact_inv = [0] * (2 * (10**5) + 1)

for i in range(1, 2 * (10**5)+1):
    fact[i] = mod.mul(fact[i-1], i)
    # fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = m.mul(ways, m.div(w, f[n]))

        ways = m.mul(ways, f[num-1])
        memo[pre, cur] = num, ways
        return num, ways

    m, f = mod, fact
    memo = {}

    for i in range(1, len(g)):
        print(dfs(None, i)[1])

    # print(memo)

def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

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

    solve(g)

if __name__ == "__main__":

    main()