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: Time Limit Exceeded

Solution code:
import os
import sys
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def get_factorials(max, mod=None):
    """
    階乗 0!, 1!, 2!, ..., max!
    :param int max:
    :param int mod:
    """
    ret = [1]
    n = 1
    if mod:
        for i in range(1, max + 1):
            n *= i
            n %= mod
            ret.append(n)
    else:
        for i in range(1, max + 1):
            n *= i
            ret.append(n)
    return ret


def mod_invs(max, mod):
    """
    逆元 0, 1/1, 1/2, 1/3, ..., 1/max
    :param int max:
    :param int mod:
    """
    invs = [1] * (max + 1)
    invs[0] = 0
    for x in range(2, max + 1):
        invs[x] = (-(mod // x) * invs[mod % x]) % mod
    return invs


def factorial_invs(max, mod):
    """
    階乗 0!, 1!, 2!, ..., max! の逆元
    :param int max:
    :param int mod:
    """
    ret = [1]
    r = 1
    for inv in mod_invs(max, mod)[1:]:
        r = r * inv % mod
        ret.append(r)
    return ret


class Combination:
    def __init__(self, max, mod):
        """
        :param int max:
        :param int mod: 3 以上の素数であること
        """
        self._factorials = get_factorials(max, mod)
        self._finvs = factorial_invs(max, mod)
        self._mod = mod

    def ncr(self, n, r):
        """
        :param int n:
        :param int r:
        :rtype: int
        """
        if n < r:
            return 0
        return self._factorials[n] * self._finvs[r] % self._mod * self._finvs[n - r] % self._mod


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

factorials = get_factorials(max=N * 2, mod=MOD)
finvs = factorial_invs(max=N * 2, mod=MOD)


@lru_cache(maxsize=1 << (2 * 10 ** 6).bit_length())
def solve(v, p):
    ret = 1
    children = []
    for u in graph[v]:
        if u == p:
            continue
        r, cnt = solve(u, v)
        children.append(cnt)
        ret *= r
        ret %= MOD
    children_cnt = sum(children)
    ret *= factorials[children_cnt]
    ret %= MOD
    for cnt in children:
        ret *= finvs[cnt]
        ret %= MOD
    return ret, children_cnt + 1


ans = []
for v in range(N):
    a, _ = solve(v, None)
    ans.append(a)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n):
        self.n = n
        self.tree = [[] for _ in range(n)]
        self.root = None
        self.dep = [None] * n
        self.size = [1] * n

    def add_edges(self, e, idx=1):
        for u, v in e:
            self.tree[u - idx].append(v - idx)
            self.tree[v - udx].append(u - idx)

    def add_edge(self, u, v, idx=1):
        self.tree[u - idx].append(v - idx)
        self.tree[v - idx].append(u - idx)

    def set_root(self, r):
        self.root = r
        self.par = [None] * self.n
        self.par[r] = -1
        self.dep[r] = 0
        self.ord = [r]
        stack = [r]
        while stack:
            v = stack.pop()
            for adj in self.tree[v]:
                if self.par[adj] is not None: continue
                self.par[adj] = v
                self.dep[adj] = self.dep[v] + 1
                self.ord.append(adj)
                stack.append(adj)
        for v in self.ord[::-1]:
            for adj in self.tree[v]:
                if self.par[v] == adj: continue
                self.size[v] += self.size[adj]

    def diam(self):
        #assert self.root is not None
        u = self.dep.index(max(self.dep))
        dist = [None] * self.n
        dist[u] = 0
        prev = [None] * self.n
        stack = [u]
        while stack:
            v = stack.pop()
            for adj in self.tree[v]:
                if dist[adj] is not None: continue
                dist[adj] = dist[v] + 1
                prev[adj] = v
                stack.append(adj)
        d = max(dist)
        v = w = dist.index(d)
        path = [v]
        while w != u:
            w = prev[w]
            path.append(v)
        return d, v, u, path

    def rerooting(self, op, e, merge, id):
        #assert self.root is not None
        dp = [e] * self.n
        lt = [id] * self.n
        rt = [id] * self.n
        inv = [id] * self.n
        for v in self.ord[::-1]:
            tl = tr = e
            for adj in self.tree[v]:
                if self.par[v] == adj: continue
                lt[adj] = tl
                tl = op(tl, dp[adj])
            for adj in self.tree[v][::-1]:
                if self.par[v] == adj: continue
                rt[adj] = tr
                tr = op(tr, dp[adj])
            dp[v] = tr
        for v in self.ord:
            if v == self.root: continue
            p = self.par[v]
            inv[v] = op(merge(lt[v], rt[v]), inv[p])
            dp[v] = op(dp[v], inv[v])
        return dp

    def heavylight_decomposition(self):
        #assert self.root is not None
        self.vid = [None] * self.n
        self.head = [None] * self.n
        self.head[self.root] = self.root
        self.next = [None] * self.n
        stack = [self.root]
        cnt = 0
        while stack:
            v = stack.pop()
            self.vid[v] = cnt
            cnt += 1
            maxs = 0
            for adj in self.tree[v]:
                if self.par[v] == adj: continue
                if maxs < self.size[adj]:
                    maxs = self.size[adj]
                    self.next[v] = adj
            for adj in self.tree[v]:
                if self.par[v] == adj or self.next[v] == adj: continue
                self.head[adj] = adj
                stack.append(adj)
            if self.next[v] is not None:
                self.head[self.next[v]] = self.head[v]
                stack.append(self.next[v])

    def lca(self, u, v):
        while True:
            if self.vid[u] > self.vid[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.par[self.head[v]]
            else:
                return u

    def range_query(self, u, v, edge_query=False):
        while True:
            if self.vid[u] > self.vid[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                yield self.vid[self.head[v]], self.vid[v] + 1
                v = self.par[self.head[v]]
            else:
                yield self.vid[u] + edge_query, self.vid[v] + 1
                return

    def subtree_query(self, u):
        return self.vid[u], self.vid[u] + self.size[u]

def build_factorial(n):
    fct = [0] * (n + 1)
    ifct = [0] * (n + 1)
    fct[0] = ifct[0] = 1
    for i in range(n):
        fct[i + 1] = fct[i] * (i + 1) % MOD
    ifct[n] = pow(fct[n], MOD - 2, MOD)
    for i in range(n)[::-1]:
        ifct[i] = ifct[i + 1] * (i + 1) % MOD
    return fct, ifct

import sys
input = sys.stdin.buffer.readline

MOD = 1000000007

N = int(input())

fct, ifct = build_factorial(N + 1)
tree = Tree(N)

for _ in range(N - 1):
    u, v = map(int, input().split())
    tree.add_edge(u, v, 1)

tree.set_root(0)

def merge(lt, rt):
    lc, ls = lt
    rc, rs = rt
    size = ls + rs - 1
    cnt = lc * rc * ifct[ls - 1] * ifct[rs - 1] * fct[size - 1] % MOD
    return cnt, size

def op(v, ad):
    vc, vs = v
    adc, ads = ad
    size = vs + ads
    cnt = vc * adc * ifct[ads] * fct[size - 1] * ifct[vs - 1] % MOD
    return cnt, size

e = (1, 1)
id = (1, 0)

d = tree.rerooting(op, e, merge, id)
res = []

for cnt, size in d:
    res.append(cnt)

print('\n'.join(map(str, res)))

Submission status: Accepted

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

U = 2*10**5
MOD = 10**9+7
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

n = int(input())
T = [[] for _ in range(n)]
for _ in range(n-1):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  T[a].append(b)
  T[b].append(a)
size = [0]*n
par = [-1]*n
dp1 = [-1]*n
dp2 = [-1]*n
def dfs1(p, v):
  if dp1[v] != -1:
    return dp1[v]
  temp = 1
  s = 1
  for nv in T[v]:
    if nv == p:
      continue
    temp *= dfs1(v, nv)
    temp *= fact_inv[size[nv]]
    temp %= MOD
    par[nv] = v
    s += size[nv]
  size[v] = s
  temp *= fact[s-1]
  temp %= MOD
  dp1[v] = temp
  return temp
dfs1(-1, 0)
def dfs2(v):
  if v == 0:
    return dp1[0]
  if dp2[v] != -1:
    return dp2[v]
  temp = dfs2(par[v])
  temp *= fact[n-size[v]-1]
  temp *= fact[size[v]]
  temp %= MOD
  temp *= fact_inv[size[v]-1]
  temp *= fact_inv[n-size[v]]
  temp %= MOD
  dp2[v] = temp
  return temp
for i in range(n):
  print(dfs2(i))

Submission status: Accepted

Solution code:
import sys,os,io
# input = sys.stdin.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7

def fact(N):
  ans = [1]*(N+1)
  for i in range(1,N+1):
    ans[i] = ans[i-1]*i%mod
  return ans

def combs_mod(n,k):
  #nC0からnCkまで
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  fac = fact(N)
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u] = v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= pow(fac[part_num[u]],mod-2,mod)*ans[u]%mod
        ans[v] %= mod
    if marker==0:
      stack.pop()
      ans[v] *= fac[part_num[v]-1]
      ans[v] %= mod
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  combs = combs_mod(N-1,N-1)
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*combs[part_num[u]],mod-2,mod)%mod
      ans[u] *= combs[part_num[u]-1]*p_value[u]
      ans[u] %= mod
      stack.append(u)
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys,os,io
input = sys.stdin.readline
# input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

N = int(input())
edge = [[] for _ in range(N)]
for i in range(N-1):
  a,b = list(map(int, input().split()))
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
mod = 10**9+7

def fact(N):
  ans = [1]*(N+1)
  for i in range(1,N+1):
    ans[i] = ans[i-1]*i%mod
  return ans

def combs_mod(n,k):
  #nC0からnCkまで
  inv = [1]*(k+1)
  for i in range(1,k+1):
    inv[i] = pow(i,mod-2,mod)
  ans = [1]*(k+1)
  for i in range(1,k+1):
    ans[i] = ans[i-1]*(n+1-i)*inv[i]%mod
  return ans

def dfs(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  fac = fact(N)
  while stack:
    v = stack[-1]
    marker = 0
    for u in edge[v]:
      if u==parent[v]:
        continue
      if parent[u]==N: #子へ降ろす
        marker = 1
        parent[u] = v
        stack.append(u)
      else: #子から吸い上げる
        part_num[v] += part_num[u]
        ans[v] *= pow(fac[part_num[u]],mod-2,mod)*ans[u]%mod
        ans[v] %= mod
    if marker==0:
      stack.pop()
      ans[v] *= fac[part_num[v]-1]
      ans[v] %= mod
  return

def dfs2(start):
  stack = [start]
  parent = [N]*N
  parent[start] = -1
  p_value = [0]*N
  combs = combs_mod(N-1,N-1)
  while stack:
    v = stack.pop()
    for i,u in enumerate(edge[v]):
      if u==parent[v]:
        continue
      parent[u]=v
      p_value[u] = ans[v]*pow(ans[u]*combs[part_num[u]],mod-2,mod)%mod
      ans[u] *= combs[part_num[u]-1]*p_value[u]
      ans[u] %= mod
      stack.append(u)
  return

ans = [1]*N
part_num = [1]*N
dfs(0)
dfs2(0)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

# Based on the following blog.
# https://null-mn.hatenablog.com/entry/2020/04/14/124151

from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def __dfs1(self, u, p):
        o = []
        s = [(u, -1)]
        while s:
            u, p = s.pop()
            o.append((u, p))
            for v in self.tree[u]:
                if v == p:
                    continue
                s.append((v, u))

        for u, p in reversed(o):
            r = self.ie
            for v in self.tree[u]:
                if v == p:
                    continue
                r = self.merge(r, self.f(self.dp[u][v], v))

            self.dp[p][u] = self.g(r, u)

    def __dfs2(self, u, p, a):
        s = [(u, p, a)]

        while s:
            u, p, a = s.pop()
            self.dp[u][p] = a


            pl = [0] * (len(self.tree[u]) + 1)
            pl[0] = self.ie
            for i, v in enumerate(self.tree[u]):
                pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

            pr = [0] * (len(self.tree[u]) + 1)
            pr[-1] = self.ie
            for i, v in reversed(list(enumerate(self.tree[u]))):
                pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

            for i, v in enumerate(self.tree[u]):
                if v == p:
                    continue
                r = self.merge(pl[i], pr[i+1])
                s.append((v, u, self.g(r, u)))

    # def __dfs1(self, u, p):
    #     r = self.ie
    #     for v in self.tree[u]:
    #         if v == p:
    #             continue
    #         self.dp[u][v] = self.__dfs1(v, u)
    #         r = self.merge(r, self.f(self.dp[u][v], v))

    #     return self.g(r, u)

    # def __dfs2(self, u, p, a):
    #     for v in self.tree[u]:
    #         if v == p:
    #             self.dp[u][v] = a
    #             break
    #     pl = [0] * (len(self.tree[u]) + 1)
    #     pl[0] = self.ie
    #     for i, v in enumerate(self.tree[u]):
    #         pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

    #     pr = [0] * (len(self.tree[u]) + 1)
    #     pr[-1] = self.ie
    #     for i, v in reversed(list(enumerate(self.tree[u]))):
    #         pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

    #     for i, v in enumerate(self.tree[u]):
    #         if v == p:
    #             continue
    #         r = self.merge(pl[i], pr[i+1])
    #         self.__dfs2(v, u, self.g(r, v))

    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)


def atcoder_dp_dp_v():
    # https://atcoder.jp/contests/dp/tasks/dp_v
    # https://atcoder.jp/contests/dp/submissions/16666380
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)-1)


