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:
from itertools import chain
import sys

def rerooting(N, adj, func):
    """
    func: iterable<T> -> T
    func takes all subtree dp results and 
    returns its aggregation result.
    """

    stack = [0]
    order = [None]*N
    parent = [None]*N
    parent[0] = -1
    for i in range(N):
        v = stack.pop()
        order[i] = v
        for u in adj[v]:
            if parent[u] is None:
                parent[u] = v
                stack.append(u)

    # from leaf to parent
    dp_down = [None]*N
    for v in reversed(order[1:]):
        dp_down[v] = func((dp_down[c] for c in adj[v] if c != parent[v]))

    dp_up = [None]*N
    for v in order[1:]:
        p = parent[v]
        dp_up[v] = func(
            chain(
                (dp_down[u] for u in adj[p] if u not in (v,parent[p])),
                (dp_up[p],) if p != 0 else ()))

    for v,l in enumerate(adj):
        order[v] = func(
            chain(
                (dp_down[u] for u in adj[v] if u != parent[v]),
                (dp_up[v],) if v != 0 else ()))

    return order


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

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

    adj = [[] for _ in range(N)]
    for a,b in edges:
        adj[a].append(b)
        adj[b].append(a)

    def aggregator(it):
        comb = 1
        n_children = 0
        for c, n in it:
            comb *= pow(factorio[n],MOD-2,MOD)*c
            comb %= MOD
            n_children += n
        comb *= factorio[n_children]
        comb %= MOD
        return comb, n_children+1

    res = rerooting(N,adj,aggregator)

    for k,n in res:
        print(k)


if __name__ == '__main__':
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
     
    N = int(readline())
    m = map(int, read().split())
    edges = tuple((a-1,b-1) for a,b in zip(m, m))

    solve(N, edges)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate,chain
import sys

sys.setrecursionlimit(10000000)

MOD = 10**9+7

# factorio = tuple(chain((1,),accumulate(range(1,N+1), func=lambda x,y: (x*y)%MOD)))

from itertools import chain
def rerooting(N, adj, func):
    """
    func: iterable<T> -> T
    func takes all subtree dp results and 
    returns its aggregation result.
    """

    stack = [0]
    order = [None]*N
    parent = [None]*N
    parent[0] = -1
    for i in range(N):
        v = stack.pop()
        order[i] = v
        for u in adj[v]:
            if parent[u] is None:
                parent[u] = v
                stack.append(u)

    # from leaf to parent
    dp_down = [None]*N
    for v in reversed(order[1:]):
        dp_down[v] = func((dp_down[c] for c in adj[v] if c != parent[v]))

    dp_up = [None]*N
    for v in order[1:]:
        p = parent[v]
        dp_up[v] = func(
            chain(
                (dp_down[u] for u in adj[p] if u not in (v,parent[p])),
                (dp_up[p],) if p != 0 else ()))

    for v,l in enumerate(adj):
        order[v] = func(
            chain(
                (dp_down[u] for u in adj[v] if u != parent[v]),
                (dp_up[v],) if v != 0 else ()))

    return order


def solve(N,edges):
    factorio = [1]*(N+1)
    t = 1
    for i in range(1,N+1):
        t *= i
        t %= MOD
        factorio[i] = t

    adj = [[] for _ in range(N)]
    for a,b in edges:
        adj[a].append(b)
        adj[b].append(a)

    def aggregator(it):
        comb = 1
        n_children = 0
        for c, n in it:
            comb *= pow(factorio[n],-1,MOD)*c
            comb %= MOD
            n_children += n
        comb *= factorio[n_children]
        comb %= MOD
        return comb, n_children+1

    res = rerooting(N,adj,aggregator)

    for k,n in res:
        print(k)


if __name__ == '__main__':
    read = sys.stdin.buffer.read
    readline = sys.stdin.buffer.readline
    readlines = sys.stdin.buffer.readlines
     
    N = int(readline())
    m = map(int, read().split())
    edges = tuple((a-1,b-1) for a,b in zip(m, m))

    solve(N, edges)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


