Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices numbered 1 to N. The i-th edge in this tree connects Vertex a_i and b_i.
For each k=1, ..., N, solve the problem below:

Consider writing a number on each vertex in the tree in the following manner:

First, write 1 on Vertex k.

Then, for each of the numbers 2, ..., N in this order, write the number on the vertex chosen as follows:

Choose a vertex that still does not have a number written on it and is adjacent to a vertex with a number already written on it. If there are multiple such vertices, choose one of them at random.

Find the number of ways in which we can write the numbers on the vertices, modulo (10^9+7).

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq a_i,b_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

For each k=1, 2, ..., N in this order, print a line containing the answer to the problem.

Sample Input 1

3
1 2
1 3

Sample Output 1

2
1
1

The graph in this input is as follows:

For k=1, there are two ways in which we can write the numbers on the vertices, as follows:

Writing 1, 2, 3 on Vertex 1, 2, 3, respectively

Writing 1, 3, 2 on Vertex 1, 2, 3, respectively

Sample Input 2

2
1 2

Sample Output 2

1
1

The graph in this input is as follows:

Sample Input 3

5
1 2
2 3
3 4
3 5

Sample Output 3

2
8
12
3
3

The graph in this input is as follows:

Sample Input 4

8
1 2
2 3
3 4
3 5
3 6
6 7
6 8

Sample Output 4

40
280
840
120
120
504
72
72

The graph in this input is as follows:



Sample input:
3
1 2
1 3


Sample output:
2
1
1

Submission status: Time Limit Exceeded

Solution code:
import sys

class nCrMod():
    def __init__(self, mod, n):
        self.mod = mod
        self.fac = [1, 1] + [0] * n
        self.finv = [1, 1] + [0] * n
        self.inv = [0, 1] + [0] * n
        f, fi = self.fac[1], self.finv[1]
        for i in range(2, n + 1):
            fn = f * i % mod
            v = -self.inv[mod % i] * (mod // i) % mod
            fin = fi * v % mod
            f, fi = fn, fin
            self.fac[i] = f
            self.finv[i] = fi
            self.inv[i] = v

    def __call__(self, n, r):
        return self.fac[n] * self.finv[r] * self.finv[n - r] % self.mod


def main():
    N = int(input())
    E = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a - 1].append(b - 1)
        E[b - 1].append(a - 1)
    mod = 10 ** 9 + 7
    nCr = nCrMod(mod, N)
    T = [{} for _ in range(N)]

    def h(n, f):
        if f in T[n]:
            return T[n][f]
        r = 1
        cc = 0
        for i in E[n]:
            if i == f:
                continue
            p, c = h(i, n)
            cc += c
            r = r * p * nCr(cc, c) % mod
        T[n][f] = (r, cc + 1)
        return (r, cc + 1)

    print('\n'.join(str(h(i, -1)[0]) for i in range(N)))