def atcoder_abc60_f():
    # https://atcoder.jp/contests/abc160/tasks/abc160_f
    # https://atcoder.jp/contests/abc160/submissions/16666397
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    M = 10**9+7

    from functools import reduce

    fact = [1]
    for i in range(1, 10**6):
        fact.append(fact[-1]*i % M)

    def f(x, _):
        c = x[0]
        s = x[1]
        c *= pow(fact[s], M-2, M)
        c %= M
        return (c, s)

    def g(x, _):
        c = x[0]
        s = x[1]
        c *= fact[s]
        c %= M
        return (c, s+1)

    def merge(x, y):
        return (x[0]*y[0]%M, x[1]+y[1])

    rr = ReRooting(f, g, merge, (1, 0))
    for a, b in AB:
        rr.add_edge(a, b)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)[0])


def codeforces_1324_f():
    N = int(input())
    A = list(map(int, input().split()))
    UV = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, v: max(x, 0)

    def g(x, v):
        return x + (1 if A[v-1] == 1 else -1)

    def merge(x, y):
        return x + y

    rr = ReRooting(f, g, merge, 0)
    for u, v in UV:
        rr.add_edge(u, v)



    rr.build()
    # rr.slv(2)
    ans = []
    for u in range(1, N+1):
        ans.append(rr.slv(u))

    print(*ans)


