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

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


def treedoubling(P):
    #根の親は-1
    P = P[:]
    N = len(P)
    D = [P[:]]
    dep = N.bit_length()
    for _ in range(dep):
        ret = [-1]*N
        for i in range(N):
            k = D[-1][i]
            if k != -1:
                ret[i] = D[-1][k]
        D.append(ret)
    return D

def lca(u, v, D, par, dist):
    if dist[u] > dist[v]:
        u, v = v, u
    
    ddif = dist[v] - dist[u]
    for i in range(ddif.bit_length()):
        if (1<<i)&ddif:
            v = D[i][v]
    
    if u != v:
        for cnt in range(dist[u].bit_length()-1, -1, -1):
            if D[cnt][u] != D[cnt][v]:
                u = D[cnt][u]
                v = D[cnt][v]
        u = par[u]
    return u

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order

def rerootingdp(P, L, intv = None):
    def merge(x, y):
        if x == intv:
            return y
        if y == intv:
            return x
        sa, da = x
        sb, db = y
        return (sa + sb, da*db%MOD)

    def g(m, vn):
        if m == intv:
            return (1, 1)
        sc, dc = m
        return (sc+1, dc*frac[sc]*fraci[sc+1]%MOD)
    
    N = len(L)
    dp = [None]*N
    LR = [intv]*N
    D = [intv]*N
    cld = [[] for _ in range(N)]
    for l in L[::-1]:        
        resl = intv
        for ci in cld[l]:
            LR[ci] = merge(LR[ci], resl)
            resl = merge(resl, dp[ci])
        resr = intv
        for ci in cld[l][::-1]:
            LR[ci] = merge(LR[ci], resr)
            resr = merge(resr, dp[ci])
        D[l] = resr
        dp[l] = g(resr, l)
        
        if P[l] != -1:
            cld[P[l]].append(l)
        
    U = [None]*N
    ans = [None]*N
    U[L[0]] = intv
    ans[L[0]] = dp[L[0]]
    for l in L[1:]:
        p = P[l]
        U[l] = g(merge(U[p], LR[l]), p)
        ans[l] = g(merge(D[l], U[l]), l)    
    return ans 

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p):
        if v == -1:
            continue
        res[v].append(i)
    return res


MOD = 10**9+7
def frac(limit):
    frac = [1]*limit
    for i in range(2,limit):
        frac[i] = i * frac[i-1]%MOD
    fraci = [None]*limit
    fraci[-1] = pow(frac[-1], MOD -2, MOD)
    for i in range(-2, -limit-1, -1):
        fraci[i] = fraci[i+1] * (limit + i + 1) % MOD
    return frac, fraci
frac, fraci = frac(1341398)

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



P, L = parorder(Edge, 0)

Ans = [frac[a]*d%MOD for a, d in rerootingdp(P, L)]
print('\n'.join(map(str, Ans)))

Submission status: Accepted

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

def main():
	N = int(input())
	edge = [[] for _ in range(N+1)]
	
	MOD = 10**9+7
	fac = [0]*(N+1)
	fac[0],fac[1] = 1,1
	invfac = [0]*(N+1)
	invfac[0],invfac[1] = 1,1

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

	invfac[-1] = pow(fac[-1],MOD-2,MOD)
	for i in range(N,0,-1):
		invfac[i-1] = (invfac[i]*i)%MOD
	
	for _ in range(N-1):
		a,b = map(int,input().split())
		edge[a].append(b)
		edge[b].append(a)

	proc = []
	parent = [0]*(N+1)
	q = deque([1])
	while q:
		now = q.pop()
		proc.append(now)
		for fol in edge[now]:
			if fol == parent[now]:
				continue
			parent[fol] = now
			q.append(fol)
	
	d_size = [0]*(N+1)
	d_dp = [1]*(N+1)

	for v in proc[::-1]:
		d_dp[v] *= fac[d_size[v]]
		d_dp[v] %= MOD
		p = parent[v]
		s = d_size[v]+1
		d_size[p] += s
		d_dp[p] *= d_dp[v]*invfac[s]
		d_dp[p] %= MOD
	
	u_size = [N-num-1 for num in d_size]
	u_dp = [1]*(N+1)
	
	for v in proc[1:]:
	    p = parent[v]
	    x = d_dp[p]
	    x *= u_dp[p]
	    x *= invfac[d_size[p]]
	    x *= fac[d_size[v]+1]
	    x *= pow(d_dp[v],MOD-2,MOD)
	    x %= MOD
	    x *= fac[u_size[v]-1]
	    x *= invfac[u_size[p]]
	    u_dp[v] = x%MOD
	
	u_size[1] = 0
	u_dp[1] = 1
	
	for i in range(1,N+1):
	    ret = d_dp[i]*u_dp[i]*fac[d_size[i]+u_size[i]]*invfac[d_size[i]]*invfac[u_size[i]]%MOD
	    print(ret)

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
MOD = 1000000007  # type: int


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        b = (self.finv[k]*self.finv[n-k] % self.MOD)
        return (self.fac[n] * b) % self.MOD


