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:
def ABC67_B():
    N, K = LI()
    L = LI()
    L.sort(reverse=True)
    ans = sum(L[:K])
    print(ans)
    return

def ABC100_C():
    def factorization_2(n):
        arr = defaultdict(int)
        temp = n
        i = 2
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr[2]
    N = I()
    A = LI()
    ans = 0
    for a in A:
        ans += factorization_2(a)
    print(ans)
    return

def ARC68_C():
    X = I()
    ans = 0
    ans += 2*(X//11)
    rest = X%11
    if rest>0:
        ans += 1
    if rest>=7:
        ans += 1
    print(ans)
    return

def ABC49_C():
    S = SI()
    T = {"maerd","remaerd","esare","resare"}
    stack = ""
    for s in S[::-1]:
        stack += s
        if stack in T:
            stack = ""
    if stack:
        print("NO")
    else:
        print("YES")
    return

def ABC142_E():
    N, M = LI()
    A = [0]*M
    C = [[]for _ in range(M)]
    for i in range(M):
        A[i], b = LI()
        C[i] = LI()
    mask = 2**N
    dp = [[inf]*mask for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        key = 0
        for j in C[i]:
            key += 2**(j-1)
        #print(key)
        for now in range(mask):
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][now])
            if key|now==now:
                continue
            dp[i+1][now|key] = min(dp[i+1][now|key],dp[i][now]+A[i])
    if dp[M][mask-1]==inf:
        print(-1)
    else:
        ans = dp[M][mask-1]
        print(ans)
    #print(dp)
    return

def ABC160_F():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    C = combination(N,mod)
    children = [-1] * N
    A = [0] * N
    def dfs(s):
        size = 1
        nowchild = []
        cur = 1
        children[s] = 0
        for i in V[s]:
            if children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= mod
        children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= C.comb(rest, k)
            rest -= k
            cur %= mod
        A[s] = cur
        return size, cur

    rep = [0] * N
    def dfs2(s, p):
        cur = 1
        rest = N - 1
        for to in V[s]:
            cur *= A[to]
            cur %= mod
        for to in V[s]:
            cur *= C.comb(rest, children[to])
            rest -= children[to]
            cur %= mod
        rep[s] = cur

        n = len(V[s])
        L = [0] * n; R = [0] * n
        L2 = [0] * n; R2 = [0] * n

        for i, ne in enumerate(V[s]):
            L[i] = R[i] = A[ne] * C.inv[children[ne]] % mod
            L2[i] = R2[i] = children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(V[s]):
            if ne == p:
                continue
            A[s] = 1
            children[s] = 1
            if i > 0:
                A[s] *= L[i - 1]
                A[s] %= mod
                children[s] += L2[i - 1]
            if i + 1 < n:
                A[s] *= R[i + 1]
                A[s] %= mod
                children[s] += R2[i + 1]
            A[s] *= C.fac[N - children[ne] - 1]
            A[s] %= mod
            dfs2(ne, s)
        return

    dfs(0)
    dfs2(0,-1)

    for ans in rep:
        print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160_F()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def ABC67_B():
    N, K = LI()
    L = LI()
    L.sort(reverse=True)
    ans = sum(L[:K])
    print(ans)
    return

def ABC100_C():
    def factorization_2(n):
        arr = defaultdict(int)
        temp = n
        i = 2
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr[2]
    N = I()
    A = LI()
    ans = 0
    for a in A:
        ans += factorization_2(a)
    print(ans)
    return

def ARC68_C():
    X = I()
    ans = 0
    ans += 2*(X//11)
    rest = X%11
    if rest>0:
        ans += 1
    if rest>=7:
        ans += 1
    print(ans)
    return

def ABC49_C():
    S = SI()
    T = {"maerd","remaerd","esare","resare"}
    stack = ""
    for s in S[::-1]:
        stack += s
        if stack in T:
            stack = ""
    if stack:
        print("NO")
    else:
        print("YES")
    return

def ABC142_E():
    N, M = LI()
    A = [0]*M
    C = [[]for _ in range(M)]
    for i in range(M):
        A[i], b = LI()
        C[i] = LI()
    mask = 2**N
    dp = [[inf]*mask for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        key = 0
        for j in C[i]:
            key += 2**(j-1)
        #print(key)
        for now in range(mask):
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][now])
            if key|now==now:
                continue
            dp[i+1][now|key] = min(dp[i+1][now|key],dp[i][now]+A[i])
    if dp[M][mask-1]==inf:
        print(-1)
    else:
        ans = dp[M][mask-1]
        print(ans)
    #print(dp)
    return