if __name__ == '__main__':
    # atcoder_dp_dp_v()
    atcoder_abc60_f()
    # codeforces_1324_f()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def __dfs1(self, u, p):
        o = []
        s = [(u, -1)]
        while s:
            u, p = s.pop()
            o.append((u, p))
            for v in self.tree[u]:
                if v == p:
                    continue
                s.append((v, u))

        for u, p in reversed(o):
            r = self.ie
            for v in self.tree[u]:
                if v == p:
                    continue
                # ep(u_, v, self.dp)
                r = self.merge(r, self.f(self.dp[u][v], v))

            self.dp[p][u] = self.g(r, u)

    def __dfs2(self, u, p, a):
        s = [(u, p, a)]

        while s:
            u, p, a = s.pop()

            self.dp[u][p] = a

            pl = [0] * (len(self.tree[u]) + 1)
            pl[0] = self.ie
            for i, v in enumerate(self.tree[u]):
                pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

            pr = [0] * (len(self.tree[u]) + 1)
            pr[-1] = self.ie
            for i, v in reversed(list(enumerate(self.tree[u]))):
                pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

            for i, v in enumerate(self.tree[u]):
                if v == p:
                    continue
                r = self.merge(pl[i], pr[i+1])
                s.append((v, u, self.g(r, v)))

    # def __dfs1(self, u, p):
    #     r = self.ie
    #     for v in self.tree[u]:
    #         if v == p:
    #             continue
    #         self.dp[u][v] = self.__dfs1(v, u)
    #         r = self.merge(r, self.f(self.dp[u][v], v))

    #     return self.g(r, u)

    # def __dfs2(self, u, p, a):
    #     for v in self.tree[u]:
    #         if v == p:
    #             self.dp[u][v] = a
    #             break
    #     pl = [0] * (len(self.tree[u]) + 1)
    #     pl[0] = self.ie
    #     for i, v in enumerate(self.tree[u]):
    #         pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

    #     pr = [0] * (len(self.tree[u]) + 1)
    #     pr[-1] = self.ie
    #     for i, v in reversed(list(enumerate(self.tree[u]))):
    #         pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

    #     for i, v in enumerate(self.tree[u]):
    #         if v == p:
    #             continue
    #         r = self.merge(pl[i], pr[i+1])
    #         self.__dfs2(v, u, self.g(r, v))

    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)


