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
import numpy as np

def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)


mod = 10**9+7

def pow_mod(base, exp):  # [numba_pow, "i8(i8,i8)"],
    # mod はグローバル変数を参照
    exp %= mod - 1
    res = 1
    while exp:
        if exp % 2:
            res = res * base % mod
        base = base * base % mod
        exp //= 2
    return res

def comb_cunstruct(n):
    # mod はグローバル変数を参照
    fac = np.empty(n+1, dtype=np.int64)
    facinv = np.empty(n+1, dtype=np.int64)
    fac[0] = f = 1
    for i in range(1, n+1):
        f = f * i % mod
        fac[i] = f
    f = pow_mod(f, -1)
    for i in range(n, -1, -1):
        facinv[i] = f
        f = f * i % mod
    return fac, facinv

def comb(n, r, fac, facinv):
    # mod はグローバル変数を参照
    return fac[n] * facinv[r] % mod * facinv[n-r] % mod

def rerooting(n, edges, fac, facinv):
    # 全方位木 dp
    # 参考: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    identity = (1, 0)
    def merge(a, b):
        return a[0] * b[0] % mod * comb(a[1] + b[1], a[1], fac, facinv) % mod, a[1] + b[1]
    def add_node(value, idx):
        return value[0], value[1] + 1
    merge(identity, identity)

    G = [[0]*0 for _ in range(n)]
    G_idxs = [[0]*0 for _ in range(n)]  # 自分を指すノードのインデックス
    for idx_edges in range(n-1):
        a, b = edges[idx_edges]
        G_idxs[a].append(len(G[b]))
        G_idxs[b].append(len(G[a]))
        G[a].append(b)
        G[b].append(a)
    # step 1
    parents = [0] * n
    order = []  # 行きがけ順
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order.append(v)
        for u in G[v]:
            if p != u:
                stack.append(u)
                parents[u] = v
    subtree_res = [[identity]*len(Gv) for Gv in G]
    # 下から登る
    for v in order[:0:-1]:
        p = parents[v]
        result = identity
        for idx_Gv, (u, subtree_res_v_i) in enumerate(zip(G[v], subtree_res[v])):
            if p == u:
                parent_idx = idx_Gv
            else:
                result = merge(result, subtree_res_v_i)
        idx_p2v = G_idxs[v][parent_idx]
        subtree_res[p][idx_p2v] = add_node(result, v)
    # step 2
    # 上から降りる
    results = [identity] * n
    for v in order:
        subtree_res_v = subtree_res[v]
        cum = identity
        cum_from_tail = [identity]
        for r in subtree_res_v[:0:-1]:
            cum = merge(r, cum)
            cum_from_tail.append(cum)
        cum_from_tail.reverse()
        cum = identity
        for r, cum_t, u, idx_u2v in zip(subtree_res_v, cum_from_tail, G[v], G_idxs[v]):
            result = add_node(merge(cum, cum_t), v)
            subtree_res[u][idx_u2v] = result
            cum = merge(cum, r)
        results[v] = add_node(cum, v)
    return np.array(results)


numba_compile([
    [pow_mod, "i8(i8,i8)"],
    [comb_cunstruct, "Tuple((i8[:],i8[:]))(i8,)"],
    [comb, "i8(i8,i8,i8[:],i8[:])"],
    [rerooting, "(i8,i8[:,:],i8[:],i8[:])"],
])


def main():
    N = int(sys.stdin.buffer.readline())
    AB = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N-1, 2) - 1
    fac, facinv = comb_cunstruct(202020)
    Ans = rerooting(N, AB, fac, facinv)
    print("\n".join(map(str, Ans[:, 0].tolist())))

main()

Submission status: Accepted

