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
sys.setrecursionlimit(10 ** 7)
class Tree:
  C, RL = {}, {}
  R, N, D, S, P, T = None, None, None, None, None, None
  TL = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N #各ノードのランク
    s.R[root] = 1
    s.RL[1] = [root] #各ランクのノード
    s.S = {} #各ノードの子ノード
    s.P = [-1] * s.N #各ノードの親ノード
    s.D = 1
    while s.RL[s.D] != []:
      s.D += 1
      s.RL[s.D] = []
      for i in s.RL[s.D - 1]:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            s.RL[s.D].append(j)
            if i not in s.S: s.S[i] = [j]
            else: s.S[i].append(j)
            s.P[j] = i      
  def bottomUpDP(s):
    for i in range(s.D - 2, 0, -1):
      T = s.RL[i]
      for j in T:
        if j not in s.S: continue
        for k in s.S[j]:
          s.dp_sub_exe(j, k)
  def topDownDP(s):
    for i in range(2, s.D):
      T = s.RL[i]
      for j in T:
        s.dp_sub_exe_inv(j, s.P[j])
  def allDP(s):
    s.dp_init()
    s.bottomUpDP()
    s.topDownDP()
    return s.DP
  def dp_init(s): #単位元で初期化
    s.DP = [1] * N
    s.sDP = [1] * N
  def dp_sub_exe(s, x, y): #ボトムアップの処理
    s.sDP[x] += s.sDP[y]
    s.DP[x] = s.DP[x] * s.DP[y] * com.com(s.sDP[x] - 1, s.sDP[y]) % MOD
  def dp_sub_exe_inv(s, x, y): #トップダウンの処理
    t = com.com(s.sDP[y] - 1, s.sDP[x]) * s.DP[x] % MOD
    t = s.DP[y] * s.inv(t, MOD)
    k = s.sDP[y] - s.sDP[x]
    k = com.com(s.sDP[y] - 1, k) % MOD
    s.sDP[x] = s.sDP[y]
    s.DP[x] = s.DP[x] * t * k % MOD
  def inv(s, a, mod): #逆元
    return pow(a, mod - 2, mod)
  
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]

MOD = 10 ** 9 + 7
com = comb(N, MOD)

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

T.makeRank(0)
DP = T.allDP()

for i in DP:
  print(i)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
