Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i.
For each k=1, ..., N, solve the problem below:

Consider writing a number on each vertex in the tree in the following manner:

First, write 1 on Vertex k.

Then, for each of the numbers 2, ..., N in this order, write the number on the vertex chosen as follows:

Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.

Find the number of ways in which we can write the numbers on the vertices, modulo (10^9+7).

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq a_i,b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

For each k=1, 2, ..., N in this order, print a line containing the answer to the problem.

Sample Input 1

3
1 2
1 3

Sample Output 1

2
1
1

The graph in this input is as follows:

For k=1, there are two ways in which we can write the numbers on the vertices, as follows:

Writing 1, 2, 3 on Vertex 1, 2, 3, respectively

Writing 1, 3, 2 on Vertex 1, 2, 3, respectively

Sample Input 2

2
1 2

Sample Output 2

1
1

The graph in this input is as follows:

Sample Input 3

5
1 2
2 3
3 4
3 5

Sample Output 3

2
8
12
3
3

The graph in this input is as follows:

Sample Input 4

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8

Sample Output 4

40
280
840
120
120
504
72
72

The graph in this input is as follows:



Sample input:
3
1 2
1 3


Sample output:
2
1
1

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
p = 1000000007  #ここを変える
def powmod(a, n):
    global p
    n_b = str(format(n, "b"))  # 2進表現に
    res = 1
    for bit in n_b:
        res = (res * res) % p
        if bit == "1":
            res = (res * a) % p
    return res
def invmod(n):
    return powmod(n, p - 2)
def cmod(n, r):
    global p
    if r > n // 2:
        return cmod(n, n - r)
    def mulmod(x, y):
        global p
        return x * y % p
    return reduce(mulmod, range(n - r + 1, n + 1), 1) * invmod(reduce(mulmod, range(1, r + 1), 1))

n = int(input())
adj_of = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    adj_of[a - 1].append(b - 1)
    adj_of[b - 1].append(a - 1)
stack = [(0, -1)] # root, excludee
course = []
while len(stack) > 0:
    popped = stack.pop()
    course.append(popped)
    for adj in adj_of[popped[0]]:
        if adj != popped[1]:
            stack.append((adj, popped[0]))
sizes = [{} for _ in range(n)] #size, pattern_num
pattern_nums = [{} for _ in range(n)]
for step in reversed(course):
    size = 1
    pattern_num = 1
    for adj in adj_of[step[0]]:
        if adj != step[1]:
            size += sizes[adj][step[0]]
            pattern_num *= pattern_nums[adj][step[0]] * cmod(size - 1, sizes[adj][step[0]])
            pattern_num %= p
    sizes[step[0]][step[1]] = size
    pattern_nums[step[0]][step[1]] = pattern_num

#print(course)
#print(sizes)
#print(pattern_nums)