def make_downward(E, N, s=0):
    # BFSでdownward順を構成する
    front, back = 0, 1
    downward = [s]*N
    parent = [-1]*N
    for _ in range(N-1):
        v = downward[front]
        front += 1
        for u in E[v]:
            if u == parent[v]:
                continue
            parent[u] = v
            downward[back] = u
            back += 1
    # print(downward)
    return downward, parent


def solve(N: int, a: "List[int]", b: "List[int]"):
    # グラフの構築
    E = [[] for _ in range(N)]
    for aa, bb in zip(a, b):
        E[aa-1].append(bb-1)
        E[bb-1].append(aa-1)

    # 組み合わせの初期化
    cmb = Combination(N)

    # BFSでdownward順を構成する
    downward, parent = make_downward(E, N)

    # 節点vを根とした部分木の塗り方dp[v]
    dp = [1]*N
    # 節点vを根とした部分木のサイズsize[v]+1
    size = [0]*N

    # 木DP
    # 葉から根へ向かう探索
    for v in reversed(downward):
        for u in E[v]:
            if u == parent[v]:
                continue
            size[v] += size[u]+1
            dp[v] *= cmb.finv[size[u]+1]
            dp[v] %= MOD
            dp[v] *= dp[u]
            dp[v] %= MOD
        dp[v] *= cmb.fac[size[v]]
        dp[v] %= MOD

    # 全方位木DP
    # 根から葉へ向かう探索
    for v in downward:
        for u in E[v]:
            if u == parent[v]:
                continue
            dp[u] = dp[v]
            dp[u] *= (size[u]+1)*cmb.inv[N-(size[u]+1)]
            dp[u] %= MOD

    for v in dp:
        print(v)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
MOD = 1000000007  # type: int


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        b = (self.finv[k]*self.finv[n-k] % self.MOD)
        return (self.fac[n] * b) % self.MOD


def solve(N: int, a: "List[int]", b: "List[int]"):
    # グラフの構築
    E = [[] for _ in range(N)]
    for aa, bb in zip(a, b):
        E[aa-1].append(bb-1)
        E[bb-1].append(aa-1)

    # 組み合わせの初期化
    cmb = Combination(N)

    # BFSの入り順を構成する
    front, back = -1, 1
    downward = [0]*N
    parent = [-1]*N
    for _ in range(N-1):
        front += 1
        v = downward[front]
        for u in E[v]:
            if u == parent[v]:
                continue
            parent[u] = v
            downward[back] = u
            back += 1
    # print(downward)

    # 節点vを根とした部分木の塗り方dp[v]
    dp = [1]*N
    # 節点vを根とした部分木のサイズsize[v]+1
    size = [0]*N

    # 木DP
    # 葉から根へ向かう探索
    for v in reversed(downward):
        for u in E[v]:
            if u == parent[v]:
                continue
            size[v] += size[u]+1
            dp[v] *= cmb.finv[size[u]+1]
            dp[v] %= MOD
            dp[v] *= dp[u]
            dp[v] %= MOD
        dp[v] *= cmb.fac[size[v]]
        dp[v] %= MOD

    # 全方位木DP
    # 根から葉へ向かう探索
    for v in downward:
        for u in E[v]:
            if u == parent[v]:
                continue
            dp[u] = dp[v]
            dp[u] *= (size[u]+1)*cmb.inv[N-(size[u]+1)]
            dp[u] %= MOD

    for v in dp:
        print(v)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from functools import lru_cache
MOD = 1000000007  # type: int


@lru_cache(maxsize=None)
def div(a, b):
    return (a * pow(b, MOD-2, MOD)) % MOD


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        b = (self.finv[k]*self.finv[n-k] % self.MOD)
        return (self.fac[n] * b) % self.MOD