class Tree:
  C, RL = {}, {}
  R, N, D, S, P, T = None, None, None, None, None, None
  TL = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N #各ノードのランク
    s.R[root] = 1
    s.RL[1] = [root] #各ランクのノード
    s.S = {} #各ノードの子ノード
    s.P = [-1] * s.N #各ノードの親ノード
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            if i not in s.S:
              s.S[i] = [j]
            else:
              s.S[i].append(j)
            s.P[j] = i
      s.D += 1
      F = Ft
  def dfs(s, x, y, r): #xからyまでの道O(M)
    if x == y:
      return [x]
    for i in s.C[x]:
      if i != r:
        t = s.dfs(i, y, x)
        if t != False:
          return [x] + t
    return False
  def dist(s, x): #最遠のノード,距離
    t = [-1] * s.N
    S = [x]
    ans = x
    ansn = 0
    t[x] = 0
    while S != []:
      k = S.pop()
      for i in s.C[k]:
        if t[i] == -1:
          t[i] = t[k] + 1
          S.append(i)
          if t[i] > ansn:
            ansn = t[i]
            ans = i
    return ans, ansn
  def getDi(s, x = 0): #直径
    a, _ = s.dfs(x)
    b, ans = s.dfs(a)
    return ans
  def getDeep(s, x): #xの子孫のうち一番深い深さ
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n): #xのn世代前の親
    if n == 0:
      return x
    if s.P[x] == -1:
      return -n
    return s.getParent(s.P[x], n - 1)
  def tour(s): #オイラーツアー
    x = s.RL[1][0]
    s.T = [] #ツアー
    s.TL = [[] for _ in range(s.N)] #各ノードの出現位置
    s.TL[x].append(len(s.T))
    s.T.append(x)
    for i in (s.S[s.RL[1][0]]):
      s.tour_sub(i)
    return s.T
  def tour_sub(s, x): #オイラーツアーのサブ
    s.TL[x].append(len(s.T))
    s.T.append(x)
    if x in s.S:
      for i in (s.S[x]):
        s.tour_sub(i)
    s.TL[s.P[x]].append(len(s.T))
    s.T.append(s.P[x])
  def bottomUpDP(s):
    s.dp_init()
    for i in range(s.D - 1, 0, -1):
      T = s.RL[i]
      for j in T:
        s.dp_sub(j)
  def allDP(s):
    bDP = s.bottomUpDP()
    for i in range(2, s.D):
      T = s.RL[i]
      for j in T:
        s.dp_sub_exe_inv(j, s.P[j])
  def dp_init(s): #単位元で初期化
    s.DP = [1] * N
    s.sDP = [1] * N
  def dp_sub(s, x):
    if x not in s.S:
      return 0
    T = s.S[x]
    for i in T:
      s.dp_sub_exe(x, i)
  def dp_sub_exe(s, x, y): #ボトムアップの処理
    s.sDP[x] += s.sDP[y]
    s.DP[x] = s.DP[x] * s.DP[y] * com.com(s.sDP[x] - 1, s.sDP[y]) % MOD
  def dp_sub_exe_inv(s, x, y): #トップダウンの処理
    t = com.com(s.sDP[y] - 1, s.sDP[x]) * s.DP[x] % MOD
    t = s.DP[y] * s.inv(t, MOD)
    k = s.sDP[y] - s.sDP[x]
    k = com.com(s.sDP[y] - 1, k) % MOD
    s.sDP[x] = s.sDP[y]
    s.DP[x] = s.DP[x] * t * k % MOD
    return 
  def inv(s, a, mod): #逆元
    return pow(a, mod - 2, mod)
  
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD

N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]

MOD = 10 ** 9 + 7
com = comb(N, MOD)

T = Tree(N)
for a, b in ab:
  a -= 1
  b -= 1
  T.set(a, b)

T.makeRank(0)
T.allDP()

for i in T.DP:
  print(i)

Submission status: Accepted

Solution code:
class ReRooting(object):
    """ 全方位木DP """
    def merge(self, a, b):
        """ 二項演算 a・b """
        return a * b % MOD
 
    def adj_bu(self, accBU, v:int):
        """
        Bottom-Upの単項演算 g(accBU[v])
 
        v: 頂点
        """
        return accBU * inv(self.SIZE[v]) % MOD
 
    def adj_td(self, accTD, v:int, p:int):
        """
        Top-Downの単項演算 g(accTD[v])
 
        v: 頂点
        p: 親
        """
        return accTD * inv(self.V - self.SIZE[v]) % MOD
 
    def adj_fin(self, acc, v:int):
        """
        最終結果の単項演算 g(acc[v])
 
        v: 頂点
        """
        return acc * fact[self.V - 1] % MOD

    def __init__(self, V:int, e:int):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
        self.SIZE = [1] * self.V
    
    def subtree_size(self):
        """ 部分木のサイズを求める """
        for v in reversed(self.order[1:]):
            self.SIZE[self.par[v]] += self.SIZE[v]

    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    que.append(w)
    
    def bottom_up(self):
        """ Bottom-Up DP """
        root = self.order[0]
        accBU = [self.e] * self.V
        resBU = [self.e] * self.V

        for v in reversed(self.order):
            resBU[v] = self.adj_bu(accBU[v], v)

            if v == root: break

            p = self.par[v]
            accBU[p] = self.merge(accBU[p], resBU[v])

        return accBU, resBU
    
    def top_down(self, resBU:list):
        """ Top-Down DP """
        accTD = [self.e] * self.V
        resTD = [self.e] * self.V

        for p in self.order:
            ac = resTD[p]
            for v in self.edge[p]:
                if v == self.par[p]: continue
                accTD[v] = ac
                ac = self.merge(ac, resBU[v])

            ac = self.e
            for v in reversed(self.edge[p]):
                if v == self.par[p]: continue
                accTD[v] = self.merge(accTD[v], ac)
                ac = self.merge(ac, resBU[v])
                resTD[v] = self.adj_td(accTD[v], v, p)

        return resTD
    
    def solve(self):
        self.topological_sort()
        self.subtree_size()
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)
        res = [self.adj_fin(self.merge(a, b), v) for v,(a,b) in enumerate(zip(accBU, resTD))]
        return res