ans = [None] * n
for step in course:
    if step[0] == 0:
        ans[0] = pattern_nums[0][-1]
        continue
    #ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums[step[1]][step[0]]\
    #             * cmod(sizes[step[0]][step[1]] + sizes[step[1]][step[0]], sizes[step[0]][step[1]]) % p
    pattern_nums_step1_step0 = ans[step[1]] * invmod(cmod(n - 1, sizes[step[0]][step[1]]) * pattern_nums[step[0]][step[1]]) % p
    ans[step[0]] = pattern_nums[step[0]][step[1]] * pattern_nums_step1_step0\
                 * cmod(n - 1, sizes[step[0]][step[1]] - 1) % p

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

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

    n = int(input())

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

    mod = 10 ** 9 + 7
    N = n + 1

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

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

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

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

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]
    
    def preprocess():
        for i in range(n):
            ns = []
            cnt = 1
            cnts = []
            l = [1]
            r = [1]
            cnts_append = cnts.append
            ns_append = ns.append
            l_append = l.append
            r_append = r.append
            downi = down[i]
            downmuli = down_mul[i]
            for e in downi:
                ni, cnti = downi[e]
                ns_append(ni)
                cnts_append(cnti)
            for j in range(len(cnts)):
                l_append(l[-1] * cnts[j] % mod)
                r_append(r[-1] * cnts[-j-1] % mod)
            for j, e in enumerate(downi):
                if len(r) >= 2:
                    downmuli[e] = l[j] * r[-j-2] % mod
                else:
                    downmuli[e] = 1

            s = sum(ns)
            S = s
            for ni in ns:
                cnt = cnt * cmb(s, ni) % mod
                s -= ni
            down_sum[i] = [S, cnt, l[-1]]
    
    def dfs_up_preprocess(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ni = 0
                cnt = 1
                if up[pre]:
                    ni, cnt = up[pre]
                # 自分以外の子について計算
                # あらかじめ積をとっておけば、毎回for 文回さなくて良い
                n_cur, cnt_cur = down[pre][cur]
                n_sum, cnt_sum, _ = down_sum[pre]
                cnt = cnt * down_mul[pre][cur] % mod
                cnt = cnt * cnt_sum % mod
                cnt = cnt * kai[n_sum - n_cur] % mod
                cnt = cnt * kai[n_cur] % mod
                cnt = cnt * rev_kai[n_sum] % mod
                cnt = cnt * cmb(n_sum-n_cur+ni, ni) % mod
                s = n_sum-n_cur+ni

                up[cur] = [s+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])

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


    if n < 10000:
        dfs_down(0, n)
        preprocess()
        dfs_up_preprocess(0, n)


        for i in range(n):
            ni = 0
            cnt = 1
            if up[i]:
                ni, cnt = up[i]
            n_sum, cnt_sum, cnt_all = down_sum[i]
            cnt = cnt * cnt_sum % mod
            cnt = cnt * cnt_all % mod
            cnt = cnt * cmb(n_sum + ni, ni) % mod
            print(cnt)
    else:
        
        dfs_down(0, n)
        dfs_up(0, n)


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    n = int(input())

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

    mod = 10 ** 9 + 7
    N = n + 1

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

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

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

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

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]
    
    def preprocess():
        for i in range(n):
            ns = []
            cnt = 1
            cnts = []
            l = [1]
            r = [1]
            cnts_append = cnts.append
            ns_append = ns.append
            l_append = l.append
            r_append = r.append
            downi = down[i]
            downmuli = down_mul[i]
            for e in downi:
                ni, cnti = downi[e]
                ns_append(ni)
                cnts_append(cnti)
            for j in range(len(cnts)):
                l_append(l[-1] * cnts[j] % mod)
                r_append(r[-1] * cnts[-j-1] % mod)
            for j, e in enumerate(downi):
                if len(r) >= 2:
                    downmuli[e] = l[j] * r[-j-2] % mod
                else:
                    downmuli[e] = 1

            s = sum(ns)
            S = s
            for ni in ns:
                cnt = cnt * cmb(s, ni) % mod
                s -= ni
            down_sum[i] = [S, cnt, l[-1]]
    
    def dfs_up_preprocess(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ni = 0
                cnt = 1
                if up[pre]:
                    ni, cnt = up[pre]
                # 自分以外の子について計算
                # あらかじめ積をとっておけば、毎回for 文回さなくて良い
                n_cur, cnt_cur = down[pre][cur]
                n_sum, cnt_sum, _ = down_sum[pre]
                cnt = cnt * down_mul[pre][cur] % mod
                cnt = cnt * cnt_sum % mod
                cnt = cnt * kai[n_sum - n_cur] % mod
                cnt = cnt * kai[n_cur] % mod
                cnt = cnt * rev_kai[n_sum] % mod
                cnt = cnt * cmb(n_sum-n_cur+ni, ni) % mod
                s = n_sum-n_cur+ni

                up[cur] = [s+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])

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


    if n > 10000:
        dfs_down(0, n)
        preprocess()
        dfs_up_preprocess(0, n)


        for i in range(n):
            ni = 0
            cnt = 1
            if up[i]:
                ni, cnt = up[i]
            n_sum, cnt_sum, cnt_all = down_sum[i]
            cnt = cnt * cnt_sum % mod
            cnt = cnt * cnt_all % mod
            cnt = cnt * cmb(n_sum + ni, ni) % mod
            print(cnt)
    else:
        
        dfs_down(0, n)
        dfs_up(0, n)


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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    n = int(input())

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

    mod = 10 ** 9 + 7
    N = n + 1

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

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

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

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

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]
    
    def preprocess():
        for i in range(n):
            ns = []
            cnt = 1
            cnts = []
            l = [1]
            r = [1]
            cnts_append = cnts.append
            ns_append = ns.append
            l_append = l.append
            r_append = r.append
            downi = down[i]
            downmuli = down_mul[i]
            for e in downi:
                ni, cnti = downi[e]
                ns_append(ni)
                cnts_append(cnti)
            for j in range(len(cnts)):
                l_append(l[-1] * cnts[j] % mod)
                r_append(r[-1] * cnts[-j-1] % mod)
            for j, e in enumerate(downi):
                if len(r) >= 2:
                    downmuli[e] = l[j] * r[-j-2] % mod
                else:
                    downmuli[e] = 1

            s = sum(ns)
            S = s
            for ni in ns:
                cnt = cnt * cmb(s, ni) % mod
                s -= ni
            down_sum[i] = [S, cnt, l[-1]]
    
    def dfs_up(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ni = 0
                cnt = 1
                if up[pre]:
                    ni, cnt = up[pre]
                # 自分以外の子について計算
                # あらかじめ積をとっておけば、毎回for 文回さなくて良い
                n_cur, cnt_cur = down[pre][cur]
                n_sum, cnt_sum, _ = down_sum[pre]
                cnt = cnt * down_mul[pre][cur] % mod
                cnt = cnt * cnt_sum % mod
                cnt = cnt * kai[n_sum - n_cur] % mod
                cnt = cnt * kai[n_cur] % mod
                cnt = cnt * rev_kai[n_sum] % mod
                cnt = cnt * cmb(n_sum-n_cur+ni, ni) % mod
                s = n_sum-n_cur+ni

                up[cur] = [s+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])


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


    for i in range(n):
        ni = 0
        cnt = 1
        if up[i]:
            ni, cnt = up[i]
        n_sum, cnt_sum, cnt_all = down_sum[i]
        cnt = cnt * cnt_sum % mod
        cnt = cnt * cnt_all % mod
        cnt = cnt * cmb(n_sum + ni, ni) % mod
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    n = int(input())

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

    mod = 10 ** 9 + 7
    N = n + 1

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

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

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

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

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]
    
    def preprocess():
        for i in range(n):
            ns = []
            cnt = 1
            cnts = []
            l = [1]
            r = [1]
            cnts_append = cnts.append
            ns_append = ns.append
            l_append = l.append
            r_append = r.append
            for e in down[i]:
                ni, cnti = down[i][e]
                ns_append(ni)
                cnts_append(cnti)
            for j in range(len(cnts)):
                l_append(l[-1] * cnts[j] % mod)
                r_append(r[-1] * cnts[-j-1] % mod)
            for j, e in enumerate(down[i]):
                if len(r) >= 2:
                    down_mul[i][e] = l[j] * r[-j-2] % mod
                else:
                    down_mul[i][e] = 1

            s = sum(ns)
            S = s
            for ni in ns:
                cnt = cnt * cmb(s, ni) % mod
                s -= ni
            down_sum[i] = [S, cnt, l[-1]]
    
    def dfs_up(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ni = 0
                cnt = 1
                if up[pre]:
                    ni, cnt = up[pre]
                # 自分以外の子について計算
                # あらかじめ積をとっておけば、毎回for 文回さなくて良い
                n_cur, cnt_cur = down[pre][cur]
                n_sum, cnt_sum, _ = down_sum[pre]
                cnt = cnt * down_mul[pre][cur] % mod
                cnt = cnt * cnt_sum % mod
                cnt = cnt * kai[n_sum - n_cur] % mod
                cnt = cnt * kai[n_cur] % mod
                cnt = cnt * rev_kai[n_sum] % mod
                cnt = cnt * cmb(n_sum-n_cur+ni, ni) % mod
                s = n_sum-n_cur+ni

                up[cur] = [s+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])


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


    for i in range(n):
        ni = 0
        cnt = 1
        if up[i]:
            ni, cnt = up[i]
        n_sum, cnt_sum, cnt_all = down_sum[i]
        cnt = cnt * cnt_sum % mod
        cnt = cnt * cnt_all % mod
        cnt = cnt * cmb(n_sum + ni, ni) % mod
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    n = int(input())

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

    mod = 10 ** 9 + 7
    N = n + 1

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

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

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

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

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]
    
    def preprocess():
        for i in range(n):
            ns = []
            cnt = 1
            cnts = []
            l = [1]
            r = [1]
            for e in down[i]:
                ni, cnti = down[i][e]
                ns.append(ni)
                cnts.append(cnti)
            for j in range(len(cnts)):
                l.append(l[-1] * cnts[j] % mod)
                r.append(r[-1] * cnts[-j-1] % mod)
            for j, e in enumerate(down[i]):
                if len(r) >= 2:
                    down_mul[i][e] = l[j] * r[-j-2] % mod
                else:
                    down_mul[i][e] = 1

            s = sum(ns)
            S = s
            for ni in ns:
                cnt = cnt * cmb(s, ni) % mod
                s -= ni
            down_sum[i] = [S, cnt, l[-1]]
    
    def dfs_up(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ni = 0
                cnt = 1
                if up[pre]:
                    ni, cnt = up[pre]
                # 自分以外の子について計算
                # あらかじめ積をとっておけば、毎回for 文回さなくて良い
                n_cur, cnt_cur = down[pre][cur]
                n_sum, cnt_sum, _ = down_sum[pre]
                cnt = cnt * down_mul[pre][cur] % mod
                cnt = cnt * cnt_sum % mod
                cnt = cnt * kai[n_sum - n_cur] % mod
                cnt = cnt * kai[n_cur] % mod
                cnt = cnt * rev_kai[n_sum] % mod
                cnt = cnt * cmb(n_sum-n_cur+ni, ni) % mod
                s = n_sum-n_cur+ni

                up[cur] = [s+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])


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


    for i in range(n):
        ni = 0
        cnt = 1
        if up[i]:
            ni, cnt = up[i]
        n_sum, cnt_sum, cnt_all = down_sum[i]
        cnt = cnt * cnt_sum % mod
        cnt = cnt * cnt_all % mod
        cnt = cnt * cmb(n_sum + ni, ni) % mod
        print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

    n = int(input())

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

    mod = 10 ** 9 + 7
    N = n + 1

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

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

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

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

    def dfs_down(cur, pre):
        if E[cur] == [pre]:
            down[pre][cur] = [1, 1]
        ns = []
        cnt = 1
        ns_append = ns.append
        for e in E[cur]:
            if e != pre:
                if e not in down[cur]:
                    dfs_down(e, cur)
                ni, cnti = down[cur][e]
                ns_append(ni)
                cnt = cnt * cnti % mod
        s = sum(ns)
        S = s
        for ni in ns:
            cnt = cnt * cmb(s, ni) % mod
            s -= ni
        down[pre][cur] = [S+1, cnt]
    
    def preprocess():
        for i in range(n):
            ns = []
            cnt = 1
            cnts = []
            l = [1]
            r = [1]
            for e in down[i]:
                ni, cnti = down[i][e]
                ns.append(ni)
                cnts.append(cnti)
            for j in range(len(cnts)):
                l.append(l[-1] * cnts[j] % mod)
                r.append(r[-1] * cnts[-j-1] % mod)
            for j, e in enumerate(down[i]):
                if len(r) >= 2:
                    down_mul[i][e] = l[j] * r[-j-2] % mod
                else:
                    down_mul[i][e] = 1

            s = sum(ns)
            S = s
            for ni in ns:
                cnt = cnt * cmb(s, ni) % mod
                s -= ni
            down_sum[i] = [S, cnt, l[-1]]
    
    def dfs_up(cur, pre):
        stack = deque([[cur, pre]])
        while stack:
            cur, pre = stack.pop() 
            if cur != 0:
                ni = 0
                cnt = 1
                if up[pre]:
                    ni, cnt = up[pre]
                # 自分以外の子について計算
                # あらかじめ積をとっておけば、毎回for 文回さなくて良い
                n_cur, cnt_cur = down[pre][cur]
                n_sum, cnt_sum, _ = down_sum[pre]
                cnt = cnt * down_mul[pre][cur] % mod
                cnt = cnt * cnt_sum * (kai[n_sum - n_cur] * kai[n_cur] * rev_kai[n_sum]) * cmb(n_sum-n_cur+ni, ni) % mod
                s = n_sum-n_cur+ni

                up[cur] = [s+1, cnt]
            for e in E[cur]:
                if e != pre:
                    stack.append([e, cur])


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


    for i in range(n):
        ni = 0
        cnt = 1
        if up[i]:
            ni, cnt = up[i]
        n_sum, cnt_sum, cnt_all = down_sum[i]
        cnt = cnt * cnt_sum * cnt_all * cmb(n_sum + ni, ni) % mod
        print(cnt)

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, 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
    memo = {}
    f, fi = fact, fact_inv

    stack = [(None, 1)]
    while stack:
        pre, cur = stack.pop()
        dfs(None, cur)

        for nxt in g[cur]:
            if nxt == pre:
                continue
            stack.append((cur, nxt))

    print(*[memo[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()