def solve(N: int, a: "List[int]", b: "List[int]"):
    # グラフの構築
    E = [[] for _ in range(N)]
    for aa, bb in zip(a, b):
        E[aa-1].append(bb-1)
        E[bb-1].append(aa-1)

    # 組み合わせの初期化
    cmb = Combination(N)

    # BFSの入り順を構成する
    curr = -1
    downward = [0]
    parent = [-1]*N
    while len(downward) < N:
        curr += 1
        v = downward[curr]
        for u in E[v]:
            if u == parent[v]:
                continue
            parent[u] = v
            downward.append(u)
    # print(downward)

    # 節点vを根とした部分木の塗り方dp[v]
    dp = [1]*N
    # 節点vを根とした部分木のサイズsize[v]+1
    size = [0]*N

    # 木DP
    # 葉から根へ向かう探索
    for v in reversed(downward):
        for u in E[v]:
            if u == parent[v]:
                continue
            size[v] += size[u]+1
            dp[v] *= cmb.finv[size[u]+1]
            dp[v] %= MOD
            dp[v] *= dp[u]
            dp[v] %= MOD
        dp[v] *= cmb.fac[size[v]]
        dp[v] %= MOD

    # 全方位木DP
    # 根から葉へ向かう探索
    for v in downward:
        for u in E[v]:
            if u == parent[v]:
                continue
            dp[u] = dp[v]
            dp[u] *= (size[u]+1)*cmb.inv[N-(size[u]+1)]
            dp[u] %= MOD

    for v in dp:
        print(v)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from functools import lru_cache
from collections import deque
MOD = 1000000007  # type: int


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, src, dest, w=1):
        self.E[src].append((dest, w))
        self.E[dest].append((src, w))


@lru_cache(maxsize=None)
def div(a, b):
    return (a * pow(b, MOD-2, MOD)) % MOD


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        b = (self.finv[k]*self.finv[n-k] % self.MOD)
        return (self.fac[n] * b) % self.MOD


def solve(N: int, a: "List[int]", b: "List[int]"):
    # グラフの構築
    g = Graph(N)
    for aa, bb in zip(a, b):
        g.add_edge(aa-1, bb-1)

    # 組み合わせの初期化
    cmb = Combination(N)

    # BFSの入り順を構成する
    curr = -1
    downward = [0]
    parent = [-1]*N
    while len(downward) < N:
        curr += 1
        v = downward[curr]
        for u, _ in g.E[v]:
            if u == parent[v]:
                continue
            parent[u] = v
            downward.append(u)
    # print(downward)

    # 節点vを根とした部分木の塗り方dp[v]
    dp = [1]*N
    # 節点vを根とした部分木のサイズsize[v]+1
    size = [0]*N

    # 葉から根へ向かう探索
    for v in reversed(downward):
        for u, _ in g.E[v]:
            if u == parent[v]:
                continue
            size[v] += size[u]+1
            dp[v] *= cmb(size[v], size[u]+1)
            dp[v] %= MOD
            dp[v] *= dp[u]
            dp[v] %= MOD

    # 全方位木DP
    # 根から葉へ向かう探索
    for v in downward:
        for u, _ in g.E[v]:
            if u == parent[v]:
                continue
            d = div(dp[v], cmb(N-1, size[u]+1))
            d = div(d, dp[u])
            dp[u] *= cmb(N-1, size[u])
            dp[u] %= MOD
            dp[u] *= d
            dp[u] %= MOD

    for v in dp:
        print(v)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from collections import defaultdict
from functools import lru_cache
from collections import deque


sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, src, dest, w=1):
        self.E[src].append((dest, w))
        self.E[dest].append((src, w))


@lru_cache(maxsize=None)
def div(a, b):
    return (a * pow(b, MOD-2, MOD)) % MOD


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    @lru_cache(maxsize=None)
    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        b = (self.finv[k]*self.finv[n-k] % self.MOD)
        return (self.fac[n] * b) % self.MOD


