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,heapq

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

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)
heapq.heapify(q)
sub=[]
heapq.heapify(sub)
while q!=[]:
    while q!=[]:
        x=heapq.heappop(q)
        for p in hen[x]:
            if parent[p]==-1:
                parent[p]=x
                heapq.heappush(sub,p)
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            heapq.heapify(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)

heapq.heapify(q)
sub=[]
heapq.heapify(sub)
while q!=[]:
    while q!=[]:
        x=heapq.heappop(q)
        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
                heapq.heappush(sub,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=[]
            heapq.heapify(sub)
            break

q=[1]
flag2={i:0 for i in range(1,N+1)}
flag2[1]=1
heapq.heapify(q)
sub=[]
heapq.heapify(sub)
while q!=[]:
    while q!=[]:
        x=heapq.heappop(q)
        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
                    heapq.heappush(sub,p)
                else:
                    ans[p]=(ans[x]*pow(N-1,mod-2,mod))%mod

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

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

Submission status: Accepted

Solution code:
import os, sys, bisect, copy
from collections import defaultdict, Counter, deque
from functools import lru_cache   #use @lru_cache(None)
if os.path.exists('in.txt'): sys.stdin=open('in.txt','r')
if os.path.exists('out.txt'): sys.stdout=open('out.txt', 'w')
#
def input(): return sys.stdin.readline()
def mapi(arg=0): return map(int if arg==0 else str,input().split())
#------------------------------------------------------------------
sys.setrecursionlimit(100005)
mod = 1000000007
N=int(2*1e5+100)
sz = [0]*N
dp = [0]*N
gr = defaultdict(list)
def modPow(a,b):
    ans=1
    while (b):
        if (b&1): ans=(ans*a)%mod
        b>>=1
        a=(a*a)%mod
    return ans

def modInv(x):
    return modPow(x,mod-2)

def dfs(x, par):
    sz[x]=1
    for item in gr[x]:
        if item==par: continue
        dfs(item,x)
        sz[x]+=sz[item]

def dfs1(x, par):
    for item in gr[x]:
        if item==par: continue
        dp[item]=(dp[x]*(n-sz[item]))%mod
        dp[item]=(dp[item]*modInv(sz[item]))%mod
        dfs1(item,x)

n = int(input())
for i in range(n-1):
    x,y = mapi()
    gr[x].append(y)
    gr[y].append(x)
dfs(1,0)
dp[1]=1
for i in range(1,n+1):
    dp[1]=(dp[1]*sz[i])%mod
dfs1(1,0)
res = 1
for i in range(1,n+1):
    res = (res*i)%mod
for i in range(1,n+1):
    dp[i]=(res*modInv(dp[i]))%mod
for i in range(1,n+1):
    print(dp[i])

Submission status: Accepted

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

MOD = 10 ** 9 + 7

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

N = int(input())


C = Factorial(N + 1, MOD)

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

order = []
order_append = order.append

stack = [(0, -1)]
stack_pop = stack.pop
stack_append = stack.append

while stack:
    tmp = stack_pop()
    order_append(tmp)
    for next_ in G[tmp[0]]:
        if next_ == tmp[1]:
            continue
        stack_append((next_, tmp[0]))
    
size = [1] * N
dp = [1] * N

# print (order)
for c, p in order[::-1]:
    if c == 0:
        break
    size[p] += size[c]

for c, p in order[::-1]:
    dp[c] = (dp[c] * C.factorial(size[c] - 1)) % MOD
    if c == 0:
        break
    # dp[c] = (dp[c] * C.factorial(size[c] - 1)) % MOD
    dp[p] = (dp[p] * dp[c] % MOD) * C.ifactorial(size[c]) % MOD

# print (dp)
dp2 = [0] * N
dp2[0] = dp[0]

for c, p in order[1::]:
    tmp = (dp2[p] * C.factorial(N - 1 - size[c]) % MOD) * C.factorial(size[c]) % MOD
    red = (tmp * C.ifactorial(N - 1) % MOD) * pow(dp[c], MOD - 2, MOD) % MOD

    size_red = N - size[c]
    tmp = (dp[c] * red % MOD) * C.factorial(N - 1) % MOD
    dp2[c] = (tmp * C.ifactorial(size[c] - 1) % MOD) * C.ifactorial(size_red) % MOD


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

Submission status: Accepted

Solution code:
# modulo
MOD = 10 ** 9 + 7

# number of vertices
n = int(input())
# adjacency list
edge = [[] for _ in range(n)]
# 0-index
for _ in range(n-1):
  a, b = map(int, input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

# factorial and inverse and inverse of factorial
fact = [1] * n
inverse = [1] * n
inv_fact = [1] * n
for i in range(2, n):
  fact[i] = fact[i-1] * i % MOD
  inverse[i] = -inverse[MOD % i] * (MOD // i) % MOD
  inv_fact[i] = inv_fact[i-1] * inverse[i] % MOD

# regarding index 0 as root of tree
# calculating parents of vertices and route from root with DFS
stack = [0]
parent = [0] * n
route = []
while stack:
  vertex = stack.pop()
  route.append(vertex)
  for child in edge[vertex]:
    if parent[vertex] != child:
      parent[child] = vertex
      stack.append(child)

# tree DP regarding index 0 as root of tree
# process from leaves to root
dp = [1] * n
size = [1] * n
for vertex in route[:0:-1]:
  pa = parent[vertex]
  sz = size[vertex]
  dp[vertex] = dp[vertex] * fact[sz-1] % MOD
  dp[pa] = dp[pa] * dp[vertex] * inv_fact[sz] % MOD
  size[pa] += sz
dp[0] = dp[0] * fact[n-1] % MOD

# rerooting
# process from root to leaves
for vertex in route[1:]:
  pa = parent[vertex]
  sz = size[vertex]
  inv_dp = pow(dp[vertex], MOD - 2, MOD)
  dp[vertex] = dp[vertex] * dp[pa] * inv_dp * sz * inverse[n-sz] % MOD

# printing result
for value in dp:
  print(value)

Submission status: Accepted

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for a,b in AB:
    c[a-1].append(b-1)
    c[b-1].append(a-1)
v=[1]+[0]*(N-1)
x=[0]
s=[]
parent=[-1]*N
child=[[] for i in range(N)]
while x:
    p=x.pop()
    s.append(p)
    for n in c[p]:
        if v[n]==0:
            v[n]=1
            x.append(n)
            parent[n]=p
            child[p].append(n)
m=10**9+7
fac=[1]*(N+10)
inv=[1]*(N+10)
ifac=[1]*(N+10)
for n in range(2,N+10):
    fac[n]=(fac[n-1]*n)%m
    inv[n]=m-inv[m%n]*(m//n)%m
    ifac[n]=(ifac[n-1]*inv[n])%m
size=[1]*N+[0]
dp=[1]*N+[0]
for n in s[::-1]:
    p=parent[n]
    size[p]+=size[n]
    dp[n]=dp[n]*fac[size[n]-1]%m
    dp[p]=dp[p]*ifac[size[n]]*dp[n]%m
size2=[N-v+1 for v in size]
dp2=[1]*N
for n in s[1:]:
    p=parent[n]
    dp2[n]=dp[p]*ifac[size[p]-1]*dp2[p]*ifac[size2[p]-1]*pow(dp[n],m-2,m)*fac[size[n]]*fac[size2[n]-2]%m
for i in range(N):
    print(dp[i]*dp2[i]*fac[size[i]+size2[i]-2]*ifac[size[i]-1]*ifac[size2[i]-1]%m)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
MAX_N = 2 * 10 ** 5

fact = [1] * MAX_N
inverse = [1] * MAX_N
inv_fact = [1] * MAX_N
for i in range(2, MAX_N):
  fact[i] = fact[i-1] * i % MOD
  inverse[i] = -inverse[MOD % i] * (MOD // i) % MOD
  inv_fact[i] = inv_fact[i-1] * inverse[i] % MOD

n = int(input())
edge = [[] for _ 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)

stack = [0]
parent = [0] * n
route = []
while stack:
  vertex = stack.pop()
  route.append(vertex)
  for child in edge[vertex]:
    if parent[vertex] != child:
      parent[child] = vertex
      stack.append(child)

dp = [1] * n
size = [1] * n
for vertex in route[:0:-1]:
  pa = parent[vertex]
  sz = size[vertex]
  dp[vertex] = dp[vertex] * fact[sz-1] % MOD
  dp[pa] = dp[pa] * dp[vertex] * inv_fact[sz] % MOD
  size[pa] += sz
dp[0] = dp[0] * fact[n-1] % MOD

for vertex in route[1:]:
  pa = parent[vertex]
  sz = size[vertex]
  tmp = dp[pa] * pow(dp[vertex], MOD - 2, MOD) * sz * inverse[n-sz] % MOD
  dp[vertex] = dp[vertex] * tmp % MOD

for value in dp:
  print(value)

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
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.factN(size[v] - 1) % MOD
    dpLeaf[pr] = dpLeaf[pr] * dpLeaf[v] * comb.factInvN(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
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.factN(size[v] - 1) % MOD
    dpLeaf[pr] = dpLeaf[pr] * dpLeaf[v] * comb.factInvN(size[v]) % MOD

ans = [0] * (N + 1)
ans[1] = dpLeaf[1]
for v in order[1:]:
    pr = parent[v]
    ans[v] = ans[pr] * comb.factN(N - 1 - size[v]) * comb.factInvN(N - size[v]) * size[v] % MOD

print(*(ans[1:]), sep='\n')

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.factN(size[v] - 1) % MOD
    dpLeaf[pr] = dpLeaf[pr] * dpLeaf[v] * comb.factInvN(size[v]) % MOD

ans = [0] * (N + 1)
ans[1] = dpLeaf[1]
for v in order[1:]:
    pr = parent[v]

    x = ans[pr]
    x *= comb.factN(N - 1 - size[v]) * comb.factInvN(N - size[v])
    x *= size[v]
    ans[v] = x % MOD

print(*(ans[1:]), sep='\n')

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline

    # comb init
    mod = 1000000007
    nmax = 2 * 10 ** 5 + 10  # change here
    fac = [0] * nmax
    finv = [0] * nmax
    inv = [0] * nmax
    fac[0] = 1
    fac[1] = 1
    finv[0] = 1
    finv[1] = 1
    inv[1] = 1
    for i in range(2, nmax):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod

    def comb(n, r):
        if n < r:
            return 0
        else:
            return (fac[n] * ((finv[r] * finv[n - r]) % mod)) % mod

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

    """ここから変更"""
    # op: 普通に根を固定した木DPで子の情報を親に集めるときの演算
    def op(a, b):
        return (((a[0] * b[0])%mod * comb(a[1]+b[1]+1, a[1]))%mod, a[1]+b[1]+1)
    ident_op = (1, -1)

    # cum_merge: 累積opどうしをマージするときの演算
    def cum_merge(a, b):
        return (((a[0] * b[0])%mod * comb(a[1]+b[1], a[1]))%mod, a[1]+b[1])
    # 単位元(cum_merge(ident, x) = x)
    ident_cum_merge = (1, 0)
    """ここまで変更"""

    # root=1でまず普通に木DPをする
    # 並行して各頂点につき、子の値の累積opを左右から求めておく
    # その後根から順番に、親からの寄与を求めていく(from_par)
    def Rerooting(adj):
        N = len(adj) - 1
        st = [1]
        seen = [0] * (N + 1)
        seen[1] = 1
        par = [0] * (N + 1)
        child = [[] for _ in range(N + 1)]
        seq = []
        while st:
            v = st.pop()
            seq.append(v)
            for u in adj[v]:
                if not seen[u]:
                    seen[u] = 1
                    par[u] = v
                    child[v].append(u)
                    st.append(u)
        seq.reverse()
        dp = [ident_op] * (N + 1)
        left = [ident_cum_merge] * (N + 1)
        right = [ident_cum_merge] * (N + 1)
        for v in seq:
            tmp = ident_cum_merge
            for u in child[v]:
                left[u] = tmp
                tmp = op(tmp, dp[u])
            tmp = ident_cum_merge
            for u in reversed(child[v]):
                right[u] = tmp
                tmp = op(tmp, dp[u])
            dp[v] = tmp

        seq.reverse()
        from_par = [ident_op] * (N + 1)
        for v in seq:
            if v == 1:
                continue
            from_par[v] = op(cum_merge(left[v], right[v]), from_par[par[v]])
            dp[v] = op(dp[v], from_par[v])

        return dp

    dp = Rerooting(adj)
    for v in range(1, N+1):
        print(dp[v][0])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
MOD = 1000000007
M = 2*10**5 + 10
fact = [1] * M
ifact = [1] * M
for i in range(2, M):
    fact[i] = fact[i - 1] * i % MOD
ifact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(2, M - 1)[::-1]:
    ifact[i] = ifact[i + 1] * (i + 1) % MOD


def comb(n, k):
    if n < 0 or k > n:
        return 0
    return (fact[n] * ifact[k] % MOD) * ifact[n - k] % MOD


class DP:
    def __init__(self, dp = 1, size = 0):    
        self.dp = dp
        self.size = size

    def __add__(self, other):
        dp = self.dp
        dp *= other.dp
        dp %= MOD
        size = self.size + other.size
        dp *= comb(size, self.size)
        dp %= MOD
        return DP(dp, size)

    def __sub__(self, other):
        size = self.size - other.size
        dp = self.dp
        dp *= pow(comb(self.size, size), MOD - 2, MOD)
        dp %= MOD
        dp *= pow(other.dp, MOD - 2, MOD)
        dp %= MOD
        return DP(dp, size)

    def addRoot(self):
        return DP(self.dp, self.size + 1)


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

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

dp = [DP() for _ in range(N)]
for v in order[1:][::-1]:
    dp[parent[v]] += dp[v].addRoot()
for v in order[1:]:
    d = dp[parent[v]] - dp[v].addRoot()
    dp[v] += d.addRoot()
for d in dp:
    print(d.dp)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return (fact[n]*finv[r])%mod*finv[n-r]%mod

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

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res

    return 

dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[x] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
    return
dfs2(0,-1)
for i in ans:
    print(i)

Submission status: Accepted

Solution code:
MOD = 1000000007
M = 2*10**5 + 10
fact = [1] * M
ifact = [1] * M
for i in range(2, M):
    fact[i] = fact[i - 1] * i % MOD
ifact[M - 1] = pow(fact[M - 1], MOD - 2, MOD)
for i in range(2, M - 1)[::-1]:
    ifact[i] = ifact[i + 1] * (i + 1) % MOD


def comb(n, k):
    if n < 0 or k > n:
        return 0
    return (fact[n] * ifact[k] % MOD) * ifact[n - k] % MOD


class DP:
    def __init__(self, dp = 1, size = 0):    
        self.dp = dp
        self.size = size

    def __add__(self, other):
        dp = self.dp
        dp *= other.dp
        dp %= MOD
        size = self.size + other.size
        dp *= comb(size, self.size)
        dp %= MOD
        return DP(dp, size)

    def __sub__(self, other):
        size = self.size - other.size
        dp = self.dp
        dp *= pow(comb(self.size, size), MOD - 2, MOD)
        dp %= MOD
        dp *= pow(other.dp, MOD - 2, MOD)
        dp %= MOD
        return DP(dp, size)

    def addRoot(self):
        return DP(self.dp, self.size + 1)


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

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

dp = [DP() for _ in range(N)]
for v in order[::-1]:
    if parent[v] == -1:
        continue
    dp[parent[v]] += dp[v].addRoot()
for v in order[1:]:
    d = dp[parent[v]] - dp[v].addRoot()
    dp[v] += d.addRoot()
for d in dp:
    print(d.dp)

Submission status: Accepted

Solution code:
import sys
from collections import deque
sys.setrecursionlimit(1000000)

def comb(n, r, fact, revfact, mod):
    return (fact[n] * (revfact[n-r] * revfact[r]) % mod) % mod

def dfs(i, parent, DP, sNum, E, fact, revfact, mod):
    Ans = 1
    sonNode = 1
    S = []
    for e in E[i]:
        if e != parent:
            mult, sn = dfs(e, i, DP, sNum, E, fact, revfact, mod)
            S.append(sn)
            Ans *= mult
            Ans %= mod
            sonNode += sn
    stotal = sonNode - 1
    for s in S:
        Ans *= comb(stotal, s, fact, revfact, mod)
        Ans %= mod
        stotal -= s
    DP[i] = Ans
    sNum[i] = sonNode - 1
    return Ans, sonNode

def solve():
    input = sys.stdin.readline
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)
        E[b-1].append(a-1)
    mod = 7 + 10 ** 9
    fact = [1] * (N + 1)
    for i in range(N): fact[i+1] = ((i + 1) * fact[i]) % mod
    revfact = [1] * (N + 1)
    revfact[N] = pow(fact[N], mod - 2, mod)
    for i in reversed(range(N)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    DP = [1] * N
    sNum = [0] * N
    usNum = [0] * N
    dfs(0, 0, DP, sNum, E, fact, revfact, mod)
    q = deque()
    for e in E[0]: q.append((e, 0))
    while q:
        nn, parn = q.popleft()
        upperMult = DP[parn] * pow(comb(N-1, sNum[nn] + 1, fact, revfact, mod), mod - 2, mod)
        usNum[nn] = upperNum = sNum[parn] - sNum[nn] + usNum[parn]
        DP[nn] = (upperMult * comb(N-1, upperNum, fact, revfact, mod)) % mod
        for e in E[nn]:
            if e != parn: q.append((e, nn))
        
    print("\n".join(map(str, DP)))
      
    return 0

if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Jun 15 22:01:38 2019

@author: aozora
"""
N, *L = map(int, open(0).read().split())
MOD = 10**9+7
graph = [[] for i in range(N+1)]
for a, b in zip(*[iter(L)]*2):
  graph[a].append(b)
  graph[b].append(a)
root = 1
parent = [0]*(N+1)
order = []
stack = [root]
while stack:
  x = stack.pop()
  order.append(x)
  for c in graph[x]:
    if parent[x]==c:
      continue
    stack.append(c)
    parent[c] = x

fact = [1] * (N + 10)
for n in range(1, N + 10):
    fact[n] = n * fact[n - 1] % MOD
fact_inv = [1] * (N + 10)
fact_inv[-1] = pow(fact[-1], MOD - 2, MOD)
for n in range(N + 9, 0, -1):
    fact_inv[n - 1] = fact_inv[n] * n % MOD

dp_d = [1]*(N+1)
size_d = [0]*(N+1)
for v in order[::-1]:
  s = size_d[v]
  p = parent[v]
  dp_d[v] *= fact[s]
  dp_d[v] %= MOD
  m = dp_d[v]
  size_d[p] += s+1
  dp_d[p] *= fact_inv[s+1]*m
  dp_d[p] %= MOD

size_u = [N-2-x for x in size_d]
dp_u = [1]*(N+1)

for v in order[1:]:
  p = parent[v]
  x = dp_d[p]
  x *= fact_inv[size_d[p]]
  x *= fact[size_d[v]+1]
  x *= pow(dp_d[v],MOD-2,MOD)
  x *= fact[size_u[v]]
  x *= fact_inv[size_u[p]+1]
  x *= dp_u[p]
  dp_u[v] = x%MOD

for xd, xu, sd, su in zip(dp_d[1:], dp_u[1:], size_d[1:], size_u[1:]):
    su += 1
    x = xd * xu * fact[sd + su] * fact_inv[sd] * fact_inv[su] % MOD
    print(x)