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: Wrong Answer

Solution code:
# ここまでやった

from collections import deque
from functools import reduce

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

def bfs(s):
    seen = [0]*N
    d = [0]*N
    prev = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while todo:
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          d[b] += d[a] + 1
          prev[b] = a
    return d,prev
  
def argsort(arr, reverse=False, shift=20):
    tmp = sorted([arr[i]<<shift | i for i in range(len(arr))],reverse=reverse)
    mask = (1<<shift) - 1
    return [tmp[i] & mask for i in range(len(arr))]

prod = lambda arr: reduce(lambda a,b:a*b%mod,arr)
  
d,prev = bfs(0)
order = argsort(d,reverse=True)
dp1 = [0]*N
dp2 = [0]*N

prodlist = [0]*N
for v in order:
  if v != 0 and len(G[v])==1:
    dp1[v] = 1
    dp2[v] = 1
  elif v != 0 and len(G[v])==2:
    dp1[v] = [dp1[i] for i in G[v] if i != prev[v]][0] + 1
    dp2[v] = [dp2[i] for i in G[v] if i != prev[v]][0]
  else:
    dp1[v] = sum([dp1[i] for i in G[v] if i != prev[v]])+1
    tmp1 = factorial[dp1[v]-1]
    tmp2 = prod([factorial[dp1[i]] for i in G[v] if i != prev[v]])
    tmp3 = prod([dp2[i] for i in G[v] if i != prev[v]])
    dp2[v] = tmp1 * pow(tmp2,-1,mod) * tmp3 % mod
    prodlist[v] = tmp3
    
ans = [0]*N
ans[0] = dp2[0]

def bfs2(s):
    seen = [0]*N
    todo = deque()
    seen[s]=1
    todo.append(s)
    while todo:
      a = todo.popleft()
      for b in G[a]:
        if seen[b] == 0:
          seen[b] = 1
          todo.append(b)
          if len(G[a]) > 1:
            size = sum([dp1[i] for i in G[a] if i != b])+1
            tmp1 = factorial[size-1]
            tmp2 = prod([factorial[dp1[i]] for i in G[a] if i != b])
            tmp3 = prodlist[a] * pow(dp2[b],-1,mod)
            prevdp = tmp1 * pow(tmp2,-1,mod) * tmp3 % mod
          else:
            size,prevdp = 0,1
          tmp1 = factorial[N-1]
          tmp2 = prod([factorial[dp1[i]] for i in G[b] if i != prev[b]]+[factorial[size]])
          tmp3 = prod([dp2[i] for i in G[b] if i != prev[b]]+[prevdp])
          ans[b] = tmp1 * pow(tmp2,-1,mod) * tmp3 % mod
          prodlist[b] = tmp3
    return
  
bfs2(0)
print(ans)

Submission status: Wrong Answer

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
                print(dpy,y,x)
                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)
print(dp)
ans = [0]*(N+1)
ans[1] = dp[1]
dfs_ans(1)
for i in ans[1:]:
    print(i)

Submission status: Wrong Answer

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 h(c):
    res=1
    for d in G[c]:
        if d==par[c]:
            continue
        par[d]=c
        res=res*h(d)*comb(cnt[c]-1,cnt[d])%mod
        cnt[c]-=cnt[d]
    D[c]=res
    return res

h(0)
ans=[0]*n
ans[0]=D[0]
q=[0]
while q:
    e=q.pop()
    r=1
    for j in G[e]:
        if ans[j]:
            continue
        inv_e=pow(comb(n-1,cnt[j]),mod-2,mod)
        ans[j]=D[j]*ans[e]*inv_e*comb(n-1,cnt[j]-1)%mod

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

Submission status: Wrong Answer

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


class ReRooting:
    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 = ReRooting(N, e1, merge1, f1, g1)
    tree_size = tree1.build()

    merge2 = lambda x,y:(x*y)%MOD
    f2 = lambda x, par, s:(x*rev[tree_size[par][s]])%MOD
    g2 = lambda x, par, s:(x*fac[tree_size[par][s]-1])%MOD
    e2 = 1
    tree2 = ReRooting(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)

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