N = int(input())
MOD = 10**9+7
n = N
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)

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

@lru_cache(maxsize=None)
def dfs1(s, par=-1):
    ans = 1
    for t in d[s]:
        if t==par:continue
        ans += dfs1(t, s)
    return ans

@lru_cache(maxsize=None)
def dfs2(s, par=-1):
    ans = 1
    l = []
    for t in d[s]:
        if t==par:continue
        ans *= dfs2(t, s)
        ans %= MOD
        l.append(dfs1(t, s))
    
    m = fac[dfs1(s, par)-1]
    v = 1
    for i in l:
        v *= fac[i]
        v %= MOD
    ans *= (m * pow(v, MOD-2, MOD))
    ans %= MOD
    return ans


for i in range(1, N+1):
    dfs1(i)
    print(dfs2(i))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


N = int(input())
MOD = 10**9+7
n = N
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)

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

size = [0]*(N+1)
dp = [0]*(N+1)

# @lru_cache(maxsize=None)
def dfs1(s, par):
    ans = 1
    for t in d[s]:
        if t==par:continue
        ans += dfs1(t, s)
    size[s] = ans
    return ans

# @lru_cache(maxsize=None)
def dfs2(s, par):
    ans = 1
    l = []
    for t in d[s]:
        if t==par:continue
        ans *= dfs2(t, s)
        ans %= MOD
        l.append(size[t])
    
    m = fac[size[s]-1]
    v = 1
    for i in l:
        v *= fac[i]
        v %= MOD
    ans *= (m * pow(v, MOD-2, MOD))
    ans %= MOD
    dp[s] = ans
    return ans


for i in range(1, N+1):
    dfs1(i, 0)
    dfs2(i, 0)
    print(dp[i])

Submission status: Time Limit Exceeded

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

MOD = 10**9 + 7

def MOD_inv(a):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u = u % MOD
    if u < 0:
        u += MOD
    return u

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

def dfs(G, dp, t, perm, crr, pre):
    tmp = 1
    f = False
    for nxt in G[crr]:
        if nxt == pre:
            continue
        dfs(G, dp, t, perm, nxt, crr)
        t[crr] += t[nxt]
        tmp *= dp[nxt]
        f = True
    if f:
        dp[crr] = perm[t[crr]-1]
        for nxt in G[crr]:
            if nxt == pre:
                continue
            dp[crr] *= MOD_inv(perm[t[nxt]]) * dp[nxt]
            dp[crr] %= MOD
    else:
        dp[crr] = 1

def solve(G, dp, t, perm, crr, pre, mul):
    dp[crr] *= MOD_inv(perm[t[crr]-1]) * perm[len(G)-1] * mul
    dp[crr] %= MOD
    for nxt in G[crr]:
        if nxt == pre:
            continue
        crr_t = len(G)
        crr_t -= t[nxt]
        crr_dp = dp[crr]
        crr_dp *= perm[t[nxt]] * MOD_inv(perm[len(G)-1]) * perm[len(G)-t[nxt]-1] * MOD_inv(dp[nxt])
        crr_dp %= MOD
        tmp = MOD_inv(perm[crr_t]) * crr_dp % MOD
        solve(G, dp, t, perm, nxt, crr, tmp)

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    init_Graph(G)
    t = [1]*n
    dp = [0]*n
    perm = [1]*(2 * 10**5 + 10)
    for i in range(2, 2 * 10**5 + 10):
        perm[i] = perm[i-1] * i % MOD
    dfs(G, dp, t, perm, 0, -1)
    solve(G, dp, t, perm, 0, -1, 1)
    for v in dp:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(10 ** 5 + 5)


# 2乗の木DP

def prepare(n, MOD):
    f = 1
    factorials = [1]  # 0!の分
    for m in range(1, n + 1):
        f *= m
        f %= MOD
        factorials.append(f)
    inv = pow(f, MOD - 2, MOD)
    invs = [1] * (n + 1)
    invs[n] = inv
    for m in range(n, 1, -1):
        inv *= m
        inv %= MOD
        invs[m - 1] = inv

    return factorials, invs