def ABC160_F():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    C = combination(N,mod)
    children = [-1] * N
    A = [0] * N
    def dfs(s):
        size = 1
        nowchild = []
        cur = 1
        children[s] = 0
        for i in V[s]:
            if children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= mod
        children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= C.comb(rest, k)
            rest -= k
            cur %= mod
        A[s] = cur
        return size, cur

    rep = [0] * N
    def dfs2(s, p=-1):
        cur = 1
        rest = N - 1
        for to in V[s]:
            cur *= A[to]
            cur %= mod
        for to in V[s]:
            cur *= C.comb(rest, children[to])
            rest -= children[to]
            cur %= mod
        rep[s] = cur

        n = len(V[s])
        L = [0] * n; R = [0] * n
        L2 = [0] * n; R2 = [0] * n

        for i, ne in enumerate(V[s]):
            L[i] = R[i] = A[ne] * C.inv[children[ne]]
            L2[i] = R2[i] = children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(V[s]):
            if ne == p:
                continue
            A[s] = 1
            children[s] = 1
            if i > 0:
                A[s] *= L[i - 1]
                A[s] %= mod
                children[s] += L2[i - 1]
            if i + 1 < n:
                A[s] *= R[i + 1]
                A[s] %= mod
                children[s] += R2[i + 1]
            A[s] *= C.fac[N - children[ne] - 1]
            A[s] %= mod
            dfs2(ne, s)
        return

    dfs(0)
    dfs2(0)

    for ans in rep:
        print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160_F()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def ABC67_B():
    N, K = LI()
    L = LI()
    L.sort(reverse=True)
    ans = sum(L[:K])
    print(ans)
    return

def ABC100_C():
    def factorization_2(n):
        arr = defaultdict(int)
        temp = n
        i = 2
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr[2]
    N = I()
    A = LI()
    ans = 0
    for a in A:
        ans += factorization_2(a)
    print(ans)
    return

def ARC68_C():
    X = I()
    ans = 0
    ans += 2*(X//11)
    rest = X%11
    if rest>0:
        ans += 1
    if rest>=7:
        ans += 1
    print(ans)
    return

def ABC49_C():
    S = SI()
    T = {"maerd","remaerd","esare","resare"}
    stack = ""
    for s in S[::-1]:
        stack += s
        if stack in T:
            stack = ""
    if stack:
        print("NO")
    else:
        print("YES")
    return

def ABC142_E():
    N, M = LI()
    A = [0]*M
    C = [[]for _ in range(M)]
    for i in range(M):
        A[i], b = LI()
        C[i] = LI()
    mask = 2**N
    dp = [[inf]*mask for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        key = 0
        for j in C[i]:
            key += 2**(j-1)
        #print(key)
        for now in range(mask):
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][now])
            if key|now==now:
                continue
            dp[i+1][now|key] = min(dp[i+1][now|key],dp[i][now]+A[i])
    if dp[M][mask-1]==inf:
        print(-1)
    else:
        ans = dp[M][mask-1]
        print(ans)
    #print(dp)
    return

def ABC160_F():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    C = combination(N,mod)
    children = [-1] * N
    A = [0] * N
    def dfs(s):
        size = 1
        nowchild = []
        cur = 1
        children[s] = 0
        for i in V[s]:
            if children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= mod
        children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= C.comb(rest, k)
            rest -= k
            cur %= mod
        A[s] = cur
        return size, cur

    rep = [0] * N
    def dfs2(s, p=-1):
        cur = 1
        rest = N - 1
        for to in V[s]:
            cur *= A[to]
            cur %= mod
        for to in V[s]:
            cur *= C.comb(rest, children[to])
            rest -= children[to]
            cur %= mod
        rep[s] = cur

        n = len(V[s])
        L = [0] * N; R = [0] * N
        L2 = [0] * N; R2 = [0] * N

        for i, ne in enumerate(V[s]):
            L[i] = R[i] = A[ne] * C.inv[children[ne]]
            L2[i] = R2[i] = children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(V[s]):
            if ne == p:
                continue
            A[s] = 1
            children[s] = 1
            if i > 0:
                A[s] *= L[i - 1]
                A[s] %= mod
                children[s] += L2[i - 1]
            if i + 1 < n:
                A[s] *= R[i + 1]
                A[s] %= mod
                children[s] += R2[i + 1]
            A[s] *= C.fac[N - children[ne] - 1]
            A[s] %= mod
            dfs2(ne, s)
        return

    dfs(0)
    dfs2(0)

    for ans in rep:
        print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160_F()

"""

"""

Submission status: Time Limit Exceeded