def atcoder_dp_dp_v():
    # https://atcoder.jp/contests/dp/tasks/dp_v
    # https://atcoder.jp/contests/dp/submissions/16666380
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)-1)


def atcoder_abc60_f():
    # https://atcoder.jp/contests/abc160/tasks/abc160_f
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    M = 10**9+7

    from functools import reduce

    fact = [1]
    for i in range(1, 10**6):
        fact.append(fact[-1]*i % M)

    def f(x, _):
        c = x[0]
        s = x[1]
        c *= pow(fact[s], M-2, M)
        c %= M
        return (c, s)

    def g(x, _):
        c = x[0]
        s = x[1]
        c *= fact[s]
        c %= M
        return (c, s+1)

    def merge(x, y):
        return (x[0]*y[0]%M, x[1]+y[1])

    rr = ReRooting(f, g, merge, (1, 0))
    for a, b in AB:
        rr.add_edge(a, b)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)[0])




if __name__ == '__main__':
    # atcoder_dp_dp_v()
    atcoder_abc60_f()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-


from collections import defaultdict

class ReRooting:
    def __init__(self, f, g, merge, ie):
        self.tree = defaultdict(list)
        self.f = f
        self.g = g
        self.merge = merge
        self.ie = ie
        self.dp = defaultdict(dict)

    def add_edge(self, u, v):
        self.tree[u].append(v)
        self.tree[v].append(u)

    def __dfs1(self, u, p):
        o = []
        s = [(u, -1)]
        while s:
            u, p = s.pop()
            o.append((u, p))
            for v in self.tree[u]:
                if v == p:
                    continue
                s.append((v, u))

        for u, p in reversed(o):
            r = self.ie
            for v in self.tree[u]:
                if v == p:
                    continue
                # ep(u_, v, self.dp)
                r = self.merge(r, self.f(self.dp[u][v], v))

            self.dp[p][u] = self.g(r, u)

    def __dfs2(self, u, p, a):
        s = [(u, p, a)]

        while s:
            u, p, a = s.pop()

            self.dp[u][p] = a

            pl = [0] * (len(self.tree[u]) + 1)
            pl[0] = self.ie
            for i, v in enumerate(self.tree[u]):
                pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

            pr = [0] * (len(self.tree[u]) + 1)
            pr[-1] = self.ie
            for i, v in reversed(list(enumerate(self.tree[u]))):
                pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

            for i, v in enumerate(self.tree[u]):
                if v == p:
                    continue
                r = self.merge(pl[i], pr[i+1])
                s.append((v, u, self.g(r, v)))

    # def __dfs1(self, u, p):
    #     r = self.ie
    #     for v in self.tree[u]:
    #         if v == p:
    #             continue
    #         self.dp[u][v] = self.__dfs1(v, u)
    #         r = self.merge(r, self.f(self.dp[u][v], v))

    #     return self.g(r, u)

    # def __dfs2(self, u, p, a):
    #     for v in self.tree[u]:
    #         if v == p:
    #             self.dp[u][v] = a
    #             break
    #     pl = [0] * (len(self.tree[u]) + 1)
    #     pl[0] = self.ie
    #     for i, v in enumerate(self.tree[u]):
    #         pl[i+1] = self.merge(pl[i], self.f(self.dp[u][v], v))

    #     pr = [0] * (len(self.tree[u]) + 1)
    #     pr[-1] = self.ie
    #     for i, v in reversed(list(enumerate(self.tree[u]))):
    #         pr[i] = self.merge(pr[i+1], self.f(self.dp[u][v], v))

    #     for i, v in enumerate(self.tree[u]):
    #         if v == p:
    #             continue
    #         r = self.merge(pl[i], pr[i+1])
    #         self.__dfs2(v, u, self.g(r, v))

    def build(self, root=1):
        self.__dfs1(root, -1)
        self.__dfs2(root, -1, self.ie)

    def slv(self, u):
        r = self.ie
        for v in self.tree[u]:
            r = self.merge(r, self.f(self.dp[u][v], v))

        return self.g(r, u)


