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
input = sys.stdin.readline

#######################################
mod = 10**9+7
MAX_N = 200000

fact = [1]
fact_inv = [0]*(MAX_N+4)
for i in range(MAX_N+3):
    fact.append(fact[-1]*(i+1)%mod)

fact_inv[-1] = pow(fact[-1],mod-2,mod)
for i in range(MAX_N+2,-1,-1):
    fact_inv[i] = fact_inv[i+1]*(i+1)%mod


def mod_comb_k(n,k,mod):
    return fact[n] * fact_inv[k] % mod * fact_inv[n-k] %mod
#######################################

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

#DFS
order = []
par = [-1]*n
tank = [0]
while tank:
    pele = tank.pop()
    order.append(pele)
    for e in edge[pele]:
        if e == par[pele]:
            continue
        tank.append(e)
        par[e] = pele

size = [1]*n
for e in order[::-1]:
    if e == 0:
        break
    size[par[e]] += size[e]


dp = [1]*n
for e in order[::-1]:
    dp[e] = dp[e] * fact[size[e]-1] % mod
    if e == 0:
        break
    dp[par[e]] = (dp[par[e]] * dp[e] % mod) * fact_inv[size[e]] % mod


dp2 = [0]*n                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                      
dp2[0] = dp[0]
for e in order[1::]:
    p = par[e]
    tmp = (dp2[p] * fact[n-1-size[e]] % mod) * fact[size[e]] % mod
    red = ( tmp * fact_inv[n-1] % mod ) * pow(dp[e],mod-2,mod) % mod
    
    size_red = n - size[e]
    tmp = (dp[e] * red % mod ) * fact[n-1] % mod
    dp2[e] = (tmp * fact_inv[size[e]-1] % mod) * fact_inv[size_red] % mod

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

Submission status: Accepted

Solution code:
n = int(input())
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)
mod = 10**9 + 7
factorial = [1]*(n+1)
factorial_inv = [1]*(n+1)
for i in range(1,n+1):
    factorial[i] = factorial[i-1]*i%mod
factorial_inv[n] = pow(factorial[n],mod-2,mod)
for i in range(n,0,-1):
    factorial_inv[i-1] = factorial_inv[i]*i%mod

pa = [0]*(n+1)
dp = [1]*(n+1)
size = [1]*(n+1)
checked = []
stack = [i]
while stack:
    a = stack.pop()
    checked.append(a)
    for j in graph[a]:
        if pa[a] == j:   
            continue
        else:
            stack.append(j)
            pa[j] = a

for i in checked[::-1]:
    p = pa[i]
    s = size[i]
    dp[i] *= factorial[s-1]
    dp[i] %= mod
    dp[p] *= dp[i]*factorial_inv[s]
    dp[p] %= mod
    size[p] += s

size_ = [n-i+1 for i in size]
dp_ = [1]*(n+1)
for i in checked[1:]:
    p = pa[i]
    dp_[i] *= dp[p]
    dp_[i] *= factorial_inv[size[p]-1]
    dp_[i] *= pow(dp[i],mod-2,mod)
    dp_[i] *= factorial[size[i]]
    dp_[i] *= dp_[p]
    dp_[i] *= factorial_inv[size_[p]-1]
    dp_[i] *= factorial[size_[i]-2]
    dp_[i] %= mod
    
for i in range(1,n+1):
    ans = factorial[n-1]*dp[i]*dp_[i]*factorial_inv[size[i]-1]*factorial_inv[size_[i]-1]
    ans %= mod
    print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

# nCk
## 0!~n!をmodしつつ求める
def fact_all(n,M=mod):
    f = [1]*(n+1)
    ans = 1
    for i in range(1,n+1):
        ans = (ans*i)%M
        f[i] = ans
    return f

## inv(0!)~inv(n!)をmodしつつ求める
def fact_inv_all(fact_all,M=mod):
    N = len(fact_all)
    finv = [0]*N
    finv[-1] = pow(fact_all[-1],M-2,M)
    for i in range(N-1)[::-1]:
        finv[i] = finv[i+1]*(i+1)%M
    return finv

## nCkをmodしつつ返す
def nCk(n,k,fact_list,inv_list,M=mod):
    return (((fact_list[n]*inv_list[k])%M)*inv_list[n-k])%M

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if not directed:
            pt[t[i]-1].append(s[i]-1)
    return pt