def solve(N: int, a: "List[int]", b: "List[int]"):
    # print(div(3, 2))

    # 全方位木DPをやるぞ！
    # 1. 木DPによって頂点ごとにhogeを求める
    # 2. 木DPで求めたhogeを使って、上手く求める

    # グラフの構築
    g = Graph(N)
    for aa, bb in zip(a, b):
        g.add_edge(aa-1, bb-1)

    # 組み合わせの初期化
    cmb = Combination(N)

    dp = [1]*N                  # 節点vを根とした部分木の塗り方dp[v]
    size = [0]*N                # 節点vを根とした部分木のサイズsize[v]+1

    # 木DPを行うDFS
    queue = [(0, -1)]
    seen = [False]*N

    while queue:
        v, p = queue[-1]
        flag = True
        if seen[v] is False:
            for u, _ in g.E[v]:
                if u == p:
                    continue
                if seen[u] is False:
                    queue.append((u, v))
                    flag = False
        if flag is True:
            # 処理
            for u, _ in g.E[v]:
                if u == p:
                    continue
                size[v] += size[u]+1
                dp[v] *= cmb(size[v], size[u]+1)
                dp[v] %= MOD
                dp[v] *= dp[u]
                dp[v] %= MOD
            # print(v, p)
            queue.pop()
            seen[v] = True
    # print(*queue)
    # print(*[(d, s) for d, s in zip(dp, size)])

    # 節点0には木の根としての値を求めた。
    # 0以外の節点には部分木の根としての値を求めた。
    # 木の根としての値を求めた節点を親としてもつ節点は、自身を木の根とした値を求めることができる

    # 全方位木DPを行うBFS
    queue = deque()
    queue.append((0, -1))

    while len(queue) > 0:
        v, p = queue.popleft()
        for u, _ in g.E[v]:
            if u == p:
                continue
            d = div(dp[v], cmb(N-1, size[u]+1))
            d = div(d, dp[u])
            dp[u] *= cmb(N-1, size[u])
            dp[u] %= MOD
            dp[u] *= d
            dp[u] %= MOD
            queue.append((u, v))

    for v in dp:
        print(v)
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


input=sys.stdin.readline
write=sys.stdout.write

N=int(input())
hen={i:[] for i in range(1,N+1)}
for i in range(0,N-1):
    a,b=map(int,input().split())
    hen[a].append(b)
    hen[b].append(a)

parent={i:-1 for i in range(1,N+1)}
parent[1]=0
q=[]
q.append(1)
sub=[]
while q!=[]:
    while q!=[]:
        x=q.pop()
        for p in hen[x]:
            if parent[p]==-1:
                parent[p]=x
                sub.append(p)
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            break

ans={i:1 for i in range(1,N+1)}
subtreesize={i:1 for i in range(1,N+1)}
flag={i:0 for i in range(0,N+1)}
q=[]
for i in range(1,N+1):
    if i!=1 and len(hen[i])==1:
        q.append(i)


sub=[]
while q!=[]:
    while q!=[]:
        x=q.pop()
        p=parent[x]
        if p!=1:
            ans[p]=(ans[p]*ans[x]*g2[subtreesize[x]])%mod
            subtreesize[p]+=subtreesize[x]
            flag[p]+=1
            if flag[p]==len(hen[p])-1:
                ans[p]=(ans[p]*g1[subtreesize[p]-1])%mod
                sub.append(p)
        else:
            subtreesize[1]+=subtreesize[x]
            ans[1]=(ans[1]*ans[x]*g2[subtreesize[x]])%mod
            flag[1]+=1
            if flag[1]==len(hen[1]):
                ans[1]=(ans[1]*g1[subtreesize[1]-1])%mod
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            break

q=[1]
flag2={i:0 for i in range(1,N+1)}
flag2[1]=1
sub=[]
while q!=[]:
    while q!=[]:
        x=q.pop()
        for p in hen[x]:
            if flag2[p]==0:
                if len(hen[p])!=1:
                    ans[p]=(ans[x]*pow(N-subtreesize[p],mod-2,mod)*g1[subtreesize[p]]*g2[subtreesize[p]-1])%mod
                    flag2[p]=1
                    sub.append(p)
                else:
                    ans[p]=(ans[x]*pow(N-1,mod-2,mod))%mod

        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            break

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

Submission status: Accepted

Solution code:
import sys

def cmb(n, r, mod):#コンビネーションの高速計算　
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 2*10**5
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )


input=sys.stdin.readline
write=sys.stdout.write

N=int(input())
hen={i:[] for i in range(1,N+1)}
for i in range(0,N-1):
    a,b=map(int,input().split())
    hen[a].append(b)
    hen[b].append(a)

parent={i:-1 for i in range(1,N+1)}
parent[1]=0
q=[]
q.append(1)
sub=[]
while q!=[]:
    while q!=[]:
        x=q.pop()
        for p in hen[x]:
            if parent[p]==-1:
                parent[p]=x
                sub.append(p)
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            break

ans={i:1 for i in range(1,N+1)}
subtreesize={i:1 for i in range(1,N+1)}
flag={i:0 for i in range(0,N+1)}
q=[]
for i in range(1,N+1):
    if i!=1 and len(hen[i])==1:
        q.append(i)