def atcoder_dp_dp_v():
    # https://atcoder.jp/contests/dp/tasks/dp_v
    # https://atcoder.jp/contests/dp/submissions/16664670
    N, M = map(int, input().split())
    XY = [list(map(int, input().split())) for _ in range(N-1)]

    f = lambda x, y: x
    g = lambda x, y: x + 1
    merge = lambda x, y: (x * y) % M
    rr = ReRooting(f, g, merge, 1)
    for x, y in XY:
        rr.add_edge(x, y)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u))


def atcoder_abc60_f():
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N-1)]

    M = 10**9+7

    from functools import reduce

    fact = [1]
    for i in range(1, 10**6):
        fact.append(fact[-1]*i % M)

    def f(x, _):
        c = x[0]
        s = x[1]
        c *= pow(fact[s], M-2, M)
        c %= M
        return (c, s)

    def g(x, _):
        c = x[0]
        s = x[1]
        c *= fact[s]
        c %= M
        return (c, s+1)

    def merge(x, y):
        return (x[0]*y[0]%M, x[1]+y[1])

    rr = ReRooting(f, g, merge, (1, 0))
    for a, b in AB:
        rr.add_edge(a, b)

    rr.build()
    for u in range(1, N+1):
        print(rr.slv(u)[0])




if __name__ == '__main__':
    # atcoder_dp_dp_v()
    atcoder_abc60_f()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1<<30)