Solution code:
def ABC67_B():
    N, K = LI()
    L = LI()
    L.sort(reverse=True)
    ans = sum(L[:K])
    print(ans)
    return

def ABC100_C():
    def factorization_2(n):
        arr = defaultdict(int)
        temp = n
        i = 2
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr[i] = cnt
        if temp != 1:
            arr[temp] = 1
        if arr == []:
            arr[n] = 1
        return arr[2]
    N = I()
    A = LI()
    ans = 0
    for a in A:
        ans += factorization_2(a)
    print(ans)
    return

def ARC68_C():
    X = I()
    ans = 0
    ans += 2*(X//11)
    rest = X%11
    if rest>0:
        ans += 1
    if rest>=7:
        ans += 1
    print(ans)
    return

def ABC49_C():
    S = SI()
    T = {"maerd","remaerd","esare","resare"}
    stack = ""
    for s in S[::-1]:
        stack += s
        if stack in T:
            stack = ""
    if stack:
        print("NO")
    else:
        print("YES")
    return

def ABC142_E():
    N, M = LI()
    A = [0]*M
    C = [[]for _ in range(M)]
    for i in range(M):
        A[i], b = LI()
        C[i] = LI()
    mask = 2**N
    dp = [[inf]*mask for _ in range(M+1)]
    dp[0][0] = 0
    for i in range(M):
        key = 0
        for j in C[i]:
            key += 2**(j-1)
        #print(key)
        for now in range(mask):
            dp[i + 1][now] = min(dp[i + 1][now], dp[i][now])
            if key|now==now:
                continue
            dp[i+1][now|key] = min(dp[i+1][now|key],dp[i][now]+A[i])
    if dp[M][mask-1]==inf:
        print(-1)
    else:
        ans = dp[M][mask-1]
        print(ans)
    #print(dp)
    return

def ABC160_F():
    class combination():
        # 素数のmod取るときのみ　速い
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    C = combination(N,mod)
    children = [-1] * N
    A = [0] * N
    def dfs(s):
        size = 1
        nowchild = []
        cur = 1
        children[s] = 0
        for i in V[s]:
            if children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= mod
        children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= C.comb(rest, k)
            rest -= k
            cur %= mod
        A[s] = cur
        return size, cur

    rep = [0] * N
    def dfs2(s, p=-1):
        cur = 1
        rest = N - 1
        for to in V[s]:
            cur *= A[to]
            cur %= mod
        for to in V[s]:
            cur *= C.comb(rest, children[to])
            rest -= children[to]
            cur %= mod
        rep[s] = cur

        n = len(V[s])
        L = [0] * N; R = [0] * N
        L2 = [0] * N; R2 = [0] * N

        for i, ne in enumerate(V[s]):
            L[i] = R[i] = A[ne] * C.inv[children[ne]] % mod
            L2[i] = R2[i] = children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(V[s]):
            if ne == p:
                continue
            A[s] = 1
            children[s] = 1
            if i > 0:
                A[s] *= L[i - 1]
                A[s] %= mod
                children[s] += L2[i - 1]
            if i + 1 < n:
                A[s] *= R[i + 1]
                A[s] %= mod
                children[s] += R2[i + 1]
            A[s] *= C.fac[N - children[ne] - 1]
            A[s] %= mod
            dfs2(ne, s)
        return

    dfs(0)
    dfs2(0)

    for ans in rep:
        print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160_F()

"""

"""

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():
    #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 math
import sys, resource
from collections import deque

sys.setrecursionlimit(10 ** 9)

to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1

def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    dfs = deque([])
    dfs.append([1,1])

    while len(dfs) != 0:
        i = dfs.pop()
        ans = 1
        num = 1
        for j in to[i[0]]:
            if j != i[1] and j != i[0]:
                if treenum.get((i[0],j)) == None:
                    dfs.append([i[0], i[1]])
                    dfs.append([j, i[0]])
                    continue
                num += treenum[(i[0],j)]
                ans = (ans*dpv[(i[0],j)]) *invfact[treenum[(i[0],j)]] % (MOD)
        
        treenum[(i[1],i[0])] = num
        treenum[(i[0],i[0])] = N
        dpv[(i[1],i[0])] = ans * fact[num-1] % (MOD)


    bfs = deque([])
    for i in to[1]:
        bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        # if dpv.get(parent,parent) == None:
        treenum[(i[1],i[0])] = N-treenum[(i[0],i[1])]
        #dpv[i[1]][i[0]] = (dpv[i[0]][i[0]]*invfact[treenum[i[0]][i[0]]-1]*fact[treenum[i[0]][i[0]]-1-treenum[i[0]][i[1]]]*fact[treenum[i[0]][i[1]]]% (MOD)/dpv[i[0]][i[1]]) % (MOD)
        val = dpv[(i[0],i[0])]*invfact[treenum[(i[0],i[0])]-1]%MOD
        val = val * fact[treenum[(i[0],i[0])]-1-treenum[(i[0],i[1])]]%MOD
        val = val * fact[treenum[(i[0],i[1])]] % (MOD)
        dpv[(i[1],i[1])] =  val *invfact[treenum[(i[1],i[0])]]%MOD
        dpv[(i[1],i[1])] = dpv[(i[1],i[1])] *invfact[treenum[(i[0],i[1])]-1]%MOD
        dpv[(i[1],i[1])] = dpv[(i[1],i[1])] * fact[N-1] % (MOD)

        for j in to[i[1]]:
            if j != i[0]:
                bfs.append([i[1],j])

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

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys, resource
from collections import deque

sys.setrecursionlimit(10 ** 9)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            pways(i, v)
            num += treenum[(v,i)]
            ans = (ans*dpv[(v,i)]) *invfact[treenum[(v,i)]] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    pways(1,1)

    bfs = deque([])
    for i in to[1]:
        bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        # if dpv.get(parent,parent) == None:
        treenum[(i[1],i[0])] = N-treenum[(i[0],i[1])]
        #dpv[i[1]][i[0]] = (dpv[i[0]][i[0]]*invfact[treenum[i[0]][i[0]]-1]*fact[treenum[i[0]][i[0]]-1-treenum[i[0]][i[1]]]*fact[treenum[i[0]][i[1]]]% (MOD)/dpv[i[0]][i[1]]) % (MOD)
        val = dpv[(i[0],i[0])]*invfact[treenum[(i[0],i[0])]-1]%MOD
        val = val * fact[treenum[(i[0],i[0])]-1-treenum[(i[0],i[1])]]%MOD
        val = val * fact[treenum[(i[0],i[1])]] % (MOD)
        dpv[(i[1],i[1])] =  val *invfact[treenum[(i[1],i[0])]]%MOD
        dpv[(i[1],i[1])] = dpv[(i[1],i[1])] *invfact[treenum[(i[0],i[1])]-1]%MOD
        dpv[(i[1],i[1])] = dpv[(i[1],i[1])] * fact[N-1] % (MOD)

        for j in to[i[1]]:
            if j != i[0]:
                bfs.append([i[1],j])

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

main()

Submission status: Time Limit Exceeded

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

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

mod = 10 ** 9 + 7

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

inv = [pow(fac[-1], mod - 2, mod)]
for i in range(N, 0, -1) :
  inv.append(inv[-1] * i % mod)
inv = inv[::-1]

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

pattern = [1] * N
subtree = [0] * N

# DFS
stack = [(0, -1, 0)]
while stack :
  cur, pre, op = stack.pop()
  
  if op == 0 :
    stack.append((cur, pre, 1))
    for nex in vec[cur] :
      if nex == pre : continue
      stack.append((nex, cur, 0))
  else :
    for nex in vec[cur] :
      pattern[cur] *= pattern[nex] * comb(subtree[cur] + subtree[nex], subtree[nex]) % mod
      pattern[cur] %= mod
      subtree[cur] += subtree[nex]
    subtree[cur] += 1

# BFS
q = [(0, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex == pre : continue
    pattern[nex] = pattern[cur] * subtree[nex] * inv[N - subtree[nex]] * fac[N - subtree[nex] - 1] % mod
    q.append((nex, cur))
  
for i in range(N) :
  print(pattern[i])

Submission status: Time Limit Exceeded

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

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

mod = 10 ** 9 + 7

fac = [1]
inv = [1]
for i in range(1, N + 10) :
  fac.append(fac[-1] * i)
  inv.append(pow(fac[-1], mod - 2, mod))

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

pattern = [1] * N
subtree = [0] * N

def dfs(cur, pre=-1) :
  for nex in vec[cur] :
    if nex == pre : continue
    dfs(nex, cur)
    pattern[cur] *= pattern[nex] * comb(subtree[cur] + subtree[nex], subtree[nex]) % mod
    pattern[cur] %= mod
    subtree[cur] += subtree[nex]
  subtree[cur] += 1
  
dfs(0)

q = [(0, -1)]
while q :
  cur, pre = q.pop()
  for nex in vec[cur] :
    if nex == pre : continue
    pattern[nex] = pattern[cur] * subtree[nex] * inv[N - subtree[nex]] * fac[N - subtree[nex] - 1] % mod
    q.append((nex, cur))
  
for i in range(N) :
  print(pattern[i])