sub=[]
while q!=[]:
    while q!=[]:
        x=q.pop()
        p=parent[x]
        if p!=1:
            ans[p]=(ans[p]*ans[x]*g2[subtreesize[x]])%mod
            subtreesize[p]+=subtreesize[x]
            flag[p]+=1
            if flag[p]==len(hen[p])-1:
                ans[p]=(ans[p]*g1[subtreesize[p]-1])%mod
                sub.append(p)
        else:
            subtreesize[1]+=subtreesize[x]
            ans[1]=(ans[1]*ans[x]*g2[subtreesize[x]])%mod
            flag[1]+=1
            if flag[1]==len(hen[1]):
                ans[1]=(ans[1]*g1[subtreesize[1]-1])%mod
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            break

q=[1]
flag2={i:0 for i in range(1,N+1)}
flag2[1]=1
sub=[]
while q!=[]:
    while q!=[]:
        x=q.pop()
        for p in hen[x]:
            if flag2[p]==0:
                if len(hen[p])!=1:
                    ans[p]=(ans[x]*pow(N-subtreesize[p],mod-2,mod)*g1[subtreesize[p]]*g2[subtreesize[p]-1])%mod
                    flag2[p]=1
                    sub.append(p)
                else:
                    ans[p]=(ans[x]*pow(N-1,mod-2,mod))%mod

        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            break

for i in range(1,N+1):
    write(str(ans[i])+"\n")

Submission status: Accepted

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

mod = 10 ** 9 + 7
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

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

##### Settings
unit = 1
merge = lambda a, b: a * b % mod
adj_bu = lambda a, i: a * inv(SIZE[i]) % mod
adj_td = lambda a, i, p: a * inv(N-SIZE[i]) % mod
adj_fin = lambda a, i: a * fa[N-1] % mod
#####

nn = 200200
mod = 10**9+7

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

inv = lambda i: fainv[i] * fa[i-1] % mod

SIZE = [1] * N
for i in R[1:][::-1]:
    SIZE[P[i]] += SIZE[i]

ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_fin(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])
    ac = unit
    for j in reversed(X[i]):
        TD[j] = adj_td(merge(TD[j], ac), j, i)
        ac = merge(ac, XX[j])
        XX[j] = adj_fin(merge(ME[j], TD[j]), j)

print(*XX, sep = "\n")

Submission status: Accepted

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

mod = 10 ** 9 + 7
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

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

##### Settings
unit = 1
merge = lambda a, b: a * b % mod
adj_bu = lambda a, i: a * inv(SIZE[i]) % mod
adj_td = lambda a, i, p: a * inv(N-SIZE[i]) % mod
adj_fin = lambda a, i: a * fa[N-1] % mod
#####

nn = 200200
mod = 10**9+7

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

inv = lambda i: fainv[i] * fa[i-1] % mod

SIZE = [1] * N
for i in R[1:][::-1]:
    SIZE[P[i]] += SIZE[i]

ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in R[1:][::-1]:
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_fin(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])
    ac = unit
    for j in X[i][::-1]:
        TD[j] = adj_td(merge(TD[j], ac), j, i)
        ac = merge(ac, XX[j])
        XX[j] = adj_fin(merge(ME[j], TD[j]), j)

print(*XX, sep = "\n")

Submission status: Accepted

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

mod = 10 ** 9 + 7
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

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

##### Settings
unit = 1
merge = lambda a, b: a * b % mod
adj_bu = lambda a, i: a * inv(SIZE[i]) % mod
adj_td = lambda a, i, p: a * inv(N-SIZE[i]) % mod
adj_fin = lambda a, i: a * fa[N-1] % mod
#####

nn = 200200
mod = 10**9+7

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

inv = lambda i: fainv[i] * fa[i-1] % mod

SIZE = [1] * N
for i in reversed(R[1:]):
    SIZE[P[i]] += SIZE[i]

ME = [unit] * N
XX = [0] * N
TD = [unit] * N
for i in reversed(R[1:]):
    XX[i] = adj_bu(ME[i], i)
    p = P[i]
    ME[p] = merge(ME[p], XX[i])
XX[R[0]] = adj_fin(ME[R[0]], R[0])

for i in R:
    ac = TD[i]
    for j in X[i]:
        TD[j] = ac
        ac = merge(ac, XX[j])
    ac = unit
    for j in reversed(X[i]):
        TD[j] = adj_td(merge(TD[j], ac), j, i)
        ac = merge(ac, XX[j])
        XX[j] = adj_fin(merge(ME[j], TD[j]), j)

print(*XX, sep = "\n")