def nhr(factorials, invs, n, r, MOD):
    return factorials[n + r - 1] * invs[n - 1] * invs[r] % MOD


def dfs0(links):
    q = [(0, -1)]
    while q:
        v, p = q.pop()
        links[v].discard(p)
        links[v] = list(links[v])
        q.extend((u, v) for u in links[v])


def dfs1(links, st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd):
    q = [(0, -1, 0)]
    while q:
        v, p, o = q.pop()
        if o == 0:
            # 初回訪問
            q.append((v, p, 1))
            q.extend((u, v, 0) for u in links[v])
        else:
            # 子の探索が終わった後の砲門
            curr_count = [0]
            curr_pattern = [1]
            for u in links[v]:
                stc_u = st_count_fwd[u][-1] + 1
                new_pattern = factorials[curr_count[-1] + stc_u] * invs[curr_count[-1]] * invs[stc_u] % MOD
                curr_pattern.append(new_pattern * curr_pattern[-1] * st_pattern_fwd[u][-1] % MOD)
                curr_count.append(curr_count[-1] + stc_u)
            st_count_fwd[v] = curr_count
            st_pattern_fwd[v] = curr_pattern
            curr_count = [0]
            curr_pattern = [1]
            for u in reversed(links[v]):
                stc_u = st_count_fwd[u][-1] + 1
                new_pattern = factorials[curr_count[-1] + stc_u] * invs[curr_count[-1]] * invs[stc_u] % MOD
                curr_pattern.append(new_pattern * curr_pattern[-1] * st_pattern_fwd[u][-1] % MOD)
                curr_count.append(curr_count[-1] + stc_u)
            st_count_bwd[v] = curr_count[::-1]
            st_pattern_bwd[v] = curr_pattern[::-1]


def dfs2(links, st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd, ans):
    def sub(v, pc, pp):
        # print(v, pc, pp)
        if pc == 0:
            ans[v] = st_pattern_fwd[v][-1]
        else:
            cc = st_count_fwd[v][-1]
            cp = st_pattern_fwd[v][-1]
            pattern = factorials[cc + pc] * invs[cc] * invs[pc] % MOD
            pattern = pattern * cp * pp % MOD
            ans[v] = pattern

        for i, u in enumerate(links[v]):
            fc = st_count_fwd[v][i]
            fp = st_pattern_fwd[v][i]
            bc = st_count_bwd[v][i + 1]
            bp = st_pattern_bwd[v][i + 1]
            p1 = factorials[fc + bc] * invs[fc] * invs[bc] % MOD
            p1 = p1 * fp * bp % MOD
            p2 = factorials[fc + bc + pc] * invs[fc + bc] * invs[pc] % MOD
            p2 = p2 * p1 * pp % MOD
            # print(v, u, fc, fp, bc, bp, p1, p2)
            sub(u, fc + bc + pc + 1, p2)

    sub(0, 0, 1)


n, *ab = map(int, sys.stdin.buffer.read().split())
links = [set() for _ in range(n)]
for a, b in zip(ab[0::2], ab[1::2]):
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
MOD = 10 ** 9 + 7
factorials, invs = prepare(n, MOD)
st_count_fwd = [[] for _ in range(n)]
st_count_bwd = [[] for _ in range(n)]
st_pattern_fwd = [[] for _ in range(n)]
st_pattern_bwd = [[] for _ in range(n)]
ans = [0] * n