mod = 10**9+7
def inv(x):
    return pow(x,mod-2,mod)
def dfs_size(x):
    sizex = 1
    for y in edges[x]:
        if y != parent[x]:
            parent[y] = x
            sizex += dfs_size(y)
    size[x] = sizex
    return sizex
def dfs_dp(x):
    dpx = 1
    for y in edges[x]:
        if y != parent[x]:
            dpx *= dfs_dp(y)
            dpx *= inv_fac[size[y]]
            dpx %= mod
    dpx *= fac[size[x]-1]
    dpx %= mod
    dp[x] = dpx
    return dpx

def dfs_ans(x):
    ansx = 1
    if x != 1:
        for y in edges[x]:
            if y != parent[x]:
                ansx *= dp[y]
                ansx *= inv_fac[size[y]]
                ansx %= mod
            else:
                dpy = ans[y]
                dpy *= inv_fac[N-1]
                dpy *= fac[size[x]]
                dpy *= fac[N-size[x]-1]
                dpy *= inv(dp[x])
                dpy %= mod
                ansx *= dpy
                ansx *= inv_fac[N-size[x]]
                ansx %= mod
        ansx *= fac[N-1]
        ansx %= mod
        ans[x] = ansx
    for y in edges[x]:
        if y != parent[x]:
            dfs_ans(y)
N = int(input())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
size = [0]*(N+1)
parent = [0]*(N+1)
dfs_size(1)
fac = [1]
for i in range(1,N+1):
    fac.append(fac[-1]*i % mod)
inv_fac = [inv(fac[N])]
for i in range(1,N+1)[::-1]:
    inv_fac.append(inv_fac[-1]*i % mod)
inv_fac = inv_fac[::-1]
dp = [0]*(N+1)
dfs_dp(1)
ans = [0]*(N+1)
ans[1] = dp[1]
dfs_ans(1)
for i in ans[1:]:
    print(i)

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().rstrip().split()
def S(): return sys.stdin.readline().rstrip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]

mod=10**9+7

n=I()

fac = [1] * (n + 1)
inv = [1] * (n + 1)
for j in range(1, n + 1):
    fac[j] = fac[j-1] * j % mod

inv[n] = pow(fac[n], mod-2, mod)
for j in range(n-1, -1, -1):
    inv[j] = inv[j+1] * (j+1) % mod


def comb(n, r):
    if r > n or n < 0 or r < 0:
        return 0
    return fac[n] * inv[n - r] * inv[r] % mod



G=[[]for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b-1] += [a-1]

cnt=[-1]*n
par=[-1]*n
def f(x):
    ret=1
    for y in G[x]:
        if par[x]==y:
            continue
        par[y]=x
        ret+=f(y)
    cnt[x]=ret
    return ret

f(0)
D=[0]*n
def tree_dp(x):
    c = 1
    remain_v = cnt[x] - 1
    for y in G[x]:
        if y == par[x]:
            continue
        c = c * tree_dp(y) * comb(remain_v, cnt[y]) % mod
        remain_v -= cnt[y]
    D[x] = c
    if x: return c

tree_dp(0)
ans=[0]*n
ans[0]=D[0]



q=deque([0])
while q:
    e=q.popleft()
    for d in G[e]:
        if d==par[e]:
            continue
        ans[d]=pow(comb(n-1,cnt[d])*D[d],mod-2,mod)*ans[e]*comb(n-1,cnt[d]-1)*D[d]%mod
        q+=[d]

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