def order_dfs(pt,N):
    s = 0
    parent = [-1]*N
    order = [s]
    visited = [False]*N
    visited[s] = True
    S = [s]
    while S:
        v = S.pop()
        for u in pt[v]:
            if not visited[u]:
                visited[u] = True
                order.append(u)
                parent[u] = v
                S.append(u)
    return order,parent

N = I()
a,b = LIR(N-1,2)
pt = edges_to_pt(a,b,N)

fl = fact_all(N)
il = fact_inv_all(fl)

order,parent = order_dfs(pt,N)
order = order[::-1]

# 順方向の部分木について数え上げ（葉側から順に行う）
visited = [False]*N
size = [0]*N
dp = [1]*N
for v in order:
    # 葉の処理
    if len(pt[v]) == 1 and not visited[pt[v][0]]:
        dp[v] = 1
        size[v] = 1
    # 葉以外での処理
    else:
        size_v = 0
        for u in pt[v]:
            size_v += size[u]
            dp[v] *= dp[u]*il[size[u]]
            dp[v] %= mod
        dp[v] *= fl[size_v]
        dp[v] %= mod
        size[v] = size_v + 1
    visited[v] = True

# 逆側の部分木について数え上げ（根側から順に行う）
dp2 = [1]*N
for v in order[::-1]:
    p = parent[v]
    # 根の処理
    if p == -1:
        dp2[v] = 1
    # 根以外での処理
    else:
        dp2[v] = (((dp[p]*dp2[p]*pow(dp[v],mod-2,mod))%mod
                    *fl[N-1-size[v]]*il[size[p]-1])%mod
                    *fl[size[v]]*il[N-size[p]])%mod

# 部分木の情報を統合
for v in range(N):
    ans = (fl[N-1]*il[size[v]-1]*il[N-size[v]]*dp[v]*dp2[v])%mod
    print(ans)

Submission status: Accepted

Solution code:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200000):
        fact.append(fact[-1]*i % mod)
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    g2 = [set(i) for i in g]
    child = [1]*n  # 子の数
    q = [-1, 0]
    while len(q) > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
            if len(q) > 1:
                child[q[-1]] += child[i]
    rank = [(j, i) for i, j in enumerate(child)]
    rank = [j for i, j in sorted(rank)]
    dp = [1]*n
    for i in rank:
        c = child[i]
        ans = fact[c-1]
        temp = 1
        for j in g[i]:
            if child[j] < c:
                ans = ans*dp[j] % mod
                temp = temp*fact[child[j]] % mod
        dp[i] = ans*pow(temp, mod-2, mod) % mod
    dp2 = [0]*n
    dp2[0] = dp[0]
    g2 = [set(i) for i in g]
    q = [-1, 0]
    while len(q) > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            c = child[j]
            temp = fact[n-c]*fact[c-1]
            dp2[j] = dp2[i]*(fact[c]*fact[n-c-1])*pow(temp, mod-2, mod) % mod
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
            if len(q) > 1:
                child[q[-1]] += child[i]

    for i in dp2:
        print(i)


main()

Submission status: Accepted

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

from collections import deque

class Factorial:
    def __init__(self, n, mod):
        self.f = [1]
        self.mod = mod
        for j in range(1, n + 1):
            self.f.append(self.f[-1] * j % mod)
        self.i = [pow(self.f[-1], mod - 2, mod)]
        for j in range(n, 0, -1):
            self.i.append(self.i[-1] * j % mod)
        self.i.reverse()
    def factorial(self, j):
        return self.f[j]
    def ifactorial(self, j):
        return self.i[j]
    def comb(self, n, k):
        return self.f[n] * self.i[n - k] % self.mod * self.i[k] % self.mod if n >= k else 0


MOD = 10 ** 9 + 7


N = int(input())

c = Factorial(N + 2, MOD)

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)

edge_num = [len(G[i]) for i in range(N + 1)]

que = deque()
check = [0] * (N + 1)
order = []
o_append =order.append
q_pop = que.pop
q_append = que.append

q_append((1, 0))
check[1] = 1
while que:
    now = q_pop()
    o_append(now)
    for next_ in G[now[0]]:
        if check[next_] == 0:
            q_append((next_, now[0]))
            check[next_] = 1

# print (order)

size1 = [0] * (N + 1) #自身を頂点とする部分木のサイズ、木の根は頂点0
dp1 = [1] * (N + 1)
for child, parent in order[::-1]:
    dp1[child] *= c.factorial(size1[child])
    dp1[child] %= MOD
    s = size1[child] + 1
    size1[parent] += s
    dp1[parent] *= c.ifactorial(s) * dp1[child]
    dp1[parent] %= MOD