sys.setrecursionlimit(10 ** 6)
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)
class fact():
    def __init__(self, i, mod):
        self.l = [1] * (i+1)
        for i in range(1, i+1):
            self.l[i] = self.l[i-1] * i
        self.mod = mod
        self.g1 = [1, 1]
        self.g2 = [1, 1]
        inverse = [0, 1]
        for i in range(2, 2 * (10 ** 5) + 1):
            self.g1.append((self.g1[-1] * i) % mod)
            inverse.append((-inverse[mod % i] * (mod // i)) % mod)
            self.g2.append((self.g2[-1] * inverse[-1]) % mod)


def main():
    N = int(input())
    d = {}
    mod = 10**9 + 7
    f = fact(N, mod)
    for i in range(N-1):
        a, b = map(int, input().split())
        if a in d:
            d[a].append(b)
        else:
            d[a] = [b]
        if b in d:
            d[b].append(a)
        else:
            d[b] = [a]
    for i in range(1, N+1):
        v = set()
        r, t = solve(i, N, v, f, d)
        print(r % mod)
def solve(n, a, v, f, d):
    v.add(n)
    x = 0
    unv = []
    for i in d[n]:
        if i not in v:
            x += 1
            unv.append(i)
    if x == 1:
        r, t = solve(unv[0], a-1, v, f, d)
        return r, t + 1
    if x == 0:
        return 1, 1
    t = 1
    r = 1
    for i in unv:
        rr, tt = solve(i, a-1, v, f, d)
        t += tt
        r *= rr
        r *= f.g2[tt]
    r *= f.l[t-1]
    return r, t
main()

Submission status: Time Limit Exceeded

Solution code:
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).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

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

while Q:
    x=Q.pop()

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

FROM1=[-1]*(N+1)
FROM2=[-1]*(N+1)

for x in SORTED[::-1]:
    if len(E[x])==1 and x!=1:
        FROM1[x]=1
        FROM2[x]=1
    else:
        L=[]
        SUML=0
        A=1
        for to in E[x]:
            if to==P[x]:
                continue
            L.append(FROM1[to])
            SUML+=FROM1[to]
            A=A*FROM2[to]%mod
        #print(x,L)
        FROM1[x]=SUML+1
        S=SUML

        for l in L:
            A=A*Combi(S,l)%mod
            S-=l
        FROM2[x]=A

TO1=[-1]*(N+1)
TO2=[-1]*(N+1)
TO2[1]=1

for x in SORTED:
    if x!=1 and len(E[x])==1:
        continue
    
    SS=1
    L=[]
    SUML=0
    for to in E[x]:
        if to==P[x]:
            continue
        
        SS=SS*FROM2[to]%mod
        L.append(FROM1[to])
        SUML+=FROM1[to]

    L.append(N-1-SUML)
    SUML+=N-1-SUML

    for to in E[x]:
        if to==P[x]:
            continue
        
        A=SS*pow(FROM2[to],mod-2,mod)*TO2[x]%mod
        S=SUML-FROM1[to]
        flag=0

        #print(x,L)
        for l in L:
            if flag==0 and l==FROM1[to]:
                flag=1
                continue
            A=A*Combi(S,l)%mod
            S-=l
        TO2[to]=A

for i in range(1,N+1):
    ANS=TO2[i]

    L=[]
    SUML=0

    for to in E[i]:
        if to==P[i]:
            continue
        ANS=ANS*FROM2[to]%mod
        L.append(FROM1[to])
        SUML+=FROM1[to]

    L.append(N-1-sum(L))
    SUML+=N-1-SUML
    S=SUML
    for l in L:
        ANS=ANS*Combi(S,l)%mod
        S-=l
    print(ANS)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate,chain
from sys import setrecursionlimit
from sys import stdin

setrecursionlimit(10000000)

MOD = 10**9+7


# mを法とするときのa^n
def modpow(a,n,m):
    res = 1
    t = a
    while n:
        if n%2:
            res = (res*t)%m
        t = (t*t)%m
        n //= 2
    return res

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


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

    patterns = dict()
    childrens = dict()
    def rec(a,b):
        if (a,b) in patterns:
            return patterns[(a,b)], childrens[(a,b)]

        prod = 1 # product of patterns
        d = 1 # denominator of multinomial coefficient
        n = 0 # total childrens
        for c in adj[b]:
            if a == c:
                continue
            p,c = rec(b,c)
            prod *= p
            prod %= MOD
            d *= factorio[c]
            d %= MOD
            n += c

        patterns[(a,b)] = (prod*factorio[n]*modpow(d,MOD-2, MOD))%MOD
        childrens[(a,b)] = n+1
        return patterns[(a,b)], childrens[(a,b)]

    for a,b in edges:
        rec(a,b)
        rec(b,a)

    for k in range(N):
        p,c = rec(-1,k)
        print(p)


if __name__ == '__main__':
    it = iter(stdin)
    N = int(next(it))
    adj = [list() for _ in range(N)]
    edges = []
    for _ in range(N-1):
        a,b = map(int,next(it).split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
        edges.append((a-1,b-1))

    solve(N,adj,edges)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
MOD = 10 ** 9 + 7

N = int(input())
factorial = [1]
fact_invs = [1]
for i in range(1, N+1):
    factorial.append((factorial[-1]*i) % MOD)
    fact_invs.append(pow(factorial[-1], MOD-2, MOD))

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

memo_num = [[None] * (N+1) for _ in range(N+1)]
memo_ptn = [[None] * (N+1) for _ in range(N+1)]
for k in range(1, N+1):
    visited = [False] * (N+1)
    stk = [(0, k)]
    i = 0
    while stk:
        parent, node = stk[i]
        if not visited[node]:
            visited[node] = True
            for child in edge[node].keys():
                if not visited[child] and memo_num[node][child] is None:
                    stk.append((node, child))
                    i += 1
        else:
            num = 1
            ptn = 1
            for child in edge[node].keys():
                if child != parent:
                    n = memo_num[node][child]
                    num += n
                    ptn *= fact_invs[n]
                    ptn %= MOD
                    p = memo_ptn[node][child]
                    ptn *= p
                    ptn %= MOD
            ptn *= factorial[num-1]
            ptn %= MOD
            memo_num[parent][node] = num
            memo_ptn[parent][node] = ptn
            i -= 1
            stk.pop()
    print(memo_ptn[0][k])

Submission status: Time Limit Exceeded

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

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

while Q:
    x=Q.pop()

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

FROM1=[-1]*(N+1)
FROM2=[-1]*(N+1)

for x in SORTED[::-1]:
    if len(E[x])==1 and x!=1:
        FROM1[x]=1
        FROM2[x]=1
    else:
        L=[]
        SUML=0
        A=1
        for to in E[x]:
            if to==P[x]:
                continue
            L.append(FROM1[to])
            SUML+=FROM1[to]
            A=A*FROM2[to]%mod
        #print(x,L)
        FROM1[x]=SUML+1
        S=SUML

        for l in L:
            A=A*Combi(S,l)%mod
            S-=l
        FROM2[x]=A

TO1=[-1]*(N+1)
TO2=[-1]*(N+1)
TO2[1]=1

for x in SORTED:
    if x!=1 and len(E[x])==1:
        continue
    
    SS=1
    L=[]
    SUML=0
    for to in E[x]:
        if to==P[x]:
            continue
        
        SS=SS*FROM2[to]%mod
        L.append(FROM1[to])
        SUML+=FROM1[to]

    L.append(N-1-SUML)
    SUML+=N-1-SUML

    for to in E[x]:
        if to==P[x]:
            continue
        
        A=SS*pow(FROM2[to],mod-2,mod)*TO2[x]%mod
        S=SUML-FROM1[to]
        flag=0

        #print(x,L)
        for l in L:
            if flag==0 and l==FROM1[to]:
                flag=1
                continue
            A=A*Combi(S,l)%mod
            S-=l
        TO2[to]=A

for i in range(1,N+1):
    ANS=TO2[i]

    L=[]
    SUML=0

    for to in E[i]:
        if to==P[i]:
            continue
        ANS=ANS*FROM2[to]%mod
        L.append(FROM1[to])
        SUML+=FROM1[to]

    L.append(N-1-sum(L))
    SUML+=N-1-SUML
    S=SUML
    for l in L:
        ANS=ANS*Combi(S,l)%mod
        S-=l
    print(ANS)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5+10)

n = int(input())
edge = [tuple(map(int, input().split())) for _ in range(n-1)]

mod = 10 ** 9 + 7
def extGCD(a, b):
    if b == 0:
        return a, 1, 0
    g, y, x = extGCD(b, a%b)
    y -= a//b * x
    return g, x, y

def moddiv(a, b):
    _, inv, _ = extGCD(b, mod)
    return (a * inv) % mod

N = 2 * 10 ** 5 + 10
fact = [0] * (N)
fact[0] = 1
for i in range(1, N):
    fact[i] = (fact[i-1] * i) % mod

def comb(a, b):
    return moddiv(moddiv(fact[a], fact[a-b]), fact[b])

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

d = {}
def dfs(v, p):
    if (v, p) in d:
        return d[(v, p)]
    num, count = 0, 1
    for next in connect[v]:
        if next != p:
            i, c = dfs(next, v)
            num += i
            count *= c * comb(num, i)
            count %= mod
    num += 1
    d[(v, p)] = num, count
    return num, count

for a, b in edge:
    dfs(a-1, b-1)
    dfs(a-1, b-1)
for i in range(n):
    print(dfs(i, -1)[1])

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
ab = [list(map(int, input().split())) for _ in range(n - 1)]

import sys
sys.setrecursionlimit(10 ** 6)


from collections import defaultdict
graph = defaultdict(list)
for i in range(n - 1):
    graph[ab[i][0] - 1].append(ab[i][1] - 1)
    graph[ab[i][1] - 1].append(ab[i][0] - 1)

def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

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

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

mod = 10 ** 9 + 7


childs = [-1] * n

def dfs(cur, prev):
    ret = 1
    for target in graph[cur]:
        if target != prev:
            ret += dfs(target, cur)
    childs[cur] = ret
    return ret

_ = dfs(0, -1)


tmpans = 1
for i in range(1, n+1):
    tmpans = tmpans * i % mod
for child in childs:
    tmpans = div(tmpans, child)

ans = [0] * n
ans[0] = tmpans

def dfs2(cur, prev):
    if cur != 0:
        # change cur <--> prev
        ans[cur] = div(ans[prev] * childs[cur] , n - childs[cur])

    for target in graph[cur]:
        if target != prev:
            dfs2(target, cur)

dfs2(0, -1)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate,chain
from sys import setrecursionlimit

setrecursionlimit(10000000)

MOD = 10**9+7


# mを法とするときのa^n
def modpow(a,n,m):
    res = 1
    t = a
    while n:
        if n%2:
            res = (res*t)%m
        t = (t*t)%m
        n //= 2
    return res

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


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

    patterns = dict()
    childrens = dict()
    def rec(a,b):
        if (a,b) in patterns:
            return patterns[(a,b)], childrens[(a,b)]

        prod = 1 # product of patterns
        d = 1 # denominator of multinomial coefficient
        n = 0 # total childrens
        for c in adj[b]:
            if a == c:
                continue
            p,c = rec(b,c)
            prod *= p
            prod %= MOD
            d *= factorio[c]
            d %= MOD
            n += c

        patterns[(a,b)] = (prod*factorio[n]*modpow(d,MOD-2, MOD))%MOD
        childrens[(a,b)] = n+1
        return patterns[(a,b)], childrens[(a,b)]

    for a,b in edges:
        rec(a,b)
        rec(b,a)

    for k in range(N):
        p,c = rec(-1,k)
        print(p)


if __name__ == '__main__':
    N = int(input())
    adj = [list() for _ in range(N)]
    edges = []
    for _ in range(N-1):
        a,b = map(int,input().split())
        adj[a-1].append(b-1)
        adj[b-1].append(a-1)
        edges.append((a-1,b-1))

    solve(N,adj,edges)

Submission status: Time Limit Exceeded

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

def abc():
    global qqq
    for i in range(len(ppp)-1,0,-1):
        qqq=qqq*cmb(ppp[i],ppp[i-1])%mod
    return qqq

mod=10**9+7
MAX=2*10**5+100
g1=[1,1]
g2=[1,1]
for i in range(2,MAX+1):
    num_1=g1[-1]*i%mod
    g1.append(num_1)
    g2.append(pow(num_1,mod-2,mod))
def cmb(n,r):
    return g1[n]*g2[r]*g2[n-r]%mod

N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]

data=[[] for i in range(N+1)]
for A,B in AB:
    data[A].append(B)
    data[B].append(A)

parent=[0]*(N+1)
flag=[0]*(N+1)
child=[0]*(N+1)
parent[1]=-1
flag[1]=1
que=[1]
ddd=deque([])
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==0:
                flag[v]=1
                h.append(v)
                parent[v]=u
                child[u]+=1
        if child[u]==0:
            ddd.append(u)
    que=h
size=[0]*(N+1)
lst=[0]*(N+1)
while ddd:
    u=ddd.pop()
    size[u]=1
    qqq=1
    ppp=[]
    for v in data[u]:
        if v==parent[u]:
            child[v]-=1
            if child[v]==0:
                ddd.appendleft(v)
            continue
        else:
            size[u]+=size[v]
            if ppp:
                ppp.append(size[v]+ppp[-1])
            else:
                ppp.append(size[v])
            qqq=qqq*lst[v]%mod
    lst[u]=abc()
que=deque(data[1][:])
ans=[0]*(N+1)
lsls=[0]*(N+1)
ans[1]=lst[1]
lsls[1]=1
while que:
    u=que.pop()
    par=parent[u]
    qqq=1
    qqq*=lsls[par]
    ppp=N-size[par]
    for v in data[par]:
        if v==u:
            continue
        if v==parent[par]:
            continue
        else:
            qqq=qqq*lst[v]*cmb(size[v]+ppp,ppp)%mod
            ppp+=size[v]
    lsls[u]=qqq
    ppp=N-size[u]
    for v in data[u]:
        if v==parent[u]:
            continue
        else:
            qqq=qqq*lst[v]*cmb(size[v]+ppp,ppp)%mod
            ppp+=size[v]
            que.appendleft(v)
    ans[u]=qqq
for i in range(1,N+1):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(int(2e5))

MOD = 10**9 + 7
MAX = int(2e5)


def div(a, b):
    return a * pow(b, MOD-2, MOD) % MOD


FACT = [1] * (MAX+1)
for i in range(1, MAX+1):
    FACT[i] = (i * FACT[i-1]) % MOD
INV = [1] * (MAX+1)
INV[MAX] = div(1, FACT[MAX])
for i in range(MAX, 0, -1):
    INV[i-1] = (INV[i] * i) % MOD

memo = {}


def query(adj, pos, prev):
    # returns (pattern, count)
    # print("q", pos, prev)
    if (pos, prev) in memo:
        return memo[(pos, prev)]
    if len(adj[pos]) == 1 and prev in adj[pos]:
        memo[(pos, prev)] = (1, 1)
    else:
        pattern = 1
        count = 0
        for nxt in adj[pos]:
            if nxt == prev:
                continue
            ptn, cnt = query(adj, nxt, pos)
            count += cnt
            pattern = (pattern * ptn) * \
                (FACT[count] * INV[cnt] * INV[count-cnt]) % MOD
        count += 1
        memo[(pos, prev)] = (pattern, count)
    return memo[(pos, prev)]


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    for i in range(N):
        pattern, count = query(adj, i, -1)
        print(pattern)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(int(1e9))

MOD = int(1e9+7)
N = int(input().strip())

fact = [1]*(N+1)
rfact = [1]*(N+1)
r = 1
for i in range(1, N+1):
  fact[i] = r = r * i % MOD
rfact[N] = r = pow(fact[N], MOD-2, MOD)
for i in range(N, 0, -1):
  rfact[i-1] = r = r * i % MOD



tree = {k:set() for k in range(1, N+1)}
for _ in range(N-1):
  a,b = map(int, input().strip().split())
  tree[a].add(b)
  tree[b].add(a)

def dfs(done_set, cand_set):
  if len(cand_set) + len(done_set) == N:
    return fact[len(cand_set)]  # cand_setの順番を数えるだけ
  elif len(cand_set) == 1:
    cand = cand_set.pop()
    return dfs(done_set|{cand}, tree[cand]-{cand})
  else:
    ret = 0
    for cand in cand_set:
      next_cand_set = cand_set - {cand}
      next_cand_set |= tree[cand] - {cand}
      ret += dfs(done_set|{cand}, next_cand_set)
      ret = ret % MOD
      return ret

for k in range(1, N+1):
  print(dfs({k}, tree[k]))

Submission status: Time Limit Exceeded

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

def modfac(n, MOD):
 
    f = 1
    factorials = [1]
    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 modnCr(n,r,mod,fac,inv): #上で求めたfacとinvsを引数に入れるべし(上の関数で与えたnが計算できる最大のnになる)

    return fac[n] * inv[n-r] * inv[r] % mod


N = int(input())

lis = [ [] for i in range(N)]

for i in range(N-1):

    a,b = map(int,input().split())
    a -= 1
    b -= 1

    lis[a].append(b)
    lis[b].append(a)

lsub = []
mod = 10**9+7

fac,inv = modfac(N+1,mod)
dic = {}
def dfs(v,p):

    if (v,p) in dic:
        return dic[(v,p)]

    ret = 1
    retk= 1
    nlis = []
    for nex in lis[v]:
        if nex != p:
            numc,kake = dfs(nex,v)
            nlis.append(kake)
            retk += kake
            ret *= numc
            ret %= mod
    nls = sum(nlis)
    for ii in range(len(nlis)-1):
        i = nlis[ii]
        ret *= modnCr(nls,i,mod,fac,inv)
        nls -= i
        ret%mod

    dic[(v,p)] = [ret%mod,retk]
    return ret%mod,retk

for i in range(N):

    ll,rr = dfs(i,i)
    print (ll)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from functools import lru_cache

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

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


# MOD = 998244353

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


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


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


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

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


def mod_inv(a, mod):
    """
    a の逆元
    :param int a:
    :param int mod:
    """
    return pow(a, mod - 2, mod)


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

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

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

memo = [None for _ in range(N)]


@lru_cache(maxsize=1 << (2 * 10 ** 6).bit_length())
def solve(v, p):
    if memo[v] is not None:
        ret, children_cnt, without = memo[v]
        if without is not None:
            r, cnt = solve(without, v)
            ret *= finvs[children_cnt]
            ret %= MOD
            ret *= factorials[children_cnt + cnt]
            ret %= MOD
            ret *= finvs[cnt]
            ret %= MOD
            ret *= r
            ret %= MOD
            children_cnt += cnt
            without = None
            memo[v] = ret, children_cnt, without
        if p is None:
            return ret, children_cnt + 1
        r, cnt = solve(p, v)
        ret *= finvs[children_cnt]
        ret %= MOD
        ret *= factorials[children_cnt - cnt]
        ret %= MOD
        ret *= factorials[cnt]
        ret %= MOD
        ret *= mod_inv(r, MOD)
        ret %= MOD
        return ret, children_cnt - cnt + 1

    ret = 1
    children = []
    for u in graph[v]:
        if u == p:
            continue
        r, cnt = solve(u, v)
        children.append(cnt)
        ret *= r
        ret %= MOD
    children_cnt = sum(children)
    ret *= factorials[children_cnt]
    ret %= MOD
    for cnt in children:
        ret *= finvs[cnt]
        ret %= MOD

    memo[v] = ret, children_cnt, p
    return ret, children_cnt + 1


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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict as dd
MOD = 10 ** 9 + 7

N = int(input())
factorial = [1]
fact_invs = [1]
for i in range(1, N+1):
    factorial.append((factorial[-1]*i) % MOD)
    fact_invs.append(pow(factorial[-1], MOD-2, MOD))

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

memo_num = dd(int)
memo_ptn = dd(int)
for k in range(1, N+1):
    visited = [False] * (N+1)
    stk = [(None, k)]
    i = 0
    while stk:
        parent, node = stk[i]

        if not visited[node]:
            visited[node] = True
            for child in edge[node].keys():
                if not visited[child] and (node, child) not in memo_num:
                    stk.append((node, child))
                    i += 1
        else:
            num = 1
            ptn = 1
            for child in edge[node].keys():
                if child != parent:
                    n = memo_num[(node, child)]
                    num += n
                    ptn *= fact_invs[n]
                    ptn %= MOD
                    p = memo_ptn[(node, child)]
                    ptn *= p
                    ptn %= MOD
            ptn *= factorial[num-1]
            ptn %= MOD
            memo_num[(parent, node)] = num
            memo_ptn[(parent, node)] = ptn
            i -= 1
            stk.pop()
    print(memo_ptn[(None, k)])

Submission status: Time Limit Exceeded

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

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

while Q:
    x=Q.pop()

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

FROM1=[-1]*(N+1)
FROM2=[-1]*(N+1)

for x in SORTED[::-1]:
    if len(E[x])==1 and x!=1:
        FROM1[x]=1
        FROM2[x]=1
    else:
        L=[]
        A=1
        for to in E[x]:
            if to==P[x]:
                continue
            L.append(FROM1[to])
            A=A*FROM2[to]%mod
        #print(x,L)
        FROM1[x]=sum(L)+1
        S=sum(L)

        for l in L:
            A=A*Combi(S,l)%mod
            S-=l
        FROM2[x]=A

TO1=[-1]*(N+1)
TO2=[-1]*(N+1)
TO2[1]=1

for x in SORTED:
    if x!=1 and len(E[x])==1:
        continue
    
    SS=1
    L=[]
    for to in E[x]:
        if to==P[x]:
            continue
        
        SS=SS*FROM2[to]%mod
        L.append(FROM1[to])

    L.append(N-1-sum(L))

    for to in E[x]:
        if to==P[x]:
            continue
        
        A=SS*pow(FROM2[to],mod-2,mod)*TO2[x]%mod
        S=sum(L)-FROM1[to]
        flag=0

        #print(x,L)
        for l in L:
            if flag==0 and l==FROM1[to]:
                flag=1
                continue
            A=A*Combi(S,l)%mod
            S-=l
        TO2[to]=A

for i in range(1,N+1):
    ANS=TO2[i]

    L=[]

    for to in E[i]:
        if to==P[i]:
            continue
        ANS=ANS*FROM2[to]%mod
        L.append(FROM1[to])

    L.append(N-1-sum(L))
    S=sum(L)
    for l in L:
        ANS=ANS*Combi(S,l)%mod
        S-=l
    print(ANS)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate,chain
from sys import setrecursionlimit

setrecursionlimit(10000000)

MOD = 10**9+7


# 拡張ユークリッド互除法
# ax + by = gcd(a,b)の最小整数解を返す
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m




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

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

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


patterns = dict()
childrens = dict()
def rec(a,b):
    if (a,b) in patterns:
        return patterns[(a,b)], childrens[(a,b)]
    if a != -1 and len(adj[b]) == 1:
        patterns[(a,b)] = 1
        childrens[(a,b)] = 1
        return 1,1

    prod = 1 # product of patterns
    d = 1 # denominator of multinomial coefficient
    n = 0 # total childrens
    for c in adj[b]:
        if a == c:
            continue
        p,c = rec(b,c)
        prod *= p
        prod %= MOD
        d *= factorio[c]
        d %= MOD
        n += c

    patterns[(a,b)] = (prod*factorio[n]*modinv(d,MOD))%MOD
    childrens[(a,b)] = n+1
    return patterns[(a,b)], childrens[(a,b)]

for a,b in edges:
    rec(a,b)
    rec(b,a)

for k in range(N):
    p,c = rec(-1,k)
    print(p)