if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

MOD = 10 ** 9 + 7
table_len = 2 * 10 ** 5 + 10

fac = [1, 1]
for i in range(2, table_len):
    fac.append(fac[-1] * i % MOD)
    
finv = [0] * table_len
finv[-1] = pow(fac[-1], MOD - 2, MOD)
for i in range(table_len-1, -1, -1):
    finv[i-1] = finv[i] * i % MOD


N = int(input())

adj = [[] for _ in range(N+1)]

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


dfs_order = []
parent = [0] * (N+1)
root = 1
stack = [root]
while stack:
    node = stack.pop()
    dfs_order.append(node)
    for child in adj[node]:
        if child != parent[node]:
            parent[child] = node
            stack.append(child)

def func(t1, t2):
    size1, value1 = t1
    size2, value2 = t2
    size = size1 + size2
    comb = fac[size] * finv[size1] * finv[size2] % MOD
    value = comb * value1 * value2 % MOD
    return (size, value)
       
dp1 = [(0, 1)] * (N+1)
for node in reversed(dfs_order):
    for child in adj[node]:
        if child != parent[node]:
            dp1[node] = func(dp1[node], dp1[child])
    dp1[node] = (dp1[node][0] + 1, dp1[node][1])
print(dp1)
dp2 = [(0, 1)] * (N+1)
for node in dfs_order:
    around = [dp1[next_node] if next_node != parent[node] else dp2[node] for next_node in adj[node]]
    from_left = [(0, 1)] + list(accumulate(around, func))[:-1]
    from_right = list(accumulate(reversed(around), func))[-2::-1] + [(0, 1)]
    without = [func(l, r) for l, r in zip(from_left, from_right)]
    for next_node, t in zip(adj[node], without):
        if next_node != parent[node]:
            dp2[next_node] = (t[0] + 1, t[1])
print(dp2)
for t1, t2 in zip(dp1[1:], dp2[1:]):
    print(func((t1[0] - 1, t1[1]), t2)[1])

Submission status: Wrong Answer

Solution code:
#%%
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from collections import deque 
#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)%self.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 _dfs(self,start):
        edge=self.edge
        N=self.N
        par=self.par
        q=deque([(start,start)])
        while len(q):
            e,pa=q.pop()#ここをpopleftにすると幅優先探索BFSになる
            if par[e]!=-1:continue
            par[e]=pa
            self.ikigake.append(e)
            for ne in edge[e]:q.append((ne,e))
        
        for e in reversed(self.ikigake[1:]):
            pa=par[e]
            ans=self.unit
            de=self.dics[e]
            for val in de.values():
                ans=self.func(ans,val)
            self.dics[pa][e]=self.addnode(ans)

    def forward(self,start):
        self._dfs(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],nvals[i]))
                aright.append(self.func(aright[-1],nvals[-i-1]))
                #count+=4
            #print(e,l,self.dics)
            self.tot[e]=self.func(aright[-1],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: Wrong Answer

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
        cb=comb(N)
        self.fact=cb.fact
        self.ifact=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
    
    def func(self,x,y):
        ans=1
        p1,s1=x
        p2,s2=y
        ans*=p1
        ans*=p2
        ans%=self.mod
        ssum=s1+s2
        #print(x,y,slist)
        ans*=self.fact[ssum]*self.ifact[s1]%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: Wrong Answer

Solution code:
# 全方位木DP
# トポロジカルソート→木DP→全方位
from collections import deque
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())

# modの会場が必要なのでライブラリから
mod = 10 ** 9 + 7
N = n + 5
bikkuri = [0 for i in range(N)]
bikkuri[0] = 1
gyaku = [0 for i in range(N)]
gyaku[0] = 1
for i in range(1, N):
    bikkuri[i] = (i * bikkuri[i - 1]) % mod
    gyaku[i] = pow(bikkuri[i], mod - 2, mod)