# print (size1)
# print (dp1)

size2 = [N - 2 - x for x in size1]
dp2 = [1] * (N + 1)

# print (size1)
# print (size2)
for child, parent in order[1:]:
    x = dp1[parent]
    x *= dp2[parent]
    x *= c.ifactorial(size1[parent])
    x *= c.factorial(size1[child] + 1)
    x *= pow(dp1[child], MOD - 2, MOD) #割り算
    x *= c.factorial(size2[child])
    x *= c.ifactorial(size2[parent] + 1)
    dp2[child] = x % MOD

# print (dp2)

for x1, x2, s1, s2 in zip(dp1[1:], dp2[1:], size1[1:], size2[1:]):
    s2 += 1
    x = x1 * x2 * c.factorial(s1 + s2) * c.ifactorial(s1) * c.ifactorial(s2) % MOD
    print (x)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*(N-1)]

mod = 10**9+7

m = 10**5*2 +10 
fac = [1]*m
ninv = [1]*m
finv = [1]*m
for i in range(2,m):
    fac[i] = fac[i-1]*i%mod
    ninv[i] = (-(mod//i)*ninv[mod%i])%mod
    finv[i] = finv[i-1]*ninv[i]%mod

E = [[] for _ in [0]*N]
Ef = [[] for _ in [0]*N]
Eb = [[] for _ in [0]*N]
for a,b in AB:
    a-=1
    b-=1
    E[a].append(b)
    E[b].append(a)
done = [False]*N
done[0] = True
q = [0]
while q:
    j = q.pop()
    for k in E[j]:
        if done[k]: continue
        done[k] = True
        q.append(k)
        Ef[j].append(k)
        Eb[k].append(j)
Vf = [None]*N
Mf = [None]*N
def getf(i):
    if Mf[i]!=None:
        return Mf[i]
    Mc = [getf(j) for j in Ef[i]]
    Vc = [Vf[j] for j in Ef[i]]
    Vf[i] = 1 + sum(Vc)
    Mf[i] = fac[Vf[i]-1]
    for mc,vc in zip(Mc,Vc):
        Mf[i] *= (mc*finv[vc])%mod
        Mf[i] %= mod
    return Mf[i]

def getp(i):
    if i==0: return 0
    p = Eb[i][0]
    vp = Vf[p]
    vi = Vf[i]
    ret = ans[p]
    ret *= (((fac[vi]*fac[N-1-vi])%mod)*finv[N-1])%mod
    ret %= mod
    ret *= pow(Mf[i],mod-2,mod)
    ret %= mod
    return ret

ans = [0]*N
ans[0] = getf(0)
q = Ef[0][:]

while q:
    i = q.pop()
    V = [N - Vf[i]]
    M = [getp(i)]
    for j in Ef[i]:
        q.append(j)
        V.append(Vf[j])
        M.append(Mf[j])
    tmp = fac[N-1]
    for mc,vc in zip(M,V):
        tmp *= (mc*finv[vc])%mod
        tmp %= mod
    ans[i] = tmp

for out in ans:
    print(out)

Submission status: Accepted

Solution code:
def main():
  from collections import deque
  N = int(input())
  ab = [list(map(int,input().split())) for _ in range(N-1)]
  mod = 10**9+7
  fact = [1]*(N+1)
  fact_inv = [1]*(N+1)
  for i in range(1,N+1):
    fact[i] = (fact[i-1]*i)%mod

  fact_inv[-1] = pow(fact[-1], mod-2, mod)
  for i in range(N,0,-1):
    fact_inv[i-1] = fact_inv[i] * i % mod

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

  parents = [0]*(N+1)
  q = deque([])
  s = deque([1])
  while s:
    x = s.pop()
    q.append(x)
    for y in g[x]:
      if y==parents[x]:
        continue
      else:
        parents[y] = x
        s.append(y)

  q = list(q)
  size_forward = [0]*(N+1)
  dp_forward = [1]*(N+1)
  for i in q[::-1]:
    p = parents[i]
    s = size_forward[i] + 1
    size_forward[p] += s
    dp_forward[i] *= fact[size_forward[i]]
    dp_forward[p] *= dp_forward[i] * fact_inv[s]
    dp_forward[p] %= mod

  size_back = [N-1-i for i in size_forward]
  dp_back = [1]*(N+1)
  for i in q[1:]:
    p = parents[i]
    x = dp_back[p]
    x *= fact_inv[size_back[p]]
    x *= dp_forward[p]
    x *= fact_inv[size_forward[p]]
    x *= fact[size_forward[i]+1]
    x *= pow(dp_forward[i],mod-2,mod)
    x *= fact[size_back[i]-1]
    dp_back[i] = x % mod

  for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
    ans = b * d * fact[a+c] * fact_inv[a] * fact_inv[c]
    ans %= mod
    print(ans)
    
main()

Submission status: Accepted

Solution code:
from collections import deque
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
mod = 10**9+7
fact = [1]*(N+1)
fact_inv = [1]*(N+1)
for i in range(1,N+1):
  fact[i] = (fact[i-1]*i)%mod
  
fact_inv[-1] = pow(fact[-1], mod-2, mod)
for i in range(N,0,-1):
  fact_inv[i-1] = fact_inv[i] * i % mod

g = [deque([]) for _ in range(N+1)]
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  
parents = [0]*(N+1)
q = deque([])
s = deque([1])
while s:
  x = s.pop()
  q.append(x)
  for y in g[x]:
    if y==parents[x]:
      continue
    else:
      parents[y] = x
      s.append(y)
      
q = list(q)
size_forward = [0]*(N+1)
dp_forward = [1]*(N+1)
for i in q[::-1]:
  p = parents[i]
  s = size_forward[i] + 1
  size_forward[p] += s
  dp_forward[i] *= fact[size_forward[i]]
  dp_forward[p] *= dp_forward[i] * fact_inv[s]
  dp_forward[p] %= mod
  
size_back = [N-1-i for i in size_forward]
dp_back = [1]*(N+1)
for i in q[1:]:
  p = parents[i]
  x = dp_back[p]
  x *= fact_inv[size_back[p]]
  x *= dp_forward[p]
  x *= fact_inv[size_forward[p]]
  x *= fact[size_forward[i]+1]
  x *= pow(dp_forward[i],mod-2,mod)
  x *= fact[size_back[i]-1]
  dp_back[i] = x % mod
  
for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
  ans = b * d * fact[a+c] * fact_inv[a] * fact_inv[c]
  ans %= mod
  print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
mod = 10 ** 9 + 7
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

class Factorial:
  def __init__(self, n, mod):
    self.f = [1]
    for i in range(1, n + 1):
      self.f.append(self.f[-1] * i % mod)
    self.i = [pow(self.f[-1], mod - 2, mod)]
    for i in range(1, n + 1)[: : -1]:
      self.i.append(self.i[-1] * i % mod)
    self.i.reverse()
  def factorial(self, i):
    return self.f[i]
  def ifactorial(self, i):
    return self.i[i]
  def combi(self, n, k):
    return self.f[n] * self.i[n - k] % mod * self.i[k] % mod

f = Factorial(N, mod)

class ReRooting:
  def ReRfunc(self, x):
    y = self.parent[x]
    return self.res[y] * self.size[x] % mod * pow(self.n - self.size[x], mod - 2, mod) % mod

  def __init__(self, n, e):
    self.n = n
    self.e = e
    self.vis = [0] * (n + 1)
    self.order = []
    self.parent = [-1] * (n + 1)
    self.ddp = [0] * (n + 1)
    self.udp = [0] * (n + 1)
    self._dfs()
    self.size = [1] * (n + 1)
    self.order.reverse()
    for x in self.order[: -1]: self.size[self.parent[x]] += self.size[x]
    self.res = [0] * (n + 1)
    #初期化の値
    self.res[1] = f.factorial(N)
    for x in range(1, N + 1): self.res[1] = self.res[1] * pow(self.size[x], mod - 2, mod) % mod

    self.order.reverse()
    for x in self.order[1: ]: self.res[x] = self.ReRfunc(x)

  def _dfs(self):
    s = [1]
    while len(s):
      x = s.pop()
      self.vis[x] = 1
      self.order.append(x)
      for y in self.e[x]:
        if self.vis[y]: continue
        s.append(y)
        self.parent[y] = x

  def Size(self, x):
    return self.size[x]

  def Query(self, x):
    return self.res[x]

rer = ReRooting(N, e)
for x in range(1, N + 1): print(rer.Query(x) % mod)

Submission status: Accepted

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

N=int(input())
E=[[] for i in range(N+1)]

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

mod=10**9+7

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

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

FACT_INV.reverse()

def Combi(a,b):
    if 0<=b<=a:
        return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod
    else:
        return 0

Q=[1]
SORTED=[1]
USE=[0]*(N+1)
USE[1]=1
P=[-1]*(N+1)

while Q:
    x=Q.pop()

    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            SORTED.append(to)
            Q.append(to)
            P[to]=x

FROM1=[-1]*(N+1)
FROM2=[-1]*(N+1)

for x in SORTED[::-1]:
    if len(E[x])==1 and x!=1:
        FROM1[x]=1
        FROM2[x]=1
    else:
        L=[]
        SUML=0
        A=1
        for to in E[x]:
            if to==P[x]:
                continue
            L.append(FROM1[to])
            SUML+=FROM1[to]
            A=A*FROM2[to]%mod
        #print(x,L)
        FROM1[x]=SUML+1
        S=SUML

        for l in L:
            A=A*Combi(S,l)%mod
            S-=l
        FROM2[x]=A

TO1=[-1]*(N+1)
TO2=[-1]*(N+1)
TO2[1]=1

for x in SORTED:
    if x!=1 and len(E[x])==1:
        continue
    
    SS=1
    L=[]
    SUML=0
    for to in E[x]:
        if to==P[x]:
            continue
        
        SS=SS*FROM2[to]%mod
        L.append(FROM1[to])
        SUML+=FROM1[to]

    L.append(N-1-SUML)
    SUML+=N-1-SUML
    A=1
    S=SUML
    for l in L:
        A=A*Combi(S,l)%mod
        S-=l

    for to in E[x]:
        if to==P[x]:
            continue
        
        B=A*SS*pow(FROM2[to],mod-2,mod)*TO2[x]%mod

        TO2[to]=B*pow(Combi(SUML,FROM1[to]),mod-2,mod)%mod

for i in range(1,N+1):
    ANS=TO2[i]

    L=[]
    SUML=0

    for to in E[i]:
        if to==P[i]:
            continue
        ANS=ANS*FROM2[to]%mod
        L.append(FROM1[to])
        SUML+=FROM1[to]

    L.append(N-1-SUML)
    SUML+=N-1-SUML
    S=SUML
    for l in L:
        ANS=ANS*Combi(S,l)%mod
        S-=l
    print(ANS%mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def dfs(v):
    global MOD
    childs = 0
    var = 1
    for e in edge[v]:
        if path[e] == 0:
            path[e] = 1
            nc, nvar = dfs(e)
            childs += nc
            V[v][e] = (nc, nvar)
            var *= nvar
            var %= MOD
            var *= invs[nc]
            var %= MOD
    var *= modFacts[childs]
    var %= MOD
    dp[v] = (childs, var)
    return childs + 1, var


def dfs2(v, pn, pVar):
    global MOD
    oNodes, oVar = dp[v]
    tNodes = pn + oNodes
    tVar = (oVar * pVar) % MOD
    tVar *= invs[oNodes]
    tVar %= MOD
    tVar *= modFacts[tNodes]
    tVar %= MOD
    tVar *= invs[pn]
    tVar %= MOD

    dp[v] = (tNodes, tVar)

    for e in V[v].keys():
        eNodes, eVar = V[v][e]
        nVar = (tVar * invs[tNodes]) % MOD
        nVar *= modFacts[eNodes]
        nVar %= MOD
        nVar *= modFacts[tNodes - eNodes]
        nVar %= MOD
        nVar *= pow(eVar, MOD - 2, MOD)
        nVar %= MOD
        dfs2(e, tNodes - eNodes + 1, nVar)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

modFacts, invs = prepare(N)

V = [{} for _ in range(N)]
path = [0] * N
dp = [None] * N
path[0] = 1
dfs(0)
dfs2(0, 0, 1)


for i in range(N):
    print(dp[i][1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def dfs(v):
    global MOD
    childs = 0
    var = 1
    for e in edge[v]:
        if path[e] == 0:
            path[e] = 1
            nc, nvar = dfs(e)
            childs += nc
            V[v][e] = (nc, nvar)
            var *= nvar
            var %= MOD
            var *= invs[nc]
            var %= MOD
    var *= modFacts[childs]
    var %= MOD
    dp[v] = (childs, var)
    return childs + 1, var


def dfs2(v, pn, pVar):
    global MOD
    oNodes, oVar = dp[v]
    tNodes = pn + oNodes
    tVar = (oVar * pVar) % MOD
    tVar *= invs[oNodes] * modFacts[tNodes] * invs[pn]
    tVar %= MOD

    dp[v] = (tNodes, tVar)

    for e in V[v].keys():
        eNodes, eVar = V[v][e]
        nVar = (tVar * invs[tNodes] * modFacts[eNodes] * modFacts[tNodes - eNodes]) % MOD
        nVar *= pow(eVar, MOD - 2, MOD)
        nVar %= MOD
        dfs2(e, tNodes - eNodes + 1, nVar)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

modFacts, invs = prepare(N)

V = [{} for _ in range(N)]
path = [0] * N
dp = [None] * N
path[0] = 1
dfs(0)
dfs2(0, 0, 1)


for i in range(N):
    print(dp[i][1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


def dfs(v):
    global MOD
    childs = 0
    var = 1
    for e in edge[v]:
        if path[e] == 0:
            path[e] = 1
            nc, nvar = dfs(e)
            childs += nc
            V[v][e] = (nc, nvar)
            var *= nvar
            var %= MOD
            var *= invs[nc]
            var %= MOD
    var *= modFacts[childs]
    var %= MOD
    return childs + 1, var


def dfs2(v):
    global MOD
    tNodes = 0
    tVar = 1
    for n, var in V[v].values():
        tNodes += n
        tVar *= var
        tVar %= MOD
        tVar *= invs[n]
        tVar %= MOD
    tVar *= modFacts[tNodes]
    tVar %= MOD
    dp[v] = tVar

    for e in edge[v]:
        if dp[e] == 0:
            eNodes, eVar = V[v][e]
            nVar = (tVar * invs[tNodes] * modFacts[eNodes] * modFacts[tNodes - eNodes]) % MOD
            nVar *= pow(eVar, MOD - 2, MOD)
            nVar %= MOD
            V[e][v] = (tNodes - eNodes + 1, nVar)
            dfs2(e)


N = int(input())
edge = [[] for _ in range(N)]
for s in sys.stdin.readlines():
    a, b = map(int, s.split())
    edge[a - 1].append(b - 1)
    edge[b - 1].append(a - 1)

modFacts, invs = prepare(N)

V = [{} for _ in range(N)]
path = [0] * N
dp = [0] * N
path[0] = 1
dfs(0)
dfs2(0)


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

Submission status: Accepted

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

def main():
    mod=1000000007
    inv=lambda x: pow(x,mod-2,mod)    
    n=int(input())
    Fact=[1] #階乗
    for i in range(1,n+1):
        Fact.append(Fact[i-1]*i%mod)
    Finv=[0]*(n+1) #階乗の逆元
    Finv[-1]=inv(Fact[-1])
    for i in range(n-1,-1,-1):
        Finv[i]=Finv[i+1]*(i+1)%mod
    Edges=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        Edges[a].append(b)
        Edges[b].append(a)
    Stack=[0]
    Par=[-1]*n
    Order=[]
    while Stack:
        v=Stack.pop()
        Order.append(v)
        for c in Edges[v]:
            if c!=Par[v]:
                Stack.append(c)
                Par[c]=v
    DP=[1]*n
    Size=[1]*n
    for v in Order[::-1]:
        DP[v]*=Fact[Size[v]-1]
        DP[v]%=mod
        p=Par[v]
        if p==-1:
            continue
        Size[p]+=Size[v]
        DP[p]*=DP[v]*Finv[Size[v]]
        DP[p]%=mod
    Ans=[0]*n
    Ans[0]=DP[0]
    for v in Order[1:]:
        p=Par[v]
        Ans[v]=Ans[p]*Size[v]*inv(n-Size[v])%mod
    print(*Ans,sep='\n')
    
if __name__=='__main__':
    main()

Submission status: Accepted

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

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

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

stack = [0]
parent = [-1] * N
order = []
while stack:
    v = stack.pop()
    order.append(v)
    for c in G[v]:
        if c != parent[v]:
            stack.append(c)
            parent[c] = v

dp = [1] * N
size = [1] * N
for v in order[::-1]:
    dp[v] = dp[v] * fact[size[v]-1] % mod
    p = parent[v]
    if p == -1:
        break
    size[p] += size[v]
    dp[p] = dp[p] * dp[v] * fact_inv[size[v]] % mod

ans = [0] * N
ans[0] = dp[0]
for v in order[1:]:
    p = parent[v]
    ans[v] = ans[p] * size[v] * inv(N-size[v]) % mod

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

def cur(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        else:
            par[x]=p
            descend[p]+=cur(x)
    neighbor[p].remove(par[p])
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])%mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

def cur(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        par[x]=p
        descend[p]+=cur(x)
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])%mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])