#########################################################################################
N = int(input())
MOD = 10 ** 9 + 7
 
fact = [1] * (N + 1) # fact[n]: n!
factinv = [1] * (N + 1) # n!の逆元
for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % MOD
factinv[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(N - 1, -1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % MOD
inv = lambda n: fact[n - 1] * factinv[n] % MOD # inv[n]: nの逆元
 
def main():
    RR = ReRooting(N, 1)
    for _ in range(N - 1):
        a, b = map(int, input().split())
        RR.add_edge(a - 1, b- 1)
 
    print(*RR.solve(), sep="\n")
 
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class ReRooting(object):
    """ 全方位木DP """
    def merge(self, a, b):
        """ 二項演算 a・b """
        return a * b % MOD

    def adj_bu(self, accBU, v:int):
        """
        Bottom-Upの単項演算 g(accBU[v])

        v: 頂点
        """
        return accBU * inv(self.SIZE[v]) % MOD

    def adj_td(self, accTD, v:int, p:int):
        """
        Top-Downの単項演算 g(accTD[v])

        v: 頂点
        p: 親
        """
        return accTD * inv(self.V - self.SIZE[v]) % MOD

    def adj_fin(self, acc, v:int):
        """
        最終結果の単項演算 g(acc[v])

        v: 頂点
        """
        return acc * fact[self.V - 1] % MOD

    def __init__(self, V:int, e:int):
        """
        V: 頂点数
        e: 単位元
        """
        self.V, self.e = V, e
        self.edge = [[] for _ in range(V)]
        self.par = [-1] * V
        self.order = []
        self.SIZE = [1] * self.V
    
    def subtree_size(self):
        """ 部分木のサイズを求める """
        for v in reversed(self.order[1:]):
            self.SIZE[self.par[v]] += self.SIZE[v]

    def add_edge(self, u:int, v:int):
        """ 辺(u,v)をグラフに追加する """
        self.edge[u].append(v)
        self.edge[v].append(u)
    
    def topological_sort(self, root:int = 0):
        """ トポロジカルソート """
        from collections import deque
        que = deque([root])
        while que:
            v = que.popleft()
            self.order.append(v)
            for w in self.edge[v]:
                if w != self.par[v]:
                    self.par[w] = v
                    self.edge[w].remove(v)
                    que.append(w)
    
    def bottom_up(self):
        """ Bottom-Up DP """
        root = self.order[0]
        accBU = [self.e] * self.V
        resBU = [self.e] * self.V

        for v in reversed(self.order):
            resBU[v] = self.adj_bu(accBU[v], v)

            if v == root: break

            p = self.par[v]
            accBU[p] = self.merge(accBU[p], resBU[v])
        return accBU, resBU
    
    def top_down(self, resBU:list):
        """ Top-Down DP """
        accTD = [self.e] * self.V
        resTD = [self.e] * self.V

        for p in self.order:
            # 左からaccTDを更新
            ac = resTD[p]
            for v in self.edge[p]:
                accTD[v] = ac
                ac = self.merge(ac, resBU[v])

            # 右からaccTDを更新
            ac = self.e
            for v in reversed(self.edge[p]):
                accTD[v] = self.merge(accTD[v], ac)
                ac = self.merge(ac, resBU[v])
                
                resTD[v] = self.adj_td(accTD[v], v, p)
        return resTD
    
    def solve(self):
        self.topological_sort()
        self.subtree_size()
        accBU, resBU = self.bottom_up()
        resTD = self.top_down(resBU)
        res = [self.adj_fin(self.merge(a, b), v) for v,(a,b) in enumerate(zip(accBU, resTD))]
        return res

#########################################################################################
N = int(input())
MOD = 10 ** 9 + 7

fact = [1] * (N + 1) # fact[n]: n!
factinv = [1] * (N + 1) # n!の逆元
for i in range(N):
    fact[i + 1] = fact[i] * (i + 1) % MOD
factinv[-1] = pow(fact[-1], MOD - 2, MOD)
for i in range(N - 1, -1, -1):
    factinv[i] = factinv[i + 1] * (i + 1) % MOD
inv = lambda n: fact[n - 1] * factinv[n] % MOD # inv[n]: nの逆元

def main():
    RR = ReRooting(N, 1)
    for _ in range(N - 1):
        a, b = map(int, input().split())
        RR.add_edge(a - 1, b- 1)

    print(*RR.solve(), sep="\n")

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
 
class Combination:
    def __init__(self, size, mod=10**9 + 7):
        self.size = size + 2
        self.mod = mod
        self.fact = [1, 1] + [0] * size
        self.factInv = [1, 1] + [0] * size
        self.inv = [0, 1] + [0] * size
 
        for i in range(2, self.size):
            self.fact[i] = self.fact[i - 1] * i % self.mod
            self.inv[i] = -self.inv[self.mod % i] * (self.mod // i) % self.mod
            self.factInv[i] = self.factInv[i - 1] * self.inv[i] % self.mod
 
    def npr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * self.factInv[n - r] % self.mod
 
    def ncr(self, n, r):
        if n < r or n < 0 or r < 0:
            return 0
        return self.fact[n] * (self.factInv[r] * self.factInv[n - r] % self.mod) % self.mod
 
    def nhr(self, n, r):  # 重複組合せ
        return self.ncr(n + r - 1, n - 1)
 
    def factN(self, n):
        if n < 0:
            return 0
        return self.fact[n]
 
    def factInvN(self, n):
        if n < 0:
            return 0
        return self.factInv[n]
 
N = int(input())
MOD = 10**9 + 7
comb = Combination(N + 100)
 
edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    fr, to = map(int, input().split())
    edges[fr].append(to)
    edges[to].append(fr)
 
order = []
parent = [0] * (N + 1)
st = [1]
while st:
    now = st.pop()
    order.append(now)
    for to in edges[now]:
        if to == parent[now]:
            continue
        st.append(to)
        parent[to] = now
 
size = [1] * (N + 1)
for v in order[::-1]:
    size[parent[v]] += size[v]
 
dpLeaf = [1] * (N + 1)
for v in order[:: -1]:
    pr = parent[v]
    dpLeaf[v] = dpLeaf[v] * comb.fact[size[v] - 1] % MOD
    dpLeaf[pr] = dpLeaf[pr] * dpLeaf[v] * comb.factInv[size[v]] % MOD
 
ans = [0] * (N + 1)
ans[1] = dpLeaf[1]
for v in order[1:]:
    pr = parent[v]
    ans[v] = ans[pr] * comb.inv[N - size[v]] * size[v] % MOD
 
print(*(ans[1:]), sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)


def input():
    return sys.stdin.readline()


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

mod = 10**9+7

kkai = [1]
for i in range(1, 2*10 ** 5):
    kkai.append(kkai[-1] * i % mod)


def kai(x, p=mod):
    return kkai[x]


def comb(a, b, p=mod):
    if a < 0 or b < 0:
        return 0
    elif a < b:
        return 0
    if b == 0:
        return 1
    c = 1
    c *= kai(a, p)
    c *= pow(kai(b, p), p - 2, p)
    c *= pow(kai(a - b, p), p - 2, p)
    return c % p


child = [0] * n


def dfs1(i=0, r=-1):
    s = 1
    for j in e[i]:
        if j == r:
            continue
        s += dfs1(j, i)
    child[i] = s
    return s


dfs1()
a = [0] * n


def dfs2(i=0, r=-1):
    s = kai(child[i]-1)
    t = 1
    for j in e[i]:
        if j == r:
            continue
        s *= dfs2(j, i)
        s %= mod
        t *= kai(child[j])
        t %= mod
    s *= pow(t, mod - 2, mod)
    s %= mod
    a[i] = s
    return s


dfs2()
b = [0] * n


def dfs3(i=0, r=-1):
    if r == -1:
        b[i] = a[i]
    else:
        s = b[r] * child[i] % mod
        s *= pow(n-child[i], mod - 2, mod)
        s %= mod
        b[i] = s

    for j in e[i]:
        if j == r:
            continue
        dfs3(j, i)


dfs3()
print("\n".join(map(str, b)))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
from collections import deque

MOD = 10**9 + 7
N = int(input())
tree = dict(zip(range(N), [[] for i in range(N)]))
edge_id = {}
c = 0
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  tree[a].append(b)
  tree[b].append(a)
  edge_id[(a, b)] = c
  edge_id[(b, a)] = c + 1
  c += 2

# 部分木のサイズ
# 頂点v1 -> v2の向きを考えたときに、頂点v2を根とする部分木のサイズを計算する
size = [0] * 2*(N-1)
def calc_size(v1, v2):
  global size
  idx = edge_id[(v1, v2)]
  if size[idx]:
    return size[idx]
  children = tree[v2]
  s = 1
  for child in children:
    if child == v1:
      continue
    s += calc_size(v2, child)
  size[idx] = s
  idx_inv = edge_id[(v2, v1)]
  size[idx_inv] = N - s
  return s

# 階乗、組合せの計算
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def comb(n, r, mod=MOD):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

# 頂点iに1を書くときの場合の数
ans = [0] * N
dp = [0] * 2*(N-1)
def calc_dp(v1, v2):
  global dp
  idx = edge_id[(v1, v2)]
  if dp[idx]:
    return dp[idx]
  children = tree[v2]
  s = calc_size(v1, v2)
  res = g1[s-1]
  for child in children:
    if child == v1:
      continue
    res *= calc_dp(v2, child)
    res %= MOD
    _s = calc_size(v2, child)
    res *= g2[_s]
    res %= MOD
  dp[idx] = res
  return res

def calc_ans(i):
  global ans
  global dp
  if ans[i]:
    return ans[i]
  children = tree[i]
  res = g1[N-1]
  for child in children:
    res *= calc_dp(i, child)
    res %= MOD
    _s = calc_size(i, child)
    res *= g2[_s]
    res %= MOD
  ans[i] = res
  return res

# 頂点0に1と記入する場合の数を求める
calc_ans(0)
# そこからはbfsで子に伝搬させていく
# 伝搬の漸化式はnode -> childのとき
# ans[child] = ans[node] * size[(node, child)]/size[(child, node)]
d = deque([[0, -1]])
c = 0
while d:
  node, par = d.popleft()
  c += 1
  children = tree[node]
  for child in children:
    if child == par:
      continue
    s1 = calc_size(node, child)
    s2 = N - s1
    r = (g1[s1] * g1[s2-1] % MOD) * (g2[s1-1] * g2[s2] % MOD) % MOD
    ans[child] = ans[node] * r % MOD
    d.append([child, node])

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
from collections import deque

MOD = 10**9 + 7
N = int(input())
tree = dict(zip(range(N), [[] for i in range(N)]))
edge_id = {}
c = 0
for i in range(N-1):
  a, b = map(int, input().split())
  a, b = a-1, b-1
  tree[a].append(b)
  tree[b].append(a)
  edge_id[(a, b)] = c
  edge_id[(b, a)] = c + 1
  c += 2

# 部分木のサイズ
# 頂点v1 -> v2の向きを考えたときに、頂点v2を根とする部分木のサイズを計算する
size = [0] * 2*(N-1)
def calc_size(v1, v2):
  global size
  idx = edge_id[(v1, v2)]
  if size[idx]:
    return size[idx]
  children = tree[v2]
  s = 1
  for child in children:
    if child == v1:
      continue
    s += calc_size(v2, child)
  size[idx] = s
  idx_inv = edge_id[(v2, v1)]
  size[idx_inv] = N - s
  return s

# 階乗、組合せの計算
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
MOD = 10**9+7
for i in range(2, 2*10**5+1):
    g1.append((g1[-1] * i) % MOD)
    inverse.append((-inverse[MOD % i] * (MOD // i)) % MOD)
    g2.append((g2[-1] * inverse[-1]) % MOD)

def comb(n, r, mod=MOD):
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    return g1[n] * g2[r] * g2[n-r] % mod

# 頂点iに1を書くときの場合の数
ans = [0] * N
dp = [0] * 2*(N-1)
def calc_dp(v1, v2):
  global dp
  idx = edge_id[(v1, v2)]
  if dp[idx]:
    return dp[idx]
  children = tree[v2]
  s = calc_size(v1, v2)
  res = g1[s-1]
  for child in children:
    if child == v1:
      continue
    res *= calc_dp(v2, child)
    res %= MOD
    _s = calc_size(v2, child)
    res *= g2[_s]
    res %= MOD
  dp[idx] = res
  return res

def calc_ans(i):
  global ans
  global dp
  if ans[i]:
    return ans[i]
  children = tree[i]
  res = g1[N-1]
  for child in children:
    res *= calc_dp(i, child)
    res %= MOD
    _s = calc_size(i, child)
    res *= g2[_s]
    res %= MOD
  ans[i] = res
  return res

# 頂点0に1と記入する場合の数を求める
calc_ans(0)
# そこからはbfsで子に伝搬させていく
# 伝搬の漸化式はnode -> childのとき
# ans[child] = ans[node] * size[(node, child)]/size[(child, node)]
d = deque([[0, -1]])
c = 0
while d:
  node, par = d.popleft()
  c += 1
  children = tree[node]
  for child in children:
    if child == par:
      continue
    s = calc_size(node, child)
    r = s * pow(N-s, MOD-2, MOD) % MOD
    ans[child] = ans[node] * r % MOD
    d.append([child, node])

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7

## nCkのmodを求める関数
# テーブルを作る(前処理)
max = 2 * 10**5 + 10
fac, finv, inv = [0]*max, [0]*max, [0]*max

def comInit(max):
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1

    for i in range(2,max):
      fac[i] = fac[i-1]* i% mod
      inv[i] = mod - inv[mod%i] * (mod // i) % mod
      finv[i] = finv[i-1] * inv[i] % mod

comInit(max)

# 二項係数の計算
def com(n,k):
    if(n < k):
        return 0
    if( (n<0) | (k < 0)):
        return 0
    return fac[n] * (finv[k] * finv[n-k] % mod) % mod

# 前準備
import sys
input = sys.stdin.readline
from collections import deque

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

def calc(a,b):
    p_a, e_a = a
    p_b, e_b = b
    e = e_a + e_b
    p = p_a * p_b * com(e,e_a) % mod
    return(p,e)

# calc1 の定義
def calc1(c,p):
    p_num, e_num = 1,0
    for i in graph[c]:
        if i == p:
            continue
        p_num,e_num = calc((p_num, e_num) , dp1[i] )
    e_num += 1
    dp1[c] = (p_num, e_num)

# calc2 の定義
def calc2(p):
    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [(1,0)]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [(1,0)]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        p_tmp,e_tmp = calc(a,b)
        prod.append( (p_tmp, e_tmp) )


    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            p_tmp,e_tmp = x
            dp2[c] = (p_tmp,e_tmp+1)



# 根から探索して親と探索順を記録
root = 1
order = []
parent = [0] * (n+1)
stack = deque()
stack.append(root)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        stack.append(y)
        parent[y] = x

# 親→子の値を算出
dp1 = [None] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])

# 子→親の値を算出　累積和チックにすることでうに対策。
dp2 = [None] * (n+1)
dp2[root] = (1,0)
for i in order:
    calc2(i)

for i in range(1,n+1):
    p1,e1 = dp1[i]
    p2,e2 = dp2[i]
    e1 -= 1
    ans = calc((p1,e1), (p2,e2))[0]
    print(ans)

Submission status: Accepted

Solution code:
n = int(input()); arr = [list(map(int,input().split())) for _ in range(n-1)]

graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1); graph[b-1].append(a-1)

parents = [-1]*n
children = [[] for _ in range(n)]
orders = []
stack = [0]
flags = [True] * n; flags[0] = False
while stack:
    tmp = stack.pop()
    orders.append(tmp)
    for node in graph[tmp]:
        if flags[node]:
            flags[node] = False
            children[tmp].append(node)
            stack.append(node)
            parents[node] = tmp

mod = 10**9+7
fac = [1]*(n+1)
inv = [1]*(n+1)
ifac = [1]*(n+1)
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = (- (mod//i)*inv[(mod%i)]) % mod
    ifac[i] = ifac[i-1] * inv[i] % mod

size = [1] * n;dp = [1] * n
for parent in orders[::-1]:
    for child in children[parent]:
        size[parent] += size[child]
        dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
    dp[parent] = dp[parent] * fac[size[parent]-1] % mod

size2 = [n-i+1 for i in size];dp2 = [1] * n; dp2[0] = dp[0]
for parent in orders[1:]:
    child = parents[parent]
    dp2[parent] = dp2[parent] * size[parent] * dp2[child] * inv[size2[parent]-1] % mod
    
for i in range(n):
    print(dp2[i])

Submission status: Accepted

Solution code:
n = int(input()); arr = [list(map(int,input().split())) for _ in range(n-1)]
graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1); graph[b-1].append(a-1)


mod = 10**9+7
fac = [1]*(n+1)
inv = [1]*(n+1)
ifac = [1]*(n+1)
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = (- (mod//i)*inv[(mod%i)]) % mod
    ifac[i] = ifac[i-1] * inv[i] % mod

parents = [-1]*n
children = [[] for _ in range(n)]
orders = []
stack = [0]
flags = [True] * n; flags[0] = False
while stack:
    tmp = stack.pop()
    orders.append(tmp)
    for node in graph[tmp]:
        if flags[node]:
            flags[node] = False
            children[tmp].append(node)
            stack.append(node)
            parents[node] = tmp

size = [1] * n
dp = [1] * n
for parent in orders[::-1]:
    for child in children[parent]:
        size[parent] += size[child]
        dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
    dp[parent] = dp[parent] * fac[size[parent]-1] % mod


size2 = [n-i+1 for i in size]
dp2 = [1] * n; dp2[0] = dp[0]
for parent in orders[1:]:
    child = parents[parent]
    dp2[parent] = dp2[parent] * size[parent] * dp2[child] * inv[size2[parent]-1] % mod
    
for i in range(n):
    print(dp2[i])

Submission status: Accepted

Solution code:
n = int(input()); arr = [list(map(int,input().split())) for _ in range(n-1)]
graph = [[] for _ in range(n)]
for a,b in arr:
    graph[a-1].append(b-1); graph[b-1].append(a-1)


mod = 10**9+7
fac = [1]*(n+1)
inv = [1]*(n+1)
ifac = [1]*(n+1)
for i in range(2,n+1):
    fac[i] = fac[i-1] * i % mod
    inv[i] = (- (mod//i)*inv[(mod%i)]) % mod
    ifac[i] = ifac[i-1] * inv[i] % mod

parents = [-1]*n
children = [[] for _ in range(n)]
orders = []
stack = [0]
flags = [True] * n; flags[0] = False
while stack:
    tmp = stack.pop()
    orders.append(tmp)
    for node in graph[tmp]:
        if flags[node]:
            flags[node] = False
            children[tmp].append(node)
            stack.append(node)
            parents[node] = tmp

size = [1] * (n+1)
dp = [1] * (n+1)    
for child in orders[::-1]:
    parent = parents[child]
    size[parent] += size[child]
    dp[child] = dp[child] * fac[size[child]-1] % mod
    dp[parent] = dp[parent] * dp[child] * ifac[size[child]] % mod
_ = size.pop();_ = dp.pop()

size2 = [n-i+1 for i in size]
dp2 = [1] * n; dp2[0] = dp[0]
for parent in orders[1:]:
    child = parents[parent]
    dp2[parent] = dp2[parent] * size[parent] * dp2[child] * inv[size2[parent]-1] % mod
    
for i in range(n):
    print(dp2[i])