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:
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 28 22:56:10 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

N = int(input())
#X, Y = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]

fact = [1, 1] # 元テーブル
fact_inv = [1, 1] # 逆元テーブル
tmp_inv = [0, 1] # 逆元テーブル計算用テーブル
for i in range(2, N+1):
    fact.append((fact[-1] * i) % mod)
    tmp_inv.append((-tmp_inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * tmp_inv[-1]) % mod)
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod
#逆元作成
def inv(a,mod):
    return pow(a,mod-2,mod)

graph = [[] for _ in range(N+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

dp = [1] * (N + 1)
size = [0] * (N + 1)
def dfs(par, v):
    for u in graph[v]:
        if par == u:
            continue
        dfs(v, u)
        size[v] += size[u]
        dp[v] = dp[v] * dp[u] * fact_inv[size[u]] % mod
    dp[v] = dp[v] * fact[size[v]] % mod
    size[v] += 1

ans = [0] * (N + 0)
def reroot(par, val_par, size_par, v):
    ans[v-1] = val_par * dp[v] * cmb(N-1, size_par, mod) % mod
    for u in graph[v]:
        if par == u:
            continue
        val = ans[v-1] * inv(dp[u] * cmb(N-1, size[u],mod),mod) % mod
        reroot(v, val, N - size[u], u)

dfs(-1,1)
reroot(-1,1,0,1)
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Tue Apr 28 22:56:10 2020
"""

import sys
#import numpy as np

sys.setrecursionlimit(10 ** 9)
#def input():
#    return sys.stdin.readline()[:-1]
mod = 10**9+7

N = int(input())
#X, Y = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(N-1)]

fact = [1, 1] # 元テーブル
fact_inv = [1, 1] # 逆元テーブル
tmp_inv = [0, 1] # 逆元テーブル計算用テーブル
for i in range(2, N+1):
    fact.append((fact[-1] * i) % mod)
    tmp_inv.append((-tmp_inv[mod % i] * (mod//i)) % mod)
    fact_inv.append((fact_inv[-1] * tmp_inv[-1]) % mod)
def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return fact[n] * fact_inv[r] * fact_inv[n-r] % mod
#逆元作成
def inv(a,mod):
    return pow(a,mod-2,mod)

graph = [[] for _ in range(N+1)]
for a, b in ab:
    graph[a].append(b)
    graph[b].append(a)

dp = [1] * (N + 1)
size = [0] * (N + 1)
def dfs(par, v):
    for u in graph[v]:
        if par == u:
            continue
        dfs(v, u)
        size[v] += size[u]
        dp[v] = dp[v] * dp[u] * fact_inv[size[u]] % mod
    dp[v] = dp[v] * fact[size[v]] % mod
    size[v] += 1

ans = [0] * (N + 1)
def reroot(par, val_par, size_par, v):
    ans[v] = val_par * dp[v] * cmb(N-1, size_par, mod) % mod
    for u in graph[v]:
        if par == u:
            continue
        val = ans[v] * inv(dp[u] * cmb(N-1, size[u],mod),mod) % mod
        reroot(v, val, N - size[u], u)

dfs(-1,1)
reroot(-1,1,0,1)
for i in range(1,N+1):
    print(ans[i])

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

    # 頂点iについて、jが根のときのDPの値を求める（アクセス時間を考慮してここで定義）
    def calc(i, j):
        root = tree_d[i][j]+1
        try:
            return tc_l[i][root-1]+tc_r[i][root]
        except:
            return tc_l[i][root-1]

    def calc2(i, j):
        root = tree_d[i][j]+1
        try:
            return tc_l2[i][root-1]*tc_r2[i][root] *\
                nCr(tc_l[i][root-1]+tc_r[i]
                    [root], tc_l[i][root-1]) % mod
        except:
            return tc_l2[i][root-1]

    tree = g
    size = len(tree)
    dp, dp2, order, q, anc = [0]*size, [1]*size, [], [0], [-1]*n
    oa, qa, qp = order.append, q.append, q.pop
    tree_d = [{k: j for j, k in enumerate(i)} for i in g]
    g_size = [len(i) for i in g]
    tc_l = [[0]*(i+1) for i in g_size]
    tc_r = [[0]*i for i in g_size]
    tc_l2 = [[1]*(i+1) for i in g_size]
    tc_r2 = [[1]*i for i in g_size]

    # トポロジカル順序をorderに記録、0を根とする根付き木上のiの祖先をanc[i]とする
    while q:
        i = qp()
        a = anc[i]
        oa(i)
        for j in g[i]:
            if j != a:
                qa(j)
                anc[j] = i

    # dpおよびtree_preに記録
    for i in order[:0:-1]:
        a = anc[i]
        t = tree_d[a][i]
        d = dp2[i]
        tc_l2[a][t+1], tc_r2[a][t] = d, d
        d = dp[i]+1
        tc_l[a][t+1], tc_r[a][t], dp[a] = d, d, dp[a]+d
        dp2[a] = dp2[a]*dp2[i]*nCr(dp[a], dp[i]+1) % mod

    # 頂点0のみ先に処理
    ans = 0
    for j in range(1, g_size[0]+1):
        tc_l[0][j] = tc_l[0][j]+tc_l[0][j-1]
        tc_l2[0][j] = tc_l2[0][j]*tc_l2[0][j-1] * \
            nCr(tc_l[0][j], tc_l[0][j-1]) % mod
    for j in range(g_size[0]-2, 0, -1):
        tc_r[0][j] = tc_r[0][j]+tc_r[0][j+1]
        tc_r2[0][j] = tc_r2[0][j]*tc_r2[0][j+1] * \
            nCr(tc_r[0][j], tc_r[0][j+1]) % mod

    # 行きがけ順に処理
    for i in order[1:]:
        a = anc[i]
        d, c, c2, length = tree_d[i][a], calc(
            a, i)+1, calc2(a, i), g_size[i]

        tc_l[i][d+1], tc_r[i][d] = c, c
        tc_l2[i][d+1], tc_r2[i][d] = c2, c2

        for j in range(1, length+1):
            tc_l[i][j] = tc_l[i][j]+tc_l[i][j-1]
            tc_l2[i][j] = tc_l2[i][j]*tc_l2[i][j-1] * \
                nCr(tc_l[i][j], tc_l[i][j-1]) % mod
        for j in range(length-2, 0, -1):
            tc_r[i][j] = tc_r[i][j+1]+tc_r[i][j]
            tc_r2[i][j] = tc_r2[i][j]*tc_r2[i][j+1] * \
                nCr(tc_r[i][j], tc_r[i][j+1]) % mod
        dp[i] = tc_l[i][-1]
        dp2[i] = tc_l2[i][-1]
    for i in dp2:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():

    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    #from time import time
    #n = 200000
    #import random
    # random.seed(0)

    # def sample_tree(n):  # n頂点の連結グラフを出力する
    #    l = [random.randrange(0, i+1) for i in range(n-1)]  # 親を指定する
    #    d = {i: j for i, j in enumerate(random.sample(range(n), n))}  # シャッフル
    #    xy = sorted([sorted([d[j]+1, d[i+1]+1])
    #                 for i, j in enumerate(l)])  # グラフを作成
    #    return xy
    #ab = sample_tree(n)

    #t = -time()

    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 rerooting():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # 頂点iについて、jが根のときのDPの値を求める（アクセス時間を考慮してここで定義）
            def calc(i, j):
                root = tree_d[i][j]+1
                try:
                    return tc_l[i][root-1]+tc_r[i][root]
                except:
                    return tc_l[i][root-1]

            def calc2(i, j):
                root = tree_d[i][j]+1
                try:
                    return tc_l2[i][root-1]*tc_r2[i][root] *\
                        nCr(tc_l[i][root-1]+tc_r[i]
                            [root], tc_l[i][root-1]) % mod
                except:
                    return tc_l2[i][root-1]

            size = len(tree)
            dp, dp2, order, q, anc = [ini]*size, [1]*size, [], [0], [-1]*n
            oa, qa, qp = order.append, q.append, q.pop
            tree_d = [{k: j for j, k in enumerate(i)} for i in g]
            g_size = [len(i) for i in g]
            tc_l = [[ini]*(i+1) for i in g_size]
            tc_r = [[ini]*i for i in g_size]
            tc_l2 = [[1]*(i+1) for i in g_size]
            tc_r2 = [[1]*i for i in g_size]

            # トポロジカル順序をorderに記録、0を根とする根付き木上のiの祖先をanc[i]とする
            while q:
                i = qp()
                a = anc[i]
                oa(i)
                for j in g[i]:
                    if j != a:
                        qa(j)
                        anc[j] = i

            # dpおよびtree_preに記録
            for i in order[:0:-1]:
                a = anc[i]
                t = tree_d[a][i]
                d = dp2[i]
                tc_l2[a][t+1], tc_r2[a][t] = d, d
                d = dp[i]+1
                tc_l[a][t+1], tc_r[a][t], dp[a] = d, d, dp[a]+d
                dp2[a] = dp2[a]*dp2[i]*nCr(dp[a], dp[i]+1) % mod

            # 頂点0のみ先に処理
            ans = 0
            for j in range(1, g_size[0]+1):
                tc_l[0][j] = tc_l[0][j]+tc_l[0][j-1]
                tc_l2[0][j] = tc_l2[0][j]*tc_l2[0][j-1] * \
                    nCr(tc_l[0][j], tc_l[0][j-1]) % mod
            for j in range(g_size[0]-2, 0, -1):
                tc_r[0][j] = tc_r[0][j]+tc_r[0][j+1]
                tc_r2[0][j] = tc_r2[0][j]*tc_r2[0][j+1] * \
                    nCr(tc_r[0][j], tc_r[0][j+1]) % mod

            # 行きがけ順に処理
            for i in order[1:]:
                a = anc[i]
                d, c, c2, length = tree_d[i][a], calc(
                    a, i)+1, calc2(a, i), g_size[i]

                tc_l[i][d+1], tc_r[i][d] = c, c
                tc_l2[i][d+1], tc_r2[i][d] = c2, c2

                for j in range(1, length+1):
                    tc_l[i][j] = tc_l[i][j]+tc_l[i][j-1]
                    tc_l2[i][j] = tc_l2[i][j]*tc_l2[i][j-1] * \
                        nCr(tc_l[i][j], tc_l[i][j-1]) % mod
                for j in range(length-2, 0, -1):
                    tc_r[i][j] = tc_r[i][j+1]+tc_r[i][j]
                    tc_r2[i][j] = tc_r2[i][j]*tc_r2[i][j+1] * \
                        nCr(tc_r[i][j], tc_r[i][j+1]) % mod
                dp[i] = tc_l[i][-1]
                dp2[i] = tc_l2[i][-1]
            for i in dp2:
                print(i)
    rerooting(g, 0)


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 rerooting():
        # addは頂点iに頂点jを根とする部分木（DPの値：x）をくっつけるときの補正
        def __init__(self, tree, ini):
            # 頂点iについて、jが根のときのDPの値を求める（アクセス時間を考慮してここで定義）
            def add(i, j, x):
                return x+1

            def monoid(i, j):
                return i+j

            def monoid2(i, j):
                return i*j % mod

            def calc(i, j):
                root = tree_d[i][j]+1
                try:
                    return monoid(tc_l[i][root-1], tc_r[i][root])
                except:
                    return tc_l[i][root-1]

            def calc2(i, j):
                root = tree_d[i][j]+1
                try:
                    return monoid2(tc_l2[i][root-1], tc_r2[i][root]) *\
                        nCr(tc_l[i][root-1]+tc_r[i][root], tc_l[i][root-1])
                except:
                    return tc_l2[i][root-1]

            size = len(tree)
            dp, dp2, order, q, anc = [ini]*size, [1]*size, [], [0], [-1]*n
            oa, qa, qp = order.append, q.append, q.pop
            tree_d = [{k: j for j, k in enumerate(i)} for i in g]
            g_size = [len(i) for i in g]
            tc_l = [[ini]*(i+1) for i in g_size]
            tc_r = [[ini]*i for i in g_size]
            tc_l2 = [[1]*(i+1) for i in g_size]
            tc_r2 = [[1]*i for i in g_size]

            # トポロジカル順序をorderに記録、0を根とする根付き木上のiの祖先をanc[i]とする
            while q:
                i = qp()
                a = anc[i]
                oa(i)
                for j in g[i]:
                    if j != a:
                        qa(j)
                        anc[j] = i

            # dpおよびtree_preに記録
            for i in order[:0:-1]:
                a = anc[i]
                t = tree_d[a][i]
                d = dp2[i]
                tc_l2[a][t+1], tc_r2[a][t] = d, d
                d = add(a, i, dp[i])
                tc_l[a][t+1], tc_r[a][t], dp[a] = d, d, monoid(dp[a], d)
                dp2[a] = dp2[a]*dp2[i]*nCr(dp[a], dp[i]+1) % mod

            # 頂点0のみ先に処理
            for j in range(1, g_size[0]+1):
                tc_l[0][j] = monoid(tc_l[0][j], tc_l[0][j-1])
                tc_l2[0][j] = tc_l2[0][j]*tc_l2[0][j-1] * \
                    nCr(tc_l[0][j], tc_l[0][j-1]) % mod
            for j in range(g_size[0]-2, 0, -1):
                tc_r[0][j] = monoid(tc_r[0][j], tc_r[0][j+1])
                tc_r2[0][j] = tc_r2[0][j]*tc_r2[0][j+1] * \
                    nCr(tc_r[0][j], tc_r[0][j+1]) % mod

            # 行きがけ順に処理
            for i in order[1:]:
                a = anc[i]
                d, c, c2, length = tree_d[i][a], add(
                    a, i, calc(a, i)), calc2(a, i), g_size[i]

                tc_l[i][d+1], tc_r[i][d] = c, c
                tc_l2[i][d+1], tc_r2[i][d] = c2, c2

                for j in range(1, length+1):
                    tc_l[i][j] = monoid(tc_l[i][j], tc_l[i][j-1])
                    tc_l2[i][j] = tc_l2[i][j]*tc_l2[i][j-1] * \
                        nCr(tc_l[i][j], tc_l[i][j-1]) % mod
                for j in range(length-2, 0, -1):
                    tc_r[i][j] = monoid(tc_r[i][j+1], tc_r[i][j])
                    tc_r2[i][j] = tc_r2[i][j]*tc_r2[i][j+1] * \
                        nCr(tc_r[i][j], tc_r[i][j+1]) % mod
                dp[i] = tc_l[i][-1]
                dp2[i] = tc_l2[i][-1]

            # アトリビュートに格納
            for i in dp2:
                print(i)

    rerooting(g, 0)


main()

Submission status: Time Limit Exceeded

Solution code:
# 全方位DP
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**6)
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 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(num, par=-1):
    res = 1
    for node in edges[num]:
        if node == par:
            continue
        else:
            res += dfs1(node, num)
    res %= MOD
    size[num] = 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)]
inv_1 = fact.fact_inv(fact.fact[n-1])
def dfs3(num, par=-1):
    if par != -1:
        res = dp[num] * fact.fact_inv(fact.fact[size[num] - 1]) * \
            fact.fact[n-1] * ans[par] * inv_1 * \
            fact.fact[n-size[num]-1] * fact.fact[size[num]] * \
            fact.fact_inv(dp[num]) * \
            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:
# 全方位DP
import sys
input = lambda: sys.stdin.buffer.readline()
sys.setrecursionlimit(10**6)
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 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(num, par=-1):
    res = 1
    for node in edges[num]:
        if node == par:
            continue
        else:
            res += dfs1(node, num)
    res %= MOD
    size[num] = 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)]
inv_1 = fact.fact_inv(fact.fact[n-1])
def dfs3(num, par=-1):
    if par != -1:
        res = dp[num] * fact.fact_inv(fact.fact[size[num] - 1]) * \
            fact.fact[n-1] * ans[par] * inv_1 * \
            fact.fact[n-size[num]-1] * fact.fact[size[num]] * \
            fact.fact_inv(dp[num]) * \
            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:
# 全方位DP
import sys
input = lambda: sys.stdin.buffer.readline().rstrip()
sys.setrecursionlimit(10**6)
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 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(num, par=-1):
    res = 1
    for node in edges[num]:
        if node == par:
            continue
        else:
            res += dfs1(node, num)
    res %= MOD
    size[num] = 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)]
inv_1 = fact.fact_inv(fact.fact[n-1])
def dfs3(num, par=-1):
    if par != -1:
        res = dp[num] * fact.fact_inv(fact.fact[size[num] - 1]) * \
            fact.fact[n-1] * ans[par] * inv_1 * \
            fact.fact[n-size[num]-1] * fact.fact[size[num]] * \
            fact.fact_inv(dp[num]) * \
            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

F = 2*10**5
mod = 10**9+7
fact = [1]*F
inv = [1]*F
for i in range(2,F):
    fact[i]=(fact[i-1]*i)%mod
inv[F-1]=pow(fact[F-1],mod-2,mod)
for i in range(F-2,1,-1):
    inv[i] = (inv[i+1]*(i+1))%mod

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

stack=[0]
order=[0]
parent=[0]*n
while stack:
    node = stack.pop()
    for child in neighbers[node]:
        if child==parent[node]:
            continue
        stack.append(child)
        order.append(child)
        parent[child]=node

# (size,combination)
upinfo=[(0,1)]*n
downinfo=[(0,1)]*n

for node in order[::-1]:
    if len(neighbers[node])==1:
        downinfo[node]=(1,1)
    else:
        totalsize=0
        totalcomb=1
        for child in neighbers[node]:
            if child == parent[node]:
                continue
            size,comb=downinfo[child]
            totalsize+=size
            totalcomb=(totalcomb*comb)%mod
            totalcomb=(totalcomb*inv[size])%mod
        totalcomb=(totalcomb*fact[totalsize])%mod
        downinfo[node]=(totalsize+1,totalcomb)
for node in order[1:]:
    totalsize=0
    totalcomb=1
    for brother in neighbers[parent[node]]:
        if brother == node:
            continue
        size,comb=upinfo[parent[node]] if brother == parent[parent[node]] else downinfo[brother]
        totalsize+=size
        totalcomb=(totalcomb*comb)%mod
        totalcomb=(totalcomb*inv[size])%mod
    totalcomb=(totalcomb*fact[totalsize])%mod
    upinfo[node]=(totalsize+1,totalcomb)
for node in range(n):
    totalsize=0
    totalcomb=1
    for child in neighbers[node]:
        size,comb=upinfo[node] if child==parent[node] else downinfo[child]
        totalsize+=size
        totalcomb=(totalcomb*comb)%mod
        totalcomb=(totalcomb*inv[size])%mod
    totalcomb=(totalcomb*fact[totalsize])%mod
    print(totalcomb)

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy
from functools import lru_cache
sys.setrecursionlimit(10**6)

def main():
    #node i is list of [child,size,comb] connected i
    #return [size,comb]
    @lru_cache(maxsize=1000000)
    def deep(i,parent):
        if len(node[i])==1 and parent!=-1:
            return (1,1)
        mysize=0
        mycomb=1
        for j in node[i]:
            if j!=parent:
                size,comb=deep(j,i)
                mysize+=size
                mycomb=(mycomb*comb)%mod
                mycomb=(mycomb*inv[size])%mod
        mycomb=(mycomb*fact[mysize])%mod
        return (mysize+1,mycomb)

    F = 2*10**5
    mod = 10**9+7
    fact = [1]*F
    inv = [1]*F
    for i in range(2,F):
        fact[i]=(fact[i-1]*i)%mod
    inv[F-1]=pow(fact[F-1],mod-2,mod)
    for i in range(F-2,1,-1):
        inv[i] = (inv[i+1]*(i+1))%mod
    
    n=int(input())
    node=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        node[a-1].append(b-1)
        node[b-1].append(a-1)
    for i in range(n):
        print(deep(i,-1)[1])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy
from functools import lru_cache
sys.setrecursionlimit(10**6)

def main():
    # input and preparation
    F = 2*10**5
    mod = 10**9+7
    fact = [1]*F
    inv = [1]*F
    for i in range(2,F):
        fact[i]=(fact[i-1]*i)%mod
    inv[F-1]=pow(fact[F-1],mod-2,mod)
    for i in range(F-2,1,-1):
        inv[i] = (inv[i+1]*(i+1))%mod
    n=int(input())
    node=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        node[a-1].append(b-1)
        node[b-1].append(a-1)
    
    memo=[[0]*n for i in range(n)]

    # node i is list of [child,size,comb] connected i
    # return [size,comb]
    def deep(i,parent):
        if len(node[i])==1 and parent!=-1:
            return [1,1]
        mysize=0
        mycomb=1
        for j in node[i]:
            if j!=parent:
                size,comb=memo[j][i] if memo[j][i] != 0 else deep(j,i)
                mysize+=size
                mycomb=(mycomb*comb)%mod
                mycomb=(mycomb*inv[size])%mod
        mycomb=(mycomb*fact[mysize])%mod
        if parent!=-1:
            memo[i][parent]=(mysize+1,mycomb)
        return (mysize+1,mycomb)
    
    for i in range(n):
        print(deep(i,-1)[1])

main()

Submission status: Time Limit Exceeded

Solution code:
import sys
from copy import deepcopy
from functools import lru_cache
sys.setrecursionlimit(10**6)

def main():
    #node i is list of [child,size,comb] connected i
    #return [size,comb]
    @lru_cache(maxsize=1000000)
    def deep(i,parent):
        if len(node[i])==1 and parent!=-1:
            return [1,1]
        mysize=0
        mycomb=1
        for j in node[i]:
            if j!=parent:
                size,comb=deep(j,i)
                mysize+=size
                mycomb=(mycomb*comb)%mod
                mycomb=(mycomb*inv[size])%mod
        mycomb=(mycomb*fact[mysize])%mod
        return (mysize+1,mycomb)

    F = 2*10**5
    mod = 10**9+7
    fact = [1]*F
    inv = [1]*F
    for i in range(2,F):
        fact[i]=(fact[i-1]*i)%mod
    inv[F-1]=pow(fact[F-1],mod-2,mod)
    for i in range(F-2,1,-1):
        inv[i] = (inv[i+1]*(i+1))%mod
    
    n=int(input())
    node=[[] for i in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        node[a-1].append(b-1)
        node[b-1].append(a-1)
    for i in range(n):
        print(deep(i,-1)[1])

main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
mod = 10**9 + 7
N = int(input())

fac = [1]*(N+1)
inv_fac = [1] *(N+1)
for i in range(1,N+1):
    fac[i] = (fac[i-1]*i)%mod
    inv_fac[i] = (inv_fac[i-1] * pow(i,mod-2,mod))%mod

#print(fac[:10])
#print(inv_fac[:10])

def merge(P,Q):
    R = [0,0]
    R[0] = (P[0]*Q[0]*fac[P[1]+Q[1]]*inv_fac[P[1]]*inv_fac[Q[1]])%mod
    R[1] = P[1]+Q[1]###部分木の親を含まない頂点数
    return R


tree = [[] for i in range(N)]
num = [[] for i in range(N)]
###iのj番目隣接点にとって, iが何番目の隣接点か(0-indexed)

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

stack = deque([0])
visit = [0]*N
order = [0]###DFSで訪問した順に頂点番号を格納
visit[0] = 1
par = [-1]*N###親番号の格納

while stack:
    x = stack.pop()
    for y in tree[x]:
        if visit[y] == 1:
            continue
        visit[y] = 1
        par[y] = x
        order.append(y)
        stack.append(y)

data = [[[1,0] for j in range(len(tree[i]))] for i in range(N)]
###葉ノードだけからなる部分木の色の塗り方は1通りなので
###これを初期値にする
###第２要素にはiを親, tree[i][j]を根とする部分木の
###サイズを保持する

for i in range(1,N):
    ###ノード0には親がないので調べなくて良い
    result = [1,0]###部分木の根を含んだノードの数
    x = order[-i]###見るノード
    for j in range(len(tree[x])):
        if tree[x][j] == par[x]:
            par_idx = j###親のインデックス
        else:###=j番目の隣接ノードが子の場合
            result = merge(result,data[x][j])
    data[par[x]][num[x][par_idx]][0] = result[0]
    data[par[x]][num[x][par_idx]][1] = result[1]+1###部分木の親自身

###
#print("STEP1")
#print("tree",tree)
#print("par",par)
#print("data",data)
#print("order",order)
#print("STEP2")
###

ans = [0]*N
for i in range(N):
    x = order[i]###見るノード(部分木の値は全てわかっている)
    if x!=0 and len(tree[x]) == 1:###隣接点が親しかいない
        ans[x] = data[x][0][0]
        continue
    if x == 0 and len(tree[0]) == 1:
        data[tree[0][0]][num[0][0]] = [1,1]
        ans[0] = data[0][0][0]
        continue
    back_acc = [[1,0] for i in range(len(tree[x]))]###後ろからの累積
    ###0:dp[u]/size(u)!%mod
    ###1:部分木の総頂点数

    for j in range(1,len(tree[x])):
        back_acc[-j] = merge(back_acc[-j+1],data[x][-j])
        ###
        #print("x:",x,"j:",j,"back:",back_acc)
        ###

    data[tree[x][0]][num[x][0]] = [back_acc[1][0],back_acc[1][1]+1]

    for_acc = [1,0]

    for j in range(len(tree[x])-2):
        for_acc = merge(for_acc,data[x][j])
        data[tree[x][j+1]][num[x][j+1]] = merge(for_acc,back_acc[j+2])
        data[tree[x][j+1]][num[x][j+1]][1] += 1
    
    for_acc = merge(for_acc,data[x][len(tree[x])-2])
    data[tree[x][len(tree[x])-1]][num[x][len(tree[x])-1]]\
        = [for_acc[0],for_acc[1]+1]

    for_acc = merge(for_acc,data[x][len(tree[x])-1])
    ans[x] = for_acc[0]###最後まで累積したものがノードxの答え

    ###
    #print("for",for_acc)
    #print("back",back_acc)
    #print("data",data)
    ###


for i in range(N):
    print(ans[i])