dfs0(links)
dfs1(links, st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd)
# print(st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd, sep='\n')
dfs2(links, st_count_fwd, st_count_bwd, st_pattern_fwd, st_pattern_bwd, ans)
print('\n'.join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
#%%
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math

#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率


def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

    
class modint:#add:和,mul:積,pow:累乗,div:商(modと互いに素であること)
    def __init__(self,x,mod=1000000007): 
        if isinstance(x, modint):x=x.x
        self.x, self.mod= x%mod, mod

    def __str__(self):
        return str(self.x)

    def __add__(self, a):
        if isinstance(a, modint):a=a.x
        return modint(self.x+a,self.mod)

    def __radd__(self, a):return self.__add__(a)

    def __iadd__(self, a):
        self.x=self.__add__(a)
        return self

    def __sub__(self, a):
        if isinstance(a, modint):a=a.x
        return self.__add__(-a)
    
    def __rsub__(self, a):return (a-self.x)%mod

    def __isub__(self, a):
        return self.__iadd__(-a)

    def __mul__(self, c):
        if isinstance(c, modint):c=c.x
        return modint(self.x*(c%self.mod),self.mod)
    
    def __rmul__(self, c):return self.__mul__(c)
    
    def __imul__(self, c):
        return self.__mul__(c)

    def __pow__(self,p):
        if isinstance(p, modint):p=p.x
        return modint(pow(self.x,p,self.mod),self.mod)
    
    def __ipow__(self,p):
        return self.__pow__(p)
        

    def __truediv__(self, d):
        if isinstance(d, modint):d=d.x
        u,v,a,b=1,0,d,self.mod
        while b:
            t=a//b
            a-=t*b
            a,b,u,v=b,a,v,u-t*v
        if a!=1: print("not 素")
        return modint(self.x*(u%self.mod),self.mod)

    def __itruediv__(self, d):
        self.x=self.__truediv__(d)
        return self

    def __eq__(self, target):
        if isinstance(target, modint):
            return self.x==target.x
        return self.x==target%self.mod
    
        
class comb:
    def __init__(self,N,mod=10**9+7):#コンビネーションnCrをmodで求める、Nは最大のn 
        self.mod=mod
        self.fact=[0]*(N+1)
        self.ifact=[0]*(N+1)
        fact,ifact=self.fact,self.ifact
        fact[0],fact[1],ifact[0],ifact[1]=1,1,1,1
        for i in range(2,N+1):
            x=(fact[i-1]*i)%mod
            fact[i]=x
            ifact[i]=self.extgcd1(x,mod)
        

    @lru_cache(maxsize = None)
    def extgcd1(self,a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b:
            t,a=divmod(a,b)
            a,b,u,v=b,a,v,u-t*v
        if a!=1: 
            print("not 素")
            return -1
        return u%b0

    #@lru_cache(maxsize = None)
    def comb(self,n,r): return (self.fact[n]*self.ifact[r]%self.mod)*self.ifact[n-r]%self.mod

    #@lru_cache(maxsize = None)
    def mulcomb(self,n,*rs):#n!/(r1!*r2!*r3!*...)
        ans=self.fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans

class rerooting:#全方位木
    def __init__(self,N,edge):#単位元self.unitとモノイドdef funcを設定すること,
        #dics[親][根（親の隣接点)]=その部分木での値
        self.unit=(modint(1),0)
        self.mod=10**9+7
        self.edge=edge
        self.cb=comb(N)
        self.fact=self.cb.fact
        self.ifact=self.cb.ifact
        self.par=[-1]*N
        self.N=N
        self.visited=[0]*N
        self.dics=[dict() for _ in range(N)]
        self.ikigake=[]
        self.tot=[self.unit]*N
    
    #@lru_cache(maxsize = None)
    def func(self,x,y):
        #ifact=self.ifact
        #mod=self.mod
        p1,s1=x
        p2,s2=y
        ans=modint(p1*p2)
        ssum=s1+s2
        ans*=self.cb.comb(ssum,s1)
        #ans*=(self.fact[ssum]*self.ifact[s1])%self.mod*self.ifact[s2]%self.mod
        #ans%=self.mod
        return ans,ssum 

    def addnode(self,x):#部分木に親のノードを結合する処理,dfsとforwardに出現
        return x[0],x[1]+1

    def _dfs(self,e,pa):
        edge=self.edge
        self.par[e]=pa
        self.ikigake.append(e)
        ans=self.unit
        for ne in edge[e]:
            if self.par[ne]!=-1:
                continue
            ans=self.func(ans,self.addnode(self._dfs(ne,e)))
            #print(ans)
        if pa!=e:
            self.dics[pa][e]=ans
        
        return ans
    
    def forward(self,start):
        self._dfs(start,start)
        #print(t2-t1)
        #count=0
        for e in self.ikigake:
            pa=self.par[e]
            de=self.dics[e]
            nes=tuple(de.keys())
            nvals=tuple(de.values())
            l=len(nes)
            aleft=[self.unit]
            aright=[self.unit]
            cleft=self.unit
            cright=self.unit
            for i in range(l-1):
                aleft.append(self.func(aleft[-1],self.addnode(nvals[i])))
                aright.append(self.func(aright[-1],self.addnode(nvals[-i-1])))
                #count+=4
            self.tot[e]=self.func(aright[-1],self.addnode(nvals[0]))
            for i,ne in enumerate(nes):
                if ne==pa:
                    continue
                self.dics[ne][e]=self.func(aleft[i],aright[-1-i])
                #count+=1
        #print(t3-t2)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    def tree_init(N):
        edgelist = [[] for _ in range(N)]
        elist=set()
        for a, b in [map(int, input().split()) for i in range(N-1)]:#木じゃない場合N-1をNに変える
            edgelist[a-1].append(b-1)#ノードの番号が0から始まる場合-1を消す
            edgelist[b-1].append(a-1)
            elist.add((a-1,b-1))
        return edgelist,elist

    edge,elist=tree_init(N)
    cb=comb(N)
    rt=rerooting(N,edge)
    rt.forward(0)

    for a in range(N):
        print(rt.tot[a][0])

if __name__ == "__main__":
    main()

#%%

Submission status: Time Limit Exceeded

Solution code:
#%%
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math

#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率


def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

    
class modint:#商をとるときはmodとdが互いに素であること
    def __init__(self,x,mod=1000000007): 
        self.x, self.mod= x%mod, mod

    def __str__(self):
        return str(self.x)

    def __add__(self, a):
        if isinstance(a, modint):a=a.x
        return (self.x+a)%self.mod

    def __radd__(self, a):return self.__add__(a)

    def __iadd__(self, a):
        self.x=self.__add__(a)
        return self

    def __sub__(self, a):
        if isinstance(a, modint):a=a.x
        return self.__add__(-a)
    
    def __rsub__(self, a):return (a-self.x)%self.mod

    def __isub__(self, a):
        return self.__iadd__(-a)

    def __mul__(self, c):
        if isinstance(c, modint):c=c.x
        return (self.x*(c%self.mod))%self.mod
    
    def __rmul__(self, c):return self.__mul__(c)
    
    def __imul__(self, c):
        self.x=self.__mul__(c)
        return self

    def __pow__(self,p):
        if isinstance(p, modint):p=p.x
        return pow(self.x,p,self.mod)
    
    def __ipow__(self,p):
        self.x=self.__pow__(p)
        return self

    def __truediv__(self, d):
        if isinstance(d, modint):d=d.x
        u,v,a,b=1,0,d,self.mod
        while b:
            t=a//b
            a-=t*b
            a,b,u,v=b,a,v,u-t*v
        if a!=1: print("not 素")
        return int((self.x*(u%self.mod))%self.mod)

    def __itruediv__(self, d):
        self.x=self.__truediv__(d)
        return self

    def __eq__(self, target):
        if isinstance(target, modint):
            return self.x==target.x
        return self.x==target%self.mod
 
        
class comb:
    def __init__(self,N,mod=10**9+7):#コンビネーションnCrをmodで求める、Nは最大のn 
        self.mod=mod
        self.fact=[0]*(N+1)
        self.ifact=[0]*(N+1)
        fact,ifact=self.fact,self.ifact
        fact[0],fact[1],ifact[0],ifact[1]=1,1,1,1
        for i in range(2,N+1):
            x=(fact[i-1]*i)%mod
            fact[i]=x
            ifact[i]=self.extgcd1(x,mod)
        

    @lru_cache(maxsize = None)
    def extgcd1(self,a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b:
            t,a=divmod(a,b)
            a,b,u,v=b,a,v,u-t*v
        if a!=1: 
            print("not 素")
            return -1
        return u%b0

    #@lru_cache(maxsize = None)
    def comb(self,n,r): return (self.fact[n]*self.ifact[r]%self.mod)*self.ifact[n-r]%self.mod

    @lru_cache(maxsize = None)
    def mulcomb(self,n,*rs):#n!/(r1!*r2!*r3!*...)
        ans=self.fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans

class rerooting:#全方位木
    def __init__(self,N,edge):#単位元self.unitとモノイドdef funcを設定すること,
        #dics[親][根（親の隣接点)]=その部分木での値
        self.unit=(modint(1),0)
        self.mod=10**9+7
        self.edge=edge
        self.cb=comb(N)
        self.fact=self.cb.fact
        self.ifact=self.cb.ifact
        self.par=[-1]*N
        self.N=N
        self.visited=[0]*N
        self.dics=[dict() for _ in range(N)]
        self.ikigake=[]
        self.tot=[self.unit]*N
    
    #@lru_cache(maxsize = None)
    def func(self,x,y):
        #ifact=self.ifact
        #mod=self.mod
        p1,s1=x
        p2,s2=y
        ans=modint(p1*p2)
        ssum=s1+s2
        ans*=self.cb.comb(ssum,s1)
        #ans*=(self.fact[ssum]*self.ifact[s1])%self.mod*self.ifact[s2]%self.mod
        #ans%=self.mod
        return ans,ssum 

    def addnode(self,x):#部分木に親のノードを結合する処理,dfsとforwardに出現
        return x[0],x[1]+1

    def _dfs(self,e,pa):
        edge=self.edge
        self.par[e]=pa
        self.ikigake.append(e)
        ans=self.unit
        for ne in edge[e]:
            if self.par[ne]!=-1:
                continue
            ans=self.func(ans,self.addnode(self._dfs(ne,e)))
            #print(ans)
        if pa!=e:
            self.dics[pa][e]=ans
        
        return ans
    
    def forward(self,start):
        self._dfs(start,start)
        #print(t2-t1)
        #count=0
        for e in self.ikigake:
            pa=self.par[e]
            de=self.dics[e]
            nes=tuple(de.keys())
            nvals=tuple(de.values())
            l=len(nes)
            aleft=[self.unit]
            aright=[self.unit]
            cleft=self.unit
            cright=self.unit
            for i in range(l-1):
                aleft.append(self.func(aleft[-1],self.addnode(nvals[i])))
                aright.append(self.func(aright[-1],self.addnode(nvals[-i-1])))
                #count+=4
            self.tot[e]=self.func(aright[-1],self.addnode(nvals[0]))
            for i,ne in enumerate(nes):
                if ne==pa:
                    continue
                self.dics[ne][e]=self.func(aleft[i],aright[-1-i])
                #count+=1
        #print(t3-t2)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    def tree_init(N):
        edgelist = [[] for _ in range(N)]
        elist=set()
        for a, b in [map(int, input().split()) for i in range(N-1)]:#木じゃない場合N-1をNに変える
            edgelist[a-1].append(b-1)#ノードの番号が0から始まる場合-1を消す
            edgelist[b-1].append(a-1)
            elist.add((a-1,b-1))
        return edgelist,elist

    edge,elist=tree_init(N)
    cb=comb(N)
    rt=rerooting(N,edge)
    rt.forward(0)

    for a in range(N):
        print(rt.tot[a][0])

if __name__ == "__main__":
    main()

#%%

Submission status: Time Limit Exceeded

Solution code:
#%%
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math

#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率


def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

        
class comb:
    def __init__(self,N,mod=10**9+7):#コンビネーションnCrをmodで求める、Nは最大のn 
        self.mod=mod
        self.fact=[0]*(N+1)
        self.ifact=[0]*(N+1)
        fact,ifact=self.fact,self.ifact
        fact[0],fact[1],ifact[0],ifact[1]=1,1,1,1
        for i in range(2,N+1):
            x=(fact[i-1]*i)%mod
            fact[i]=x
            ifact[i]=self.extgcd1(x,mod)
        

    @lru_cache(maxsize = None)
    def extgcd1(self,a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b:
            t,a=divmod(a,b)
            a,b,u,v=b,a,v,u-t*v
        if a!=1: 
            print("not 素")
            return -1
        return u%b0

    @lru_cache(maxsize = None)
    def comb(self,n,r): return (self.fact[n]*self.ifact[r]%self.mod)*self.ifact[n-r]%self.mod

    @lru_cache(maxsize = None)
    def mulcomb(self,n,*rs):#n!/(r1!*r2!*r3!*...)
        ans=self.fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans

class rerooting:#全方位木
    def __init__(self,N,edge):#単位元self.unitとモノイドdef funcを設定すること,
        #dics[親][根（親の隣接点)]=その部分木での値
        self.unit=(1,0)
        self.mod=10**9+7
        self.edge=edge
        self.cb=comb(N)
        self.fact=self.cb.fact
        self.ifact=self.cb.ifact
        self.par=[-1]*N
        self.N=N
        self.visited=[0]*N
        self.dics=[dict() for _ in range(N)]
        self.ikigake=[]
        self.tot=[self.unit]*N
    
    #@lru_cache(maxsize = None)
    def func(self,x,y):
        #ifact=self.ifact
        #mod=self.mod
        p1,s1=x
        p2,s2=y
        ans=(p1*p2)%self.mod
        ssum=s1+s2
        ans*=self.cb.comb(ssum,s1)
        #ans*=(self.fact[ssum]*self.ifact[s1])%self.mod*self.ifact[s2]%self.mod
        ans%=self.mod
        return ans,ssum 

    def addnode(self,x):#部分木に親のノードを結合する処理,dfsとforwardに出現
        return x[0],x[1]+1

    def _dfs(self,e,pa):
        edge=self.edge
        self.par[e]=pa
        self.ikigake.append(e)
        ans=self.unit
        for ne in edge[e]:
            if self.par[ne]!=-1:
                continue
            ans=self.func(ans,self.addnode(self._dfs(ne,e)))
            #print(ans)
        if pa!=e:
            self.dics[pa][e]=ans
        
        return ans
    
    def forward(self,start):
        self._dfs(start,start)
        #print(t2-t1)
        #count=0
        for e in self.ikigake:
            pa=self.par[e]
            de=self.dics[e]
            nes=tuple(de.keys())
            nvals=tuple(de.values())
            l=len(nes)
            aleft=[self.unit]
            aright=[self.unit]
            cleft=self.unit
            cright=self.unit
            for i in range(l-1):
                aleft.append(self.func(aleft[-1],self.addnode(nvals[i])))
                aright.append(self.func(aright[-1],self.addnode(nvals[-i-1])))
                #count+=4
            self.tot[e]=self.func(aright[-1],self.addnode(nvals[0]))
            for i,ne in enumerate(nes):
                if ne==pa:
                    continue
                self.dics[ne][e]=self.func(aleft[i],aright[-1-i])
                #count+=1
        #print(t3-t2)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    def tree_init(N):
        edgelist = [[] for _ in range(N)]
        elist=set()
        for a, b in [map(int, input().split()) for i in range(N-1)]:#木じゃない場合N-1をNに変える
            edgelist[a-1].append(b-1)#ノードの番号が0から始まる場合-1を消す
            edgelist[b-1].append(a-1)
            elist.add((a-1,b-1))
        return edgelist,elist

    edge,elist=tree_init(N)
    cb=comb(N)
    rt=rerooting(N,edge)
    rt.forward(0)

    for a in range(N):
        print(rt.tot[a][0])

if __name__ == "__main__":
    main()

#%%