Solution code:
def rerooting(n, edges, identity, merge, add_node):
    # 全方位木 dp
    # 参考: https://qiita.com/keymoon/items/2a52f1b0fb7ef67fb89e
    G = [[] for _ in range(n)]
    G_idxs = [[] for _ in range(n)]  # 自分を指すノードのインデックス
    for a, b in edges:
        G_idxs[a].append(len(G[b]))
        G_idxs[b].append(len(G[a]))
        G[a].append(b)
        G[b].append(a)
    # step 1
    parents = [0] * n
    order = []  # 行きがけ順
    stack = [0]
    parents[0] = -1
    while stack:
        v = stack.pop()
        p = parents[v]
        order.append(v)
        for u in G[v]:
            if p != u:
                stack.append(u)
                parents[u] = v
    subtree_res = [[0]*len(Gv) for Gv in G]
    # 下から登る
    for v in order[:0:-1]:
        p = parents[v]
        result = identity
        for idx_Gv, (u, subtree_res_v_i) in enumerate(zip(G[v], subtree_res[v])):
            if p == u:
                parent_idx = idx_Gv
            else:
                result = merge(result, subtree_res_v_i)
        idx_p2v = G_idxs[v][parent_idx]
        subtree_res[p][idx_p2v] = add_node(result, v)
    # step 2
    # 上から降りる
    results = [0] * n
    for v in order:
        subtree_res_v = subtree_res[v]
        cum = identity
        cum_from_tail = [identity]
        for r in subtree_res_v[:0:-1]:
            cum = merge(r, cum)
            cum_from_tail.append(cum)
        cum_from_tail.reverse()
        cum = identity
        for r, cum_t, u, idx_u2v in zip(subtree_res_v, cum_from_tail, G[v], G_idxs[v]):
            result = add_node(merge(cum, cum_t), v)
            subtree_res[u][idx_u2v] = result
            cum = merge(cum, r)
        results[v] = add_node(cum, v)
    return results


class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

    def __call__(self, n, r):  # self.C と同じ
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

def main():
    N = int(input())
    AB = [list(map(lambda x: int(x)-1, input().split())) for _ in range(N-1)]
    mod = 10**9 + 7
    comb = Combination(202020)
    identity = (1, 0)
    merge = lambda a, b: (a[0] * b[0] % mod * comb(a[1]+b[1], a[1]) % mod, a[1] + b[1])
    add_node = lambda value, idx: (value[0], value[1]+1)
    Ans = rerooting(N, AB, identity, merge, add_node)
    print("\n".join(str(ans) for ans, _ in Ans))

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(505050)

class Combination:
    def __init__(self, n_max, mod=10**9+7):
        # O(n_max + log(mod))
        self.mod = mod
        f = 1
        self.fac = fac = [f]
        for i in range(1, n_max+1):
            f = f * i % mod
            fac.append(f)
        f = pow(f, mod-2, mod)
        self.facinv = facinv = [f]
        for i in range(n_max, 0, -1):
            f = f * i % mod
            facinv.append(f)
        facinv.reverse()

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

Siz = [0] * (N+1)
A = [0] * (N+1)
mod = 10**9 + 7
comb = Combination(202020)
def dfs1(v, p):
    siz = 1
    an_prod = 1
    an_numer = 0
    an_denom = 1
    for u in G[v]:
        if u != p:
            s, a = dfs1(u, v)
            siz += s
            an_prod = an_prod * a % mod
            an_numer += s
            an_denom = an_denom * comb.facinv[s] % mod
    an_numer = comb.fac[an_numer]
    an = an_numer * an_denom % mod * an_prod % mod
    Siz[v] = siz
    A[v] = an
    return siz, an

_, ans = dfs1(1, 0)
# for i in range(1, N+1):
#     print(i, dfs1(i, 0))

Ans = [0] * (N+1)
Ans[1] = ans

def dfs2(v, p, an_p):
    siz_v = Siz[v]
    if v==1:
        ans = A[v]
    else:
        ans = A[v] * comb.fac[N-1] % mod * comb.facinv[siz_v-1] % mod * an_p % mod * comb.facinv[N-siz_v] % mod
        Ans[v] = ans
    for u in G[v]:
        if p != u:
            siz_u = Siz[u]
            an = ans * comb.facinv[N-1] % mod * comb.fac[N-1-siz_u] % mod * comb.fac[siz_u] % mod * pow(A[u], mod-2, mod) % mod
            dfs2(u, v, an)