graph = [[] for _ in range(n + 1)]
m = map(int, read().split())
AB = zip(m, m)
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

# topological sort
par = [-1] * (n + 1)
que = deque([])
que.append(1)
topo = []
while que:
    v = que.popleft()
    topo.append(v)
    for u in graph[v]:
        if u == par[v]:
            continue
        par[u] = v
        graph[u].remove(v)
        que.append(u)

# これでparのリストとtopological_sortと子供方向のみグラフを得る
# 木DP
dp1 = [0] * (n + 1)
size = [0] * (n + 1)
edge_index = [{} for _ in range(n + 1)]
dpl = [[] for _ in range(n + 1)]
dpr = [[] for _ in range(n + 1)]
for v in topo[::-1]:
    dp1[v] = 1
    size[v] = 1
    # サイズを先に計算
    for u in graph[v]:
        size[v] += size[u]
        dp1[v] *= dp1[u]
        dp1[v] *= gyaku[size[u]]
    # 次に組み合わせを考える
    # 左から
    temp = 1
    for i in range(len(graph[v])):
        u = graph[v][i]
        edge_index[v][u] = i
        temp *= dp1[u]
        temp %= mod
        temp *= gyaku[size[u]]
        temp %= mod
        dpl[v].append(temp)
    # 右から
    temp = 1
    for i in range(len(graph[v]))[::-1]:
        u = graph[v][i]
        temp *= dp1[u]
        temp *= gyaku[size[u]]
        temp %= mod
        dpr[v].append(temp)
    dp1[v] *= bikkuri[size[v] - 1]
    dp1[v] %= mod

# 全方位
ans = [0] * (n + 1)
dp2 = [0] * (n + 1)

for v in topo:
    # 根の時
    if par[v] == -1:
        dp2[v] = 1
        ans[v] = dp1[v]
    else:
        # 上側の処理
        dp2[v] = 1
        p = par[v]
        # 上からみたv以外の累積積を取りたい。
        # graph[p]において、vは何番目かを考える。
        v_idx = edge_index[p][v]
        dp2[v] *= dp2[p] * gyaku[n - size[p]]
        dp2[v] *= bikkuri[n - size[v] - 1]
        dp2[v] %= mod
        # 左からv_idx個, idxはv_idx-1まで
        if dpl[p]:
            if v_idx - 1 >= 0:
                dp2[v] *= dpl[p][v_idx - 1]
                dp2[v] %= mod
            # 右からlen(grap[v])-(v_idx+1)個→idxはlen(graph[v])-v_idx-2
            if v_idx < len(graph[p]) - 1:
                dp2[v] *= dpr[p][len(graph[p]) - 2 - v_idx]
                dp2[v] %= mod
    # 上側と下側の合体
    ans[v] = bikkuri[n - 1]
    if dpl[v]:
        ans[v] *= dpl[v][-1]
    ans[v] *= dp2[v] * gyaku[n - size[v]]
    ans[v] %= mod

print(*ans[1::], sep="/n")

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n-1)]
mod=pow(10,9)+7
ki=[[] for _ in range(n)]
todo=[]
for a,b in ab:
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
import sys
sys.setrecursionlimit(100000)
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
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 )
memo={}

def dfs(i,j):#i->jの矢印に対応する部分木の値を返す。サイズ、パターン数
  if (i,j) in memo:
    return memo[(i,j)]
  l=ki[j]
  ret=0
  sizes=[]
  pats=[]
  sum_size=0
  ret=1
  for li in l:
    if li==i:
      continue
    size,pat=dfs(j,li)
    sizes.append(size)
    sum_size+=size
    ret*=cmb(sum_size,size,mod)
    ret*=pat
  memo[(i,j)]=(sum_size+1,ret)
  return (sum_size+1,ret)
