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)

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        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):
    if neighbor[p]==[]: return
    for x in neighbor[p]:
        par[x]=p
        neighbor[x].remove(p)
        cur(x)
    descend[par[p]]+=descend[p]

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

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

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

cur(1)


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

cur2(1)

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

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
comb = lambda n, k : fact[n] * fact_inv[k] * fact_inv[n-k] % mod

dp = [1] * N
size = [0] * N
def dfs(par, v):
    for u in G[v]:
        if par == u:
            continue
        dfs(v, u)
        size[v] += size[u]
        dp[v] = dp[v] * dp[u] * fact_inv[size[u]] % mod
    dp[v] = dp[v] * fact[size[v]] % mod
    size[v] += 1

ans = [0] * N
def reroot(par, val_par, size_par, v):
    ans[v] = val_par * dp[v] * comb(N-1, size_par) % mod
    for u in G[v]:
        if par == u:
            continue
        val = ans[v] * inv(dp[u] * comb(N-1, size[u])) % mod
        reroot(v, val, N-size[u],  u)

dfs(-1, 0)
reroot(-1, 1, 0, 0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
from collections import deque


MOD = 10 ** 9 + 7


def solve(n, edge_list):

    # mod
    factorial = [1] * n
    for i in range(1, n):
        factorial[i] = (factorial[i - 1] * i) % MOD
    factorial_inv = [1] * n
    factorial_inv[-1] = pow(factorial[-1], MOD - 2, MOD)
    for i in range(n - 2, 0, -1):
        factorial_inv[i] = (factorial_inv[i + 1] * (i + 1)) % MOD

    # graph
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        a, b = edge_list[i]
        g[a].append(b)
        g[b].append(a)

    # root 0
    order = []
    parent = [-1] * n
    parent[0] = 0
    children = [[] for _ in range(n)]
    queue = deque([0])
    while len(queue) > 0:
        p = queue.popleft()
        order.append(p)
        for q in g[p]:
            if parent[q] == -1:
                parent[q] = p
                children[p].append(q)
                queue.append(q)

    # n_children
    count_children_res = [-1] * n

    for x in order[::-1]:
        if len(children[x]) == 0:
            count_children_res[x] = 0
        else:
            r = len(children[x]) + sum([count_children_res[y] for y in children[x]])
            count_children_res[x] = r

    assign_children_res = [-1] * n

    for x in order[::-1]:
        if len(children[x]) == 0:
            assign_children_res[x] = 1
        else:
            r = factorial[count_children_res[x]]
            for y in children[x]:
                r *= assign_children_res[y]
                r *= factorial_inv[count_children_res[y] + 1]
                r %= MOD
            assign_children_res[x] = r

    # reverse direction
    assign_parents_res = [-1] * n
    assign_parents_res[0] = 1

    for x in order[1:]:
        p = parent[x]
        r = assign_children_res[p]
        r *= pow(assign_children_res[x], MOD - 2, MOD)
        r *= factorial[count_children_res[x] + 1]

        # r *= factorial[count_children_res[p] - count_children_res[x] - 1]
        r *= factorial_inv[count_children_res[p]]

        r *= assign_parents_res[p]
        r *= factorial[n - count_children_res[x] - 2]
        # r *= factorial_inv[count_children_res[p] - count_children_res[x] - 1]
        r *= factorial_inv[n - count_children_res[p] - 1]

        r %= MOD
        assign_parents_res[x] = r

    res_list = [0] * n
    res_list[0] = assign_children_res[0]

    for i in range(1, n):
        res = factorial[n - 1]
        # children
        for j in children[i]:
            res *= assign_children_res[j]
            res *= factorial_inv[count_children_res[j] + 1]
            res %= MOD
        # parent
        res *= assign_parents_res[i]
        res *= factorial_inv[n - 1 - count_children_res[i]]
        res %= MOD
        res_list[i] = res
    # print(res_list)
    return res_list


def main():
    n = int(input())
    edge_list = []
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge_list.append((a - 1, b - 1))
    res_list = solve(n, edge_list)
    for res in res_list:
        print(res)


def test():
    assert solve(3, [(0, 1), (0, 2)]) == [2, 1, 1]
    assert solve(2, [(0, 1)]) == [1, 1]
    assert solve(5, [(0, 1), (1, 2), (2, 3), (2, 4)]) == [2, 8, 12, 3, 3]
    assert solve(8, [(0, 1), (1, 2), (2, 3), (2, 4), (2, 5), (5, 6), (5, 7)]) == [40, 280, 840, 120, 120, 504, 72, 72]


if __name__ == "__main__":
    test()
    # r_star = solve(200000, [(i, 0) for i in range(1, 200000)])
    # print(1)
    main()

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, modinv(b))
def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
NNN = (2*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

vs = set([1])
stack = [1]
vs_bfs = list()
parents = [0] * (N+1)
while stack:
    v = stack.pop()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        stack.append(u)

dp1 = [0 for _ in range(N+1)]
sss = [0 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    ts = []
    for u in d[v]:
        if u == parents[v]:
            continue
        t = mul(dp1[u], t)
        ts.append(sss[u])
    st = sum(ts)
    sss[v] = st + 1
    for tt in ts:
        t = mul(cmb(st, tt), t)
        st -= tt
    dp1[v] = t

for v in vs_bfs:
    if v == 1:
        continue
    p = parents[v]
    dp1[v] = mul(
            mul(dp1[p], sss[v]),
            inverse[N-sss[v]]
            )

for x in dp1[1:]:
    print(x)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
mod=10**9+7


n_max=(2*10**5+1)
F,FI=[0]*(n_max+1),[0]*(n_max+1)
F[0],FI[0]=1,1
for i in range(n_max):
  F[i+1]=(F[i]*(i+1))%mod
FI[n_max-1]=pow(F[n_max-1],mod-2,mod)
for i in reversed(range(n_max-1)):
  FI[i]=(FI[i+1]*(i+1))%mod
def comb(x,y):
  return (F[x]*FI[x-y]*FI[y])%mod
def I(x):
  return pow(x,mod-2,mod)

edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
Ans=[]
inf=10**6

#親と入次数を求める
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)
 
#トポソする
from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

Used=[False]*n
C=[0]*n
for i in reversed(range(n)):
  v=TS[i]
  Used[v]=True
  for g in edge[v]:
    if not Used[g]:
      C[g]+=C[v]+1

D=[1]*n
for i in reversed(range(n)):
  v=TS[i]
  D[v]=(D[v]*F[C[v]])%mod
  if Par[v]!=-1:
    D[Par[v]]=(D[Par[v]]*I(F[C[v]+1])*D[v])%mod
E=[1]*n
for i in range(n):
  v=TS[i]
  if Par[v]!=-1:
    cur=E[v]*FI[n-C[v]-1]
  else:
    cur=1
  for e in edge[v]:
    if e!=Par[v]:
      cur=(cur*FI[C[e]+1]*D[e])%mod
  for e in edge[v]:
    if e!=Par[v]:
      E[e]=(cur*F[n-2-C[e]]*F[C[e]+1]*I(D[e]))%mod
for i in range(n):
  print((comb(n-1,C[i])*D[i]*E[i])%mod)

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod
def div(a, b):
    return mul(a, modinv(b))
def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u
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
NNN = (2*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]
for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

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

vs = set([1])
stack = [1]
vs_bfs = list()
parents = [0] * (N+1)
while stack:
    v = stack.pop()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        stack.append(u)

dp1 = [0 for _ in range(N+1)]
sss = [0 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    ts = []
    for u in d[v]:
        if u == parents[v]:
            continue
        t = mul(dp1[u], t)
        ts.append(sss[u])
    st = sum(ts)
    sss[v] = st + 1
    for tt in ts:
        t = mul(cmb(st, tt, mod), t)
        st -= tt
    dp1[v] = t

for v in vs_bfs:
    if v == 1:
        continue
    p = parents[v]
    dp1[v] = mul(
            div(dp1[p], cmb(N-1, sss[v], mod)),
            cmb(N-1, N-sss[v], mod)
            )

for x in dp1[1:]:
    print(x)

Submission status: Accepted

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


class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


class rerooting:
    def __init__(self, tree, node_merge, node_purge, e):
        self.tree = tree
        self.root = 0
        self.n = len(tree)
        self.par = {self.root: -1}
        self.e = e
        self.node_merge = node_merge
        self.node_purge = node_purge
        self.val1 = [self.e for _ in range(self.n)]
        self.val2 = [self.e for _ in range(self.n)]
        self._dfs1()
        self._dfs2()
         
    def _dfs1(self):
        st1, st2 = deque([self.root]), deque([self.root])
        # 行きがけ順を記録
        while st1:
            v = st1.pop()
            for nxt_v in self.tree[v]:
                if nxt_v in self.par:
                    continue
                else:
                    self.par[nxt_v] = v
                    st1.append(nxt_v)
                    st2.append(nxt_v)
        # 帰りがけ順で処理
        while st2:
            v = st2.pop()
            for nxt_v in self.tree[v]:
                if nxt_v == self.par[v]:
                    continue
                else:
                    self.val1[v] = self.node_merge(self.val1[v], self.val1[nxt_v])

    def _dfs2(self):
        q = deque([(self.root, self.e)])
        while q:
            v, par_val = q.pop()
            tmp = {}
            for nxt_v in self.tree[v]:
                if nxt_v == self.par[v]:
                    tmp[nxt_v] = par_val
                else:
                    tmp[nxt_v] = self.val1[nxt_v]
            for nxt_v in tmp:
                self.val2[v] = self.node_merge(self.val2[v], tmp[nxt_v])

            for nxt_v in tree[v]:
                if nxt_v == self.par[v]:
                    continue
                else:
                    q.append((nxt_v, self.node_purge(self.val2[v], self.val1[nxt_v])))

def node_merge(sub, node):
    ptn_sub, cnt_sub = sub
    ptn_node, cnt_node = node
    cnt = cnt_sub + cnt_node
    return (ptn_sub * ptn_node * comb.combination(cnt - 1, cnt_node) % MOD, cnt)
      
def node_purge(sub, node):
    ptn_sub, cnt_sub = sub
    ptn_node, cnt_node = node
    inv_ptn_node = pow(ptn_node, MOD - 2, MOD)
    inv_comb = pow(comb.combination(cnt_sub - 1, cnt_node), MOD - 2, MOD)
    inv_cnt = cnt_sub - cnt_node
    return (ptn_sub * inv_ptn_node * inv_comb % MOD, inv_cnt)

e = (1, 1)

n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
MOD = 10 ** 9 + 7

tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

comb = Combination(10 ** 6, MOD)
rt = rerooting(tree, node_merge, node_purge, e)
for i in range(n):
    print(rt.val2[i][0])

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

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
    import sys
    mod = pow(10, 9) + 7
    sys.setrecursionlimit(pow(10, 8))

NNN = (2*10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

from collections import deque
N, = map(int, input().split())
d = [list() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

vs = set([1])
stack = [1]
vs_bfs = list()
parents = [0] * (N+1)
while stack:
    v = stack.pop()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        stack.append(u)

dp1 = [0 for _ in range(N+1)]
sss = [0 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    ts = []
    for u in d[v]:
        if u == parents[v]:
            continue
        t = mul(dp1[u], t)
        ts.append(sss[u])
    st = sum(ts)
    sss[v] = st + 1
    for tt in ts:
        t = mul(cmb(st, tt, mod), t)
        st -= tt
    dp1[v] = t

for v in vs_bfs:
    if v == 1:
        continue
    p = parents[v]
    dp1[v] = mul(
            div2(dp1[p], cmb(N-1, sss[v], mod)),
            cmb(N-1, N-sss[v], mod))

for x in dp1[1:]:
    print(x)

Submission status: Accepted

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


class Combination:
    """階乗とその逆元のテーブルをO(N)で事前作成し、組み合わせの計算をO(1)で行う"""
    def __init__(self, n, MOD):
        self.fact = [1]
        for i in range(1, n + 1):
            self.fact.append(self.fact[-1] * i % MOD)
        self.inv_fact = [0] * (n + 1)
        self.inv_fact[n] = pow(self.fact[n], MOD - 2, MOD)
        for i in reversed(range(n)):
            self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % MOD
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


class rerooting:
    def __init__(self, tree):
        self.tree = tree
        self.root = 0
        self.n = len(tree)
        self.par = {self.root: -1}
        self.e = (1, 1)
        self.val1 = [self.e for _ in range(self.n)]
        self.val2 = [self.e for _ in range(self.n)]
        self._dfs1()
        self._dfs2()

    def node_merge(self, sub, node):
        ptn_sub, cnt_sub = sub
        ptn_node, cnt_node = node
        cnt = cnt_sub + cnt_node
        return (ptn_sub * ptn_node * comb.combination(cnt - 1, cnt_node) % MOD, cnt)
      
    def node_purge(self, sub, node):
        ptn_sub, cnt_sub = sub
        ptn_node, cnt_node = node
        inv_ptn_node = pow(ptn_node, MOD - 2, MOD)
        inv_comb = pow(comb.combination(cnt_sub - 1, cnt_node), MOD - 2, MOD)
        inv_cnt = cnt_sub - cnt_node
        return (ptn_sub * inv_ptn_node * inv_comb % MOD, inv_cnt)
         
    def _dfs1(self):
        st1, st2 = deque([self.root]), deque([self.root])
        # 行きがけ順を記録
        while st1:
            v = st1.pop()
            for nxt_v in self.tree[v]:
                if nxt_v in self.par:
                    continue
                else:
                    self.par[nxt_v] = v
                    st1.append(nxt_v)
                    st2.append(nxt_v)
        # 帰りがけ順で処理
        while st2:
            v = st2.pop()
            for nxt_v in self.tree[v]:
                if nxt_v == self.par[v]:
                    continue
                else:
                    self.val1[v] = self.node_merge(self.val1[v], self.val1[nxt_v])

    def _dfs2(self):
        q = deque([(self.root, self.e)])
        while q:
            v, par_val = q.pop()
            tmp = {}
            for nxt_v in self.tree[v]:
                if nxt_v == self.par[v]:
                    tmp[nxt_v] = par_val
                else:
                    tmp[nxt_v] = self.val1[nxt_v]
            for nxt_v in tmp:
                self.val2[v] = self.node_merge(self.val2[v], tmp[nxt_v])

            for nxt_v in tree[v]:
                if nxt_v == self.par[v]:
                    continue
                else:
                    q.append((nxt_v, self.node_purge(self.val2[v], self.val1[nxt_v])))


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
MOD = 10 ** 9 + 7

tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

comb = Combination(10 ** 6, MOD)
rt = rerooting(tree)
for i in range(n):
    print(rt.val2[i][0])

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

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
    import sys
    mod = pow(10, 9) + 7
    sys.setrecursionlimit(pow(10, 8))

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

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

from collections import deque
N, = map(int, input().split())
d = [list() for _ in range(N+1)]
d2 = [list() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

queue=deque([1])
vs = set([1])
vs_bfs = list()
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)
        d2[v].append(u)

dp1 = [0 for _ in range(N+1)]
sss = [0 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    ts = []
    for u in d2[v]:
        t = mul(dp1[u], t)
        ts.append(sss[u])
    st = sum(ts)
    sss[v] = st + 1
    for tt in ts:
        t = mul(cmb(st, tt, mod), t)
        st -= tt
    dp1[v] = t
#print(dp1)

for v in vs_bfs:
    if v == 1:
        continue
    p = parents[v]
#    print(dp2[p])
    dp1[v] = mul(
            div2(dp1[p], cmb(N-1, sss[v], mod)),
            cmb(N-1, N-sss[v], mod))

#print(dp2)

for x in dp1[1:]:
    print(x)

Submission status: Accepted

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

nn = 200200
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
inv = [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
for i in range(1, nn)[::-1]:
    inv[i] = fainv[i] * fa[i-1]

C = lambda a, b: fa[a] * fainv[b] % mod * fainv[a-b] % mod if 0 <= b <= a else 0

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)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 1
    for j in X[i]:
        a = a * BU[j] % mod
        s += SI[j]
    SI[i] = s
    BU[i] = inv[s] * a % mod

for i in R:
    c = len(X[i])
    AR = [1] * (c + 1)
    AL = 1
    for k in range(c-1, 0, -1):
        j = X[i][k]
        AR[k] = AR[k+1] * BU[j] % mod
    for k, j in enumerate(X[i]):
        TD[j] = TD[i] * AL % mod * AR[k+1] % mod * inv[N - SI[j]] % mod
        AL = AL * BU[j] % mod

for i in range(N):
    print(BU[i] * fa[SI[i]] % mod * TD[i] % mod * fa[N - SI[i]] % mod * C(N-1, SI[i] - 1) % mod)

Submission status: Accepted

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

nn = 200200
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
inv = [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
for i in range(1, nn)[::-1]:
    inv[i] = fainv[i] * fa[i-1]

C = lambda a, b: fa[a] * fainv[b] % mod * fainv[a-b] % mod if 0 <= b <= a else 0

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)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 1
    for j in X[i]:
        a = a * BU[j] % mod
        s += SI[j]
    SI[i] = s
    BU[i] = inv[s] * a % mod

for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for k, j in enumerate(X[i]):
        AL[k+1] = AL[k] * BU[j] % mod
    for k, j in enumerate(X[i][::-1]):
        AR[c-k-1] = AR[c-k] * BU[j] % mod
    for k, j in enumerate(X[i]):
        TD[j] = TD[i] * AL[k] % mod * AR[k+1] % mod * inv[N - SI[j]] % mod

for i in range(N):
    print(BU[i] * fa[SI[i]] % mod * TD[i] % mod * fa[N - SI[i]] % mod * C(N-1, SI[i] - 1) % mod)

Submission status: Accepted

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

nn = 200200
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
inv = [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
for i in range(1, nn)[::-1]:
    inv[i] = fainv[i] * fa[i-1]

C = lambda a, b: fa[a] * fainv[b] % mod * fainv[a-b] % mod if 0 <= b <= a else 0

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)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 1
    for j in X[i]:
        a = a * BU[j] % mod
        s += SI[j]
    SI[i] = s
    BU[i] = inv[s] * a % mod

for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for k, j in enumerate(X[i]):
        AL[k+1] = AL[k] * BU[j] % mod
    for k in range(c-1, 0, -1):
        j = X[i][k]
        AR[k] = AR[k+1] * BU[j] % mod
    for k, j in enumerate(X[i]):
        TD[j] = TD[i] * AL[k] % mod * AR[k+1] % mod * inv[N - SI[j]] % mod

for i in range(N):
    print(BU[i] * fa[SI[i]] % mod * TD[i] % mod * fa[N - SI[i]] % mod * C(N-1, SI[i] - 1) % mod)

Submission status: Accepted

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

nn = 200200
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
inv = [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
for i in range(1, nn)[::-1]:
    inv[i] = fainv[i] * fa[i-1]

C = lambda a, b: fa[a] * fainv[b] % mod * fainv[a-b] % mod if 0 <= b <= a else 0

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)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 1
    for j in X[i]:
        a = a * BU[j] % mod
        s += SI[j]
    SI[i] = s
    BU[i] = inv[s] * a % mod

for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for k, j in enumerate(X[i]):
        AL[k+1] = AL[k] * BU[j] % mod
    for k in range(c-1, -1, -1):
        j = X[i][k]
        AR[k] = AR[k+1] * BU[j] % mod
    for k, j in enumerate(X[i]):
        TD[j] = TD[i] * AL[k] % mod * AR[k+1] % mod * inv[N - SI[j]] % mod

for i in range(N):
    print(BU[i] * fa[SI[i]] % mod * TD[i] % mod * fa[N - SI[i]] % mod * C(N-1, SI[i] - 1) % mod)

Submission status: Accepted

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

nn = 200200
mod = 10**9+7

fa = [1] * (nn+1)
fainv = [1] * (nn+1)
inv = [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
for i in range(1, nn)[::-1]:
    inv[i] = fainv[i] * fa[i-1]

C = lambda a, b: fa[a] * fainv[b] % mod * fainv[a-b] % mod if 0 <= b <= a else 0

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)

BU = [1] * N
TD = [1] * N
SI = [1] * N
for i in R[::-1]:
    a = 1
    s = 1
    for j in X[i]:
        a = a * BU[j] % mod
        s += SI[j]
    SI[i] = s
    BU[i] = inv[s] * a % mod

for i in R:
    c = len(X[i])
    AL = [1] * (c + 1)
    AR = [1] * (c + 1)
    for k, j in enumerate(X[i]):
        AL[k+1] = AL[k] * BU[j] % mod
    for k, j in list(enumerate(X[i]))[::-1]:
        AR[k] = AR[k+1] * BU[j] % mod
    for k, j in enumerate(X[i]):
        TD[j] = TD[i] * AL[k] % mod * AR[k+1] % mod * inv[N - SI[j]] % mod

for i in range(N):
    print(BU[i] * fa[SI[i]] % mod * TD[i] % mod * fa[N - SI[i]] % mod * C(N-1, SI[i] - 1) % mod)