dfs2(1, 0, None)
print("\n".join(map(str, Ans[1:])))

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
def main():
    n=int(input())
    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 #出力の制限
    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 )

    ki=[[] for _ in range(n)]
    for _ in range(n-1):
        a,b=map(int,input().split())
        a,b=a-1,b-1
        ki[a].append(b)
        ki[b].append(a)
    memo={} # memo[(p,v)]:p->vの部分木のサイズ、整数の書き方
    def dfs(p,v):
        if (p,v) in memo:return memo[(p,v)]
        size,pat=0,1
        tmps,tmpp=1,1
        deg=len(ki[v])
        for nv in ki[v]:
            if nv==p:continue
            si,pi=dfs(v,nv)
            size+=si
            tmps*=g2[si]
            tmps%=mod
            tmpp*=pi
            tmpp%=mod
        pat=(g1[size]*tmps*tmpp)%mod
        memo[(p,v)]=(size+1,pat)
        return (size+1,pat)
    ans=[0]*n
    def bfs(p,v,res):
        if p!=-1:memo[(v,p)]=res
        deg=len(ki[v])
        tmps,tmpp=1,1
        for i in range(deg):
            si,pi=memo[(v,ki[v][i])]
            tmps*=g2[si]
            tmpp*=pi
            tmps%=mod
            tmpp%=mod

        ans[v]=g1[n-1]*tmps*tmpp
        ans[v]%=mod

        dpl=[1]*(deg+1)
        dpr=[1]*(deg+1)
        tmp=1
        for i in range(deg):
            si,pi=memo[(v,ki[v][i])]
            tmp*=pi*g2[si]
            tmp%=mod
            dpl[i+1]=tmp
        tmp=1
        for i in range(deg-1,-1,-1):
            si,pi=memo[(v,ki[v][i])]
            tmp*=pi*g2[si]
            tmp%=mod
            dpr[i]=tmp
        for i in range(deg):
            nv=ki[v][i]
            if p==nv:continue
            bfs(v,nv,(n-memo[(v,nv)][0],(g1[n-1-memo[(v,nv)][0]]*dpl[i]*dpr[i+1])%mod))
    dfs(-1,0)
    #print(memo)
    bfs(-1,0,0)
    print(*ans,sep='\n')
    #print(memo)