dfs(-1,0)
#print(memo.keys())
# memo[(i,j)]:#i->jの部分木
def bfs(i,j): # i->jの矢印に対応する部分木を計算する
    if (-1,j) in memo: 
        # (-1,j)が定まっているなら、jから出ていく矢印に対応する部分木はすべて定まっている。
        # 従ってmemo[(j,i)]が定まっている
        ret=memo[(-1,j)][0]
        ret*=pow(memo[(j,i)][1],mod-2,mod)
        ret%=mod
        ret*=pow(cmb(n,memo[(j,i)][0],mod),mod-2,mod)
        ret%=mod
        memo[(i,j)]=(n-memo[(j,i)][0],ret)
        if (-1,i) not in memo:
            memo[(-1,i)]=dfs(-1,i)
    else:
        # 適切な順番で呼び出すことにより、(-1,j)が定まっていなくても、
        # jから出ていく矢印に対応する部分木はすべて定まっている状態にできる。
        l=ki[j]
        pat=1
        size=0
        for li in l:
            pat*=memo[(j,li)][1]
            size_=memo[(j,li)][0]
            size+=size_
            pat*=cmb(size,size_,mod)
            pat%=mod
        memo[(j,-1)]=(n,pat)
        bfs(i,j)
from collections import deque
todo=deque([0])
seen=[0]*n
seen[0]=1
while todo:
    i=todo.popleft()
    l=ki[i]
    for li in l:
        if seen[li]==0:
            bfs(li,i)
            todo.append(li)
            seen[li]=1
#print(memo.keys())
for i in range(n):
    print(memo[(-1,i)][1]%mod)

Submission status: Wrong Answer

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n-1)]
mod=pow(10,9)+7
ki=[[] for _ in range(n)]
todo=[]
for a,b in ab:
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
import sys
sys.setrecursionlimit(100000)
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
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 )
memo={}

def dfs(i,j):#i->jの矢印に対応する部分木の値を返す。サイズ、パターン数
  if (i,j) in memo:
    return memo[(i,j)]
  l=ki[j]
  ret=0
  sizes=[]
  pats=[]
  sum_size=0
  ret=1
  for li in l:
    if li==i:
      continue
    size,pat=dfs(j,li)
    sizes.append(size)
    sum_size+=size
    ret*=cmb(sum_size,size,mod)
    ret*=pat
  memo[(i,j)]=(sum_size+1,ret)
  return (sum_size+1,ret)
dfs(-1,0)
print(memo.keys())
# memo[(i,j)]:#i->jの部分木
def bfs(i,j): # i->jの矢印に対応する部分木を計算する
    if (-1,j) in memo: 
        # (-1,j)が定まっているなら、jから出ていく矢印に対応する部分木はすべて定まっている。
        # 従ってmemo[(j,i)]が定まっている
        ret=memo[(-1,j)][0]
        ret*=pow(memo[(j,i)][1],mod-2,mod)
        ret%=mod
        ret*=pow(cmb(n,memo[(j,i)][0],mod),mod-2,mod)
        ret%=mod
        memo[(i,j)]=(n-memo[(j,i)][0],ret)
        if (-1,i) not in memo:
            memo[(-1,i)]=dfs(-1,i)
    else:
        # 適切な順番で呼び出すことにより、(-1,j)が定まっていなくても、
        # jから出ていく矢印に対応する部分木はすべて定まっている状態にできる。
        l=ki[j]
        pat=1
        size=0
        for li in l:
            pat*=memo[(j,li)][1]
            size_=memo[(j,li)][0]
            size+=size_
            pat*=cmb(size,size_,mod)
            pat%=mod
        memo[(j,-1)]=(n,pat)
        bfs(i,j)
from collections import deque
todo=deque([0])
seen=[0]*n
seen[0]=1
while todo:
    i=todo.popleft()
    l=ki[i]
    for li in l:
        if seen[li]==0:
            bfs(li,i)
            todo.append(li)
            seen[li]=1
print(memo.keys())
for i in range(n):
    print(memo[(-1,i)][1]%mod)