if __name__=='__main__':
    main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    """
    根を固定させたバージョンをまず考える．
    木dpをしたいのでノードに通り数を持たせる．
    通り数が同じでも部分木のサイズが異なると，親要素の通り数は変わる（1-2-3-4で2が親のときを想起）ので
    通り数と部分木のサイズは持つ必要あり．
    子要素が2つの時を考える，
    左がa通り+b個
    右がc通り+d個
    a+cを並び替えてa側でb通り，c側でd通りなので
    (a+c)Ca *b*d
    ということは，各子要素の通り数をai，サイズをbiとして，
    Πai * (Σbi)!/(Π(bi!))
    シグマの部分だけ後回し（調整）
    
    あとは全方位化
    """
    N=I()

    fact=[1,1]
    factinv=[1,1]
    inv=[0,1]
    
    for i in range(2, 2*N+10):
        fact.append((fact[-1] * i) % mod)
        inv.append((-inv[mod % i] * (mod // i)) % mod)
        factinv.append((factinv[-1] * inv[-1]) % mod)
    
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        a,b=MI()
        a-=1
        b-=1
        adj[a].append(b)
        adj[b].append(a)
        
    import queue
    
    P=[-1]*N#親リスト
    Q=queue.Queue()#BFSに使う
    R=[]#BFSでトポソしたものを入れる
    
    Q.put(0)#1回目では0を根とする
    
    #トポソ########################
    while not Q.empty():
        v=Q.get()
        R.append(v)
        for nv in adj[v]:
            if nv!=P[v]:
                P[nv]=v
                adj[nv].remove(v)#親につながる辺を消しておく
                Q.put(nv)
    
    #1が上りで，2が下り
    size1=[1]*N
    size2=[0]*N
    dp1=[1]*N
    dp2=[1]*N
    
    #先にサイズは求めておく
    for v in R[1:][::-1]:
        size1[P[v]]+=size1[v]
        
    for v in range(N):
        size2[v]=N-size1[v]
    
    for v in R[1:][::-1]:#根以外を後ろから
        dp1[v]=(dp1[v]*fact[size1[v]-1])%mod
        p=P[v]
        dp1[p]=(dp1[p]*dp1[v]*factinv[size1[v]])%mod
        
    #根だけ
    dp1[R[0]]=(dp1[R[0]]*fact[size1[R[0]]-1])%mod

        
    #累積和ではなく逆元で．ここではしっかり根から決まっていく
    for v in R[1:]:
        p=P[v]
        
        #下り部分，根側
        temp=dp2[p]
        
        # 親要素のdp1から自分のdp1を引くことで，親周りの自分以外の寄与を求めた
        temp2=(dp1[p]*pow(dp1[v],mod-2,mod))%mod
        temp=(temp*temp2)%mod
        
        
        temp=(temp*factinv[size1[p]-1]*fact[size1[v]])%mod#親のところは親要素の分を加味して1引く
        temp=(temp*factinv[size2[p]]*fact[size2[v]-1])%mod#逆側から見たときは，vがpの親に見える
        dp2[v]=temp
        
    for i in range(N):
        #上側と下側の塗り方を考慮して（これは結局，一番最初のa+bCaに近い）
        ans=(dp1[i]*dp2[i]*fact[N-1]*factinv[size1[i]-1]*factinv[size2[i]])%mod
        print(ans)
        
        
        
        
    
    
        
  
        

main()

Submission status: Accepted

Solution code:
class Graph:
    def __init__(self, n_vertices, edges, directed=True):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]
            if self.directed:
                for u,v in self.edges:
                    adj[u].append(v)
            else:
                for u,v in self.edges:
                    adj[u].append(v)
                    adj[v].append(u)
            self._adj = adj
            return adj

class RootedTree(Graph):
    def __init__(self, n_vertices, edges, root_vertex=0):
        self.root = root_vertex
        super().__init__(n_vertices, edges, False)

    @property
    def parent(self):
        try:
            return self._parent
        except AttributeError:
            adj = self.adj
            parent = [None]*self.n_vertices
            parent[self.root] = -1
            stack = [self.root]
            for _ in range(self.n_vertices):
                v = stack.pop()
                for u in adj[v]:
                    if parent[u] is None:
                        parent[u] = v
                        stack.append(u)
            self._parent = parent
            return parent

    @property
    def children(self):
        try:
            return self._children
        except AttributeError:
            children = [None]*self.n_vertices
            for v,(l,p) in enumerate(zip(self.adj,self.parent)):
                children[v] = [u for u in l if u != p]
            self._children = children
            return children

    @property
    def dfs_order(self):
        try:
            return self._dfs_order
        except AttributeError:
            order = [None]*self.n_vertices
            children = self.children
            stack = [self.root]
            for i in range(self.n_vertices):
                v = stack.pop()
                order[i] = v
                for u in children[v]:
                    stack.append(u)
            self._dfs_order = order
            return order

from functools import reduce
from itertools import accumulate,chain
def rerooting(rooted_tree, merge, identity, finalize):
    """
    merge: (T,T) -> T, (T, merge)はモノイド
    identity: 単位元
    finalize: (T, V, V) -> T
 
    以下の形で書けるdpは対応可能
    dp[u,v] = finalize(merge(dp[v,k] for k in adj[v] if k != u), u, v)
    ただし(u,v)は辺
    """
    N = rooted_tree.n_vertices
    parent = rooted_tree.parent
    children = rooted_tree.children
    order = rooted_tree.dfs_order

    # from leaf to parent
    dp_down = [None]*N
    for v in reversed(order):
        dp_down[v] = finalize(reduce(merge,
            (dp_down[c] for c in children[v]),
            identity), parent[v], v)

    # from parent to leaf
    dp_up = [None]*N
    dp_up[0] = identity
    for v in order:
        if len(children[v]) == 0:
            continue
        temp = (dp_up[v],)+tuple(dp_down[u] for u in children[v])+(identity,)
        left = accumulate(temp[:-2],merge)
        right = tuple(accumulate(reversed(temp[2:]),merge))
        for u,l,r in zip(children[v],left,reversed(right)):
            dp_up[u] = finalize(merge(l,r), u, v)

    res = [None]*N
    for v,l in enumerate(children):
        res[v] = reduce(merge,
                    (dp_down[u] for u in children[v]),
                    identity)
        res[v] = merge(res[v], dp_up[v])
    return res,dp_up,dp_down

def solve(N,edges):
    MOD = 10**9+7

    factorio = [None]*(N+1)
    factorio[0] = 1
    t = 1
    for i in range(1,N+1):
        t *= i
        t %= MOD
        factorio[i] = t

    factorio_inv = [None]*(N+1)
    factorio_inv[0] = 1
    t = pow(factorio[-1],MOD-2,MOD)
    for i in reversed(range(1,N+1)):
        factorio_inv[i] = t
        t *= i
        t %= MOD

    def merge(x,y):
        cx,nx = x
        cy,ny = y
        c = cx*cy*factorio[nx+ny]*factorio_inv[nx]*factorio_inv[ny]
        return c%MOD, nx+ny

    def finalize(x, u, v):
        c,n = x
        return c,n+1

    t = RootedTree(N,edges)
    res,_,_ = rerooting(t, merge, (1,0), finalize)

    return (k for k,n in res)


import sys
if __name__ == '__main__':
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
     
    N = int(readline())
    m = map(lambda x: int(x)-1, read().split())
    edges = zip(m, m)

    print(*solve(N, edges), sep='\n')

Submission status: Accepted

Solution code:
class Graph:
    def __init__(self, n_vertices, edges, directed=True):
        self.n_vertices = n_vertices
        self.edges = edges
        self.directed = directed

    @property
    def adj(self):
        try:
            return self._adj
        except AttributeError:
            adj = [[] for _ in range(self.n_vertices)]
            if self.directed:
                for u,v in self.edges:
                    adj[u].append(v)
            else:
                for u,v in self.edges:
                    adj[u].append(v)
                    adj[v].append(u)
            self._adj = adj
            return adj

class RootedTree(Graph):
    def __init__(self, n_vertices, edges, root_vertex=0):
        self.root = root_vertex
        super().__init__(n_vertices, edges, False)

    @property
    def parent(self):
        try:
            return self._parent
        except AttributeError:
            adj = self.adj
            parent = [None]*self.n_vertices
            parent[self.root] = -1
            stack = [self.root]
            for _ in range(self.n_vertices):
                v = stack.pop()
                for u in adj[v]:
                    if parent[u] is None:
                        parent[u] = v
                        stack.append(u)
            self._parent = parent
            return parent

    @property
    def children(self):
        try:
            return self._children
        except AttributeError:
            children = [None]*self.n_vertices
            for v,(l,p) in enumerate(zip(self.adj,self.parent)):
                children[v] = [u for u in l if u != p]
            self._children = children
            return children

    @property
    def dfs_order(self):
        try:
            return self._dfs_order
        except AttributeError:
            order = [None]*self.n_vertices
            children = self.children
            stack = [self.root]
            for i in range(self.n_vertices):
                v = stack.pop()
                order[i] = v
                for u in children[v]:
                    stack.append(u)
            self._dfs_order = order
            return order

from functools import reduce
from itertools import accumulate,chain
def rerooting(rooted_tree, merge, identity, finalize):
    """
    merge: (T,T) -> T, (T, merge)はモノイド
    identity: 単位元
    finalize: (T, V, V) -> T
 
    以下の形で書けるdpは対応可能
    dp[u,v] = finalize(merge(dp[v,k] for k in adj[v] if k != u), u, v)
    ただし(u,v)は辺
    """
    N = rooted_tree.n_vertices
    parent = rooted_tree.parent
    children = rooted_tree.children
    order = rooted_tree.dfs_order

    # from leaf to parent
    dp_down = [None]*N
    for v in reversed(order):
        dp_down[v] = finalize(reduce(merge,
            (dp_down[c] for c in children[v]),
            identity), parent[v], v)

    # from parent to leaf
    dp_up = [None]*N
    dp_up[0] = identity
    for v in order:
        if len(children[v]) == 0:
            continue
        temp = (dp_up[v],)+tuple(dp_down[u] for u in children[v])+(identity,)
        left = accumulate(temp[:-2],merge)
        right = tuple(accumulate(reversed(temp[2:]),merge))
        for u,l,r in zip(children[v],left,reversed(right)):
            dp_up[u] = finalize(merge(l,r), u, v)

    res = [None]*N
    for v,l in enumerate(children):
        res[v] = reduce(merge,
                    (dp_down[u] for u in children[v]),
                    identity)
        res[v] = merge(res[v], dp_up[v])
    return res,dp_up,dp_down

def solve(N,edges):
    MOD = 10**9+7

    factorio = [None]*(N+1)
    factorio[0] = 1
    t = 1
    for i in range(1,N+1):
        t *= i
        t %= MOD
        factorio[i] = t

    factorio_inv = [None]*(N+1)
    factorio_inv[0] = 1
    t = pow(factorio[-1],MOD-2,MOD)
    for i in reversed(range(1,N+1)):
        factorio_inv[i] = t
        t *= i
        t %= MOD

    def merge(x,y):
        cx,nx = x
        cy,ny = y
        c = cx*cy*factorio[nx+ny]*factorio_inv[nx]*factorio_inv[ny]
        return c%MOD, nx+ny

    def finalize(x, u, v):
        c,n = x
        return c,n+1

    t = RootedTree(N,edges)
    res,_,_ = rerooting(t, merge, (1,0), finalize)

    for k,n in res:
        print(k)


import sys
if __name__ == '__main__':
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
     
    N = int(readline())
    m = map(lambda x: int(x)-1, read().split())
    edges = zip(m, m)

    solve(N, edges)

Submission status: Accepted

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

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

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

mod=10**9+7

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

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

FACT_INV.reverse()

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

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

while Q:
    x=Q.pop()
    TOP_SORT.append(x)

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

Children=[1]*(N+1)
ANS_UP=[1]*(N+1)

for x in TOP_SORT[::-1]:
    sumchild=0
    for to in E[x]:
        if to==P[x]:
            continue
        sumchild+=Children[to]
        ANS_UP[x]=ANS_UP[x]*Combi(sumchild,Children[to])%mod
                    
    Children[P[x]]+=Children[x]
    ANS_UP[P[x]]=ANS_UP[P[x]]*ANS_UP[x]%mod

ANS_DOWN=[1]*(N+1)

for x in TOP_SORT:
    if x==1:
        continue
    ANS_DOWN[x]=ANS_DOWN[P[x]]*ANS_UP[P[x]]*Combi(N-Children[x]-1,N-Children[P[x]])*pow(ANS_UP[x],mod-2,mod)*pow(Combi(Children[P[x]]-1,Children[x]),mod-2,mod)%mod

for i in range(1,N+1):
    if i==1:
        print(ANS_UP[1])
    else:
        ANS=ANS_DOWN[i]%mod

        sumchild=0
        for to in E[i]:
            if to==P[i]:
                sumchild+=N-Children[i]
                ANS=ANS*Combi(sumchild,N-Children[i])%mod
            else:                  
                sumchild+=Children[to]
                ANS=ANS*ANS_UP[to]*Combi(sumchild,Children[to])%mod

        print(ANS)

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
input=sys.stdin.readline


class Reroot:
    def __init__(self, N, e, merge, f, g):
        self.G = defaultdict(list)
        self.parents = [-1]*(N+1)
        self.dp = defaultdict(lambda: defaultdict(int))
        self.merge = merge
        self.f = f
        self.g = g
        self.e = e

    def add_edge(self, s, t):
        self.G[s].append(t)

    def build(self):
        self.dfs1(1)
        self.dfs2(1)
        return self.dp

    def dfs1(self, s):
        l = []
        q = [1]
        while q:
            s = q.pop()
            l.append(s)
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                self.parents[t] = s
                q.append(t)

        for s in l[::-1]:
            v = self.e
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                v = self.merge(v, self.f(self.dp[s][t], s, t))
            self.dp[self.parents[s]][s] = self.g(v, self.parents[s], s)

    def dfs2(self, s):
        q = [(s, self.e)]
        while q:
            s, dp_p = q.pop()
            par = self.parents[s]
            self.dp[s][par] = dp_p

            size = len(self.G[s])
            ac_l = [self.e] * (size+1)
            ac_r = [self.e] * (size+1)
            for i, t in enumerate(self.G[s]):
                ac_l[i+1] = self.merge(ac_l[i], self.f(self.dp[s][t], s, t))
            for i, t in enumerate(self.G[s][::-1]):
                ac_r[size-i-1] = self.merge(ac_r[size-i], self.f(self.dp[s][t], s, t))
            self.dp[-1][s] = self.g(ac_l[size], -1, s)

            for i, t in enumerate(self.G[s]):
                if t == par:
                    continue
                q.append((t, self.g(self.merge(ac_l[i], ac_r[i+1]), t, s)))


def solve():
    N = int(input())

    MOD = 10**9+7
    n = N
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    d = defaultdict(list)

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

    merge1 = lambda x,y:x+y
    f1 = lambda x, par, s:x
    g1 = lambda x, par, s:x+1
    e1 = 0
    tree1 = Reroot(N, e1, merge1, f1, g1)

    merge2 = lambda x,y:(x*y)%MOD
    f2 = lambda x, par, s:(x*rev[tree1.dp[par][s]])%MOD
    g2 = lambda x, par, s:(x*fac[tree1.dp[par][s]-1])%MOD
    e2 = 1
    tree2 = Reroot(N, e2, merge2, f2, g2)

    for _ in range(N-1):
        a, b = map(int, input().split())
        tree2.add_edge(a, b)
        tree2.add_edge(b, a)
        tree1.add_edge(a, b)
        tree1.add_edge(b, a)

    tree1.build()
    ans = tree2.build()

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


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
input=sys.stdin.readline


class Reroot:
    def __init__(self, N, e, merge, f, g):
        self.G = defaultdict(list)
        self.parents = [-1]*(N+1)
        self.dp = defaultdict(lambda: defaultdict(int))
        self.merge = merge
        self.f = f
        self.g = g
        self.e = e

    def add_edge(self, s, t):
        self.G[s].append(t)

    def build(self):
        self.dfs1(1)
        self.dfs2(1)
        return self.dp

    def dfs1(self, s):
        l = []
        q = [1]
        while q:
            s = q.pop()
            l.append(s)
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                self.parents[t] = s
                q.append(t)

        for s in l[::-1]:
            v = self.e
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                v = self.merge(v, self.f(self.dp[s][t], s, t))
            self.dp[self.parents[s]][s] = self.g(v, self.parents[s], s)

    def dfs2(self, s):
        q = [(s, self.e)]
        while q:
            s, dp_p = q.pop()
            par = self.parents[s]
            for t in self.G[s]:
                if t == par:
                    self.dp[s][t] = dp_p

            size = len(self.G[s])
            ac_l = [self.e] * (size+1)
            ac_r = [self.e] * (size+1)
            for i, t in enumerate(self.G[s]):
                ac_l[i+1] = self.merge(ac_l[i], self.f(self.dp[s][t], s, t))
            for i, t in enumerate(self.G[s][::-1]):
                ac_r[size-i-1] = self.merge(ac_r[size-i], self.f(self.dp[s][t], s, t))
            self.dp[-1][s] = self.g(ac_l[size], -1, s)

            for i, t in enumerate(self.G[s]):
                if t == par:
                    continue
                q.append((t, self.g(self.merge(ac_l[i], ac_r[i+1]), t, s)))


def solve():
    N = int(input())

    MOD = 10**9+7
    n = N
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    d = defaultdict(list)

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

    merge1 = lambda x,y:x+y
    f1 = lambda x, par, s:x
    g1 = lambda x, par, s:x+1
    e1 = 0
    tree1 = Reroot(N, e1, merge1, f1, g1)

    merge2 = lambda x,y:(x*y)%MOD
    f2 = lambda x, par, s:(x*rev[tree1.dp[par][s]])%MOD
    g2 = lambda x, par, s:(x*fac[tree1.dp[par][s]-1])%MOD
    e2 = 1
    tree2 = Reroot(N, e2, merge2, f2, g2)

    for _ in range(N-1):
        a, b = map(int, input().split())
        tree2.add_edge(a, b)
        tree2.add_edge(b, a)
        tree1.add_edge(a, b)
        tree1.add_edge(b, a)

    tree1.build()
    ans = tree2.build()

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


if __name__ == "__main__":
    solve()