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 math
import sys, resource
from collections import deque

sys.setrecursionlimit(10 ** 9)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            pways(i, v)
            num += treenum[(v,i)]
            ans = (ans*dpv[(v,i)]) *invfact[treenum[(v,i)]] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    pways(1,1)

    bfs = deque([])
    for i in to[1]:
        bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        # if dpv.get(parent,parent) == None:
        treenum[(i[1],i[0])] = N-treenum[(i[0],i[1])]
        #dpv[i[1]][i[0]] = (dpv[i[0]][i[0]]*invfact[treenum[i[0]][i[0]]-1]*fact[treenum[i[0]][i[0]]-1-treenum[i[0]][i[1]]]*fact[treenum[i[0]][i[1]]]% (MOD)/dpv[i[0]][i[1]]) % (MOD)
        val = dpv[(i[0],i[0])]*invfact[treenum[(i[0],i[0])]-1]*fact[treenum[(i[0],i[0])]-1-treenum[(i[0],i[1])]]*fact[treenum[(i[0],i[1])]] % (MOD)
        dpv[(i[1],i[1])] =  val *invfact[treenum[(i[1],i[0])]] *invfact[treenum[(i[0],i[1])]-1] * fact[N-1] % (MOD)

        for j in to[i[1]]:
            if j != i[0]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[(i,i)]))

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys, resource
from collections import deque

sys.setrecursionlimit(10 ** 9)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            pways(i, v)
            num += treenum[(v,i)]
            ans = (ans*dpv[(v,i)]) *invfact[treenum[(v,i)]] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    pways(1,1)

    bfs = deque([])
    for i in to[1]:
        bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        # if dpv.get(parent,parent) == None:
        treenum[(i[1],i[0])] = N-treenum[(i[0],i[1])]
        #dpv[i[1]][i[0]] = (dpv[i[0]][i[0]]*invfact[treenum[i[0]][i[0]]-1]*fact[treenum[i[0]][i[0]]-1-treenum[i[0]][i[1]]]*fact[treenum[i[0]][i[1]]]% (MOD)/dpv[i[0]][i[1]]) % (MOD)
        val = (dpv[(i[0],i[0])]*invfact[treenum[(i[0],i[0])]-1]*fact[treenum[(i[0],i[0])]-1-treenum[(i[0],i[1])]]*fact[treenum[(i[0],i[1])]]% (MOD)) % (MOD)
        dpv[(i[1],i[1])] =  val *invfact[treenum[(i[1],i[0])]] *invfact[treenum[(i[0],i[1])]-1] * fact[N-1] % (MOD)

        for j in to[i[1]]:
            if j != i[0]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[(i,i)]))

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys, resource
from collections import deque

sys.setrecursionlimit(10 ** 9)
resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            pways(i, v)
            num += treenum[(v,i)]
            ans = (ans*dpv[(v,i)]) *invfact[treenum[(v,i)]] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

def revways(v, parent):
    global dpv, treenum, N, fact, invfact, MOD

    # if dpv.get(parent,parent) == None:
    treenum[(parent,v)] = N-treenum[(v,parent)]
    #dpv[parent][v] = (dpv[v][v]*invfact[treenum[v][v]-1]*fact[treenum[v][v]-1-treenum[v][parent]]*fact[treenum[v][parent]]% (MOD)/dpv[v][parent]) % (MOD)
    val = (dpv[(v,v)]*invfact[treenum[(v,v)]-1]*fact[treenum[(v,v)]-1-treenum[(v,parent)]]*fact[treenum[(v,parent)]]% (MOD)) % (MOD)
    dpv[(parent,parent)] =  val *invfact[treenum[(parent,v)]] *invfact[treenum[(v,parent)]-1] * fact[N-1] % (MOD)


def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    pways(1,1)

    bfs = deque([])
    for i in to[1]:
        bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in to[i[1]]:
            if j != i[0]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[(i,i)]))

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys, resource
from collections import deque

sys.setrecursionlimit(10 ** 9)

to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            pways(i, v)
            num += treenum[(v,i)]
            ans = (ans*dpv[(v,i)]) *invfact[treenum[(v,i)]] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

def revways(v, parent):
    global dpv, treenum, N, fact, invfact, MOD

    # if dpv.get(parent,parent) == None:
    treenum[(parent,v)] = N-treenum[(v,parent)]
    #dpv[parent][v] = (dpv[v][v]*invfact[treenum[v][v]-1]*fact[treenum[v][v]-1-treenum[v][parent]]*fact[treenum[v][parent]]% (MOD)/dpv[v][parent]) % (MOD)
    val = (dpv[(v,v)]*invfact[treenum[(v,v)]-1]*fact[treenum[(v,v)]-1-treenum[(v,parent)]]*fact[treenum[(v,parent)]]% (MOD)) % (MOD)
    dpv[(parent,parent)] =  val *invfact[treenum[(parent,v)]] *invfact[treenum[(v,parent)]-1] * fact[N-1] % (MOD)


def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    pways(1,1)

    bfs = deque([])
    for i in range(1, N+1):
        if i in to[1]:
            bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in to[i[1]]:
            if j != i[0]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[(i,i)]))

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys, resource
from collections import deque

sys.setrecursionlimit(10 ** 9)

to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            pways(i, v)
            num += treenum[(v,i)]
            ans = (ans*dpv[(v,i)]) *invfact[treenum[(v,i)]] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

def revways(v, parent):
    global dpv, treenum, N, fact, invfact, MOD

    # if dpv.get(parent,parent) == None:
    treenum[(parent,v)] = N-treenum[(v,parent)]
    #dpv[parent][v] = (dpv[v][v]*invfact[treenum[v][v]-1]*fact[treenum[v][v]-1-treenum[v][parent]]*fact[treenum[v][parent]]% (MOD)/dpv[v][parent]) % (MOD)
    val = (dpv[(v,v)]*invfact[treenum[(v,v)]-1]*fact[treenum[(v,v)]-1-treenum[(v,parent)]]*fact[treenum[(v,parent)]]% (MOD)) % (MOD)
    dpv[(parent,parent)] =  val *invfact[treenum[(parent,v)]] *invfact[treenum[(v,parent)]-1] * fact[N-1] % (MOD)


def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    pways(1,1)

    bfs = deque([])
    for i in range(1, N+1):
        if i in to[1]:
            bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and j in to[i[1]]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[(i,i)]))

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from collections import deque

sys.setrecursionlimit(10 ** 9)

to = {0:[0]}
treenum = {(0,0):0}
dpv = {(0,0):0}
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) *invfact[c_num] % (MOD)
    
    treenum[(parent,v)] = num
    treenum[(v,v)] = N
    dpv[(parent,v)] = ans * fact[num-1] % (MOD)

    return dpv[(parent,v)], treenum[(parent,v)]

def revways(v, parent):
    global dpv, treenum, N, fact, invfact, MOD

    # if dpv.get(parent,parent) == None:
    treenum[(parent,v)] = N-treenum[(v,parent)]
    #dpv[parent][v] = (dpv[v][v]*invfact[treenum[v][v]-1]*fact[treenum[v][v]-1-treenum[v][parent]]*fact[treenum[v][parent]]% (MOD)/dpv[v][parent]) % (MOD)
    val = (dpv[(v,v)]*invfact[treenum[(v,v)]-1]*fact[treenum[(v,v)]-1-treenum[(v,parent)]]*fact[treenum[(v,parent)]]% (MOD)) % (MOD)
    dpv[(parent,parent)] =  val *invfact[treenum[(parent,v)]] *invfact[treenum[(v,parent)]-1] * fact[N-1] % (MOD)


def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())
    to = [[] for i in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    pways(1,1)

    bfs = deque([])
    for i in range(1, N+1):
        if i in to[1]:
            bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and j in to[i[1]]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[(i,i)]))

main()

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from collections import deque
to = [0]
treenum = [0]
dpv = [0]
N = 0
NMAX = 2*(10**5)
MOD = 10**9+7

fact = [0 for i in range(NMAX+1)]
fact[0] = 1
invfact = [0 for i in range(NMAX+1)]
invfact[0] = 1


def pways(v, parent):
    global to, dpv, treenum, fact, invfact, MOD

    if dpv[parent][v] != 0:
        return dpv[parent][v], treenum[parent][v]

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) *invfact[c_num] % (MOD)
    
    treenum[parent][v] = num
    treenum[v][v] = N
    dpv[parent][v] = ans * fact[num-1] % (MOD)

    return dpv[parent][v], treenum[parent][v]

def revways(v, parent):
    global dpv, treenum, N, fact, invfact, MOD

    if dpv[parent][parent] == 0:
        treenum[parent][v] = N-treenum[v][parent]
        #dpv[parent][v] = (dpv[v][v]*invfact[treenum[v][v]-1]*fact[treenum[v][v]-1-treenum[v][parent]]*fact[treenum[v][parent]]% (MOD)/dpv[v][parent]) % (MOD)
        val = (dpv[v][v]*invfact[treenum[v][v]-1]*fact[treenum[v][v]-1-treenum[v][parent]]*fact[treenum[v][parent]]% (MOD)) % (MOD)
        dpv[parent][parent] =  val *invfact[treenum[parent][v]] *invfact[treenum[v][parent]-1] * fact[N-1] % (MOD)


def main():
    global to, N, dpv, treenum, fact, invfact, NMAX, MOD
    input = sys.stdin.readline
    N = int(input())

    to = [[] for i in range(N+1)]
    dpv = [[0 for i in range(N+1)] for j in range(N+1)]
    treenum = [[0 for i in range(N+1)] for j in range(N+1)]

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


    for i in range(NMAX):
        fact[i+1] = fact[i]*(i+1)%(MOD)

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

    pways(1,1)

    bfs = deque([])
    for i in range(1, N+1):
        if i in to[1]:
            bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and j in to[i[1]]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[i][i]))

main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
arr = [list(map(int,input().split())) for _ in range(n-1)]
mod = 10**9+7

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

vect = [1] + [0] * (n-1)
x_parent_stack = [0]
search_order = []
parent = [-1]*(n)
child = [[] for _ in range(n)]
while x_parent_stack:
    p_num = x_parent_stack.pop()
    search_order.append(p_num)
    for i in graph[p_num]:
        if vect[i] == 0:
            vect[i] = 1
            x_parent_stack.append(i)
            parent[i] = p_num
            child[p_num].append(i)

fac = [1] * (n+10)
inv = [1] * (n+10)
ifac = [1] * (n+10)
for i in range(2,n+10):
    fac[i]=(fac[i-1]*i)%mod
    inv[i]=-(inv[mod%i]*(mod//i))%mod
    ifac[i]=(ifac[i-1]*inv[i])%mod

size = [1]*n + [0]
dp = [1]*n + [0]
for child in search_order[::-1]:
    p = parent[child]
    size[p] += size[child]
    dp[child] = dp[child] * fac[size[child]-1] % mod
    dp[p] = dp[p] * ifac[size[child]] * dp[child] % mod

size2 = [n-i+1 for i in size]
dp2 = [1] * n
for i in search_order[1:]:
    p = parent[i]
    dp2[i] = (dp[p] * ifac[size[p]-1]) * \
             (dp2[p] * ifac[size2[p]-1]) * \
             pow(dp[i],mod-2,mod) * \
             fac[size[i]] * fac[size2[i]-2] \
             % mod

for i in range(n):
    print(dp[i] * dp2[i] * fac[size[i]+size2[i]-2] * ifac[size[i]-1] * ifac[size2[i]-1] % mod)

Submission status: Time Limit Exceeded

Solution code:
import math
import sys
from collections import deque
to = [0]
treenum = [0]
dpv = [0]
N = 0

def pways(v, parent):
    global to, dpv, treenum

    if dpv[parent][v] != 0:
        return dpv[parent][v], treenum[parent][v]

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) / math.factorial(c_num) % (10**9+7)
    
    treenum[parent][v] = num
    treenum[v][v] = N
    dpv[parent][v] = ans * math.factorial(num-1) % (10**9+7)

    return dpv[parent][v], treenum[parent][v]

def revways(v, parent):
    global dpv, treenum, N

    if dpv[parent][parent] == 0:
        treenum[parent][v] = N-treenum[v][parent]
        dpv[parent][v] = (dpv[v][v]/math.factorial(treenum[v][v]-1)*math.factorial(treenum[v][v]-1-treenum[v][parent])*math.factorial(treenum[v][parent])/dpv[v][parent]) % (10**9+7)
        dpv[parent][parent] =  dpv[parent][v] /  math.factorial(treenum[parent][v]) * dpv[v][parent]/math.factorial(treenum[v][parent]-1) * math.factorial(N-1) % (10**9+7)


def main():
    global to, N, dpv, treenum
    input = sys.stdin.readline
    N = int(input())

    to = [[] for i in range(N+1)]
    dpv = [[0 for i in range(N+1)] for j in range(N+1)]
    treenum = [[0 for i in range(N+1)] for j in range(N+1)]

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

    pways(1,1)

    bfs = deque([])
    for i in range(1, N+1):
        if i in to[1]:
            bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and j in to[i[1]]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[i][i]))

main()

Submission status: Time Limit Exceeded

Solution code:
import math
from collections import deque
to = [0]
treenum = [0]
dpv = [0]
N = 0

def pways(v, parent):
    global to, dpv, treenum

    if dpv[parent][v] != 0:
        return dpv[parent][v], treenum[parent][v]

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) / math.factorial(c_num) % (10**9+7)
    
    treenum[parent][v] = num
    treenum[v][v] = N
    dpv[parent][v] = ans * math.factorial(num-1) % (10**9+7)

    return dpv[parent][v], treenum[parent][v]

def revways(v, parent):
    global dpv, treenum, N

    if dpv[parent][parent] == 0:
        treenum[parent][v] = N-treenum[v][parent]
        dpv[parent][v] = (dpv[v][v]/math.factorial(treenum[v][v]-1)*math.factorial(treenum[v][v]-1-treenum[v][parent])*math.factorial(treenum[v][parent])/dpv[v][parent]) % (10**9+7)
        dpv[parent][parent] =  dpv[parent][v] /  math.factorial(treenum[parent][v]) * dpv[v][parent]/math.factorial(treenum[v][parent]-1) * math.factorial(N-1) % (10**9+7)


def main():
    global to, N, dpv, treenum
    N = int(input())
    ab = [map(int,input().split()) for i in range(N-1)]

    to = [[] for i in range(N+1)]
    dpv = [[0 for i in range(N+1)] for j in range(N+1)]
    treenum = [[0 for i in range(N+1)] for j in range(N+1)]

    for i in ab:
        l = list(i)
        a = l[0]
        b = l[1]
        to[a].append(b)
        to[b].append(a)

    pways(1,1)

    bfs = deque([])
    for i in range(1, N+1):
        if i in to[1]:
            bfs.append([1,i])

    while len(bfs) != 0:
        i = bfs.popleft()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and j in to[i[1]]:
                bfs.append([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[i][i]))


main()

Submission status: Time Limit Exceeded

Solution code:
import math, queue
to = [0]
treenum = [0]
dpv = [0]
N = 0

def pways(v, parent):
    global to, dpv, treenum

    if dpv[parent][v] != 0:
        return dpv[parent][v], treenum[parent][v]

    ans = 1
    num = 1
    for i in to[v]:
        if i != parent and i != v:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) / math.factorial(c_num) % (10**9+7)
    
    treenum[parent][v] = num
    treenum[v][v] = N
    dpv[parent][v] = ans * math.factorial(num-1) % (10**9+7)

    return dpv[parent][v], treenum[parent][v]

def revways(v, parent):
    global dpv, treenum, N

    if dpv[parent][parent] == 0:
        treenum[parent][v] = N-treenum[v][parent]
        dpv[parent][v] = (dpv[v][v]/math.factorial(treenum[v][v]-1)*math.factorial(treenum[v][v]-1-treenum[v][parent])*math.factorial(treenum[v][parent])/dpv[v][parent]) % (10**9+7)
        dpv[parent][parent] =  dpv[parent][v] /  math.factorial(treenum[parent][v]) * dpv[v][parent]/math.factorial(treenum[v][parent]-1) * math.factorial(N-1) % (10**9+7)


def main():
    global to, N, dpv, treenum
    N = int(input())
    ab = [map(int,input().split()) for i in range(N-1)]

    to = [[] for i in range(N+1)]
    dpv = [[0 for i in range(N+1)] for j in range(N+1)]
    treenum = [[0 for i in range(N+1)] for j in range(N+1)]

    for i in ab:
        l = list(i)
        a = l[0]
        b = l[1]
        to[a].append(b)
        to[b].append(a)

    pways(1,1)

    bfs = queue.Queue()
    for i in range(1, N+1):
        if i in to[1]:
            bfs.put([1,i])

    while not bfs.empty():
        i = bfs.get()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and j in to[i[1]]:
                bfs.put([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[i][i]))


main()

Submission status: Time Limit Exceeded

Solution code:
import math, queue
list1 = [0]
treenum = [0]
dpv = [0]
N = 0

def pways(v, parent):
    global list1, dpv, treenum

    if dpv[parent][v] != 0:
        return dpv[parent][v], treenum[parent][v]

    ans = 1
    num = 1

    for i in range(v,N+1):
        if i != parent and i != v and list1[v][i] == 1:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) / math.factorial(c_num) % (10**9+7)
    
    treenum[parent][v] = num
    treenum[v][v] = N
    dpv[parent][v] = ans * math.factorial(num-1) % (10**9+7)

    return dpv[parent][v], treenum[parent][v]

def revways(v, parent):
    global list1, dpv, treenum, N

    if dpv[parent][parent] == 0:
        treenum[parent][v] = N-treenum[v][parent]
        dpv[parent][v] = (dpv[v][v]/math.factorial(treenum[v][v]-1)*math.factorial(treenum[v][v]-1-treenum[v][parent])*math.factorial(treenum[v][parent])/dpv[v][parent]) % (10**9+7)
        dpv[parent][parent] =  dpv[parent][v] /  math.factorial(treenum[parent][v]) * dpv[v][parent]/math.factorial(treenum[v][parent]-1) * math.factorial(N-1) % (10**9+7)


def main():
    global list1, N, dpv, treenum
    N = int(input())
    ab = [map(int,input().split()) for i in range(N-1)]

    list1 = [[0 for i in range(N+1)] for j in range(N+1)]
    dpv = [[0 for i in range(N+1)] for j in range(N+1)]
    treenum = [[0 for i in range(N+1)] for j in range(N+1)]

    for i in ab:
        l = list(i)
        a = l[0]
        b = l[1]
        list1[a][b] = 1
        list1[b][a] = 1

    pways(1,1)

    bfs = queue.Queue()
    for i in range(1, N+1):
        if list1[1][i] == 1:
            bfs.put([1,i])

    while not bfs.empty():
        i = bfs.get()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and list1[i[1]][j] == 1:
                bfs.put([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[i][i]))


main()

Submission status: Time Limit Exceeded

Solution code:
import math, queue
list1 = [0]
treenum = [0]
dpv = [0]
N = 0

def pways(v, parent):
    global list1, dpv, treenum

    if dpv[parent][v] != 0:
        return dpv[parent][v], treenum[parent][v]

    ans = 1
    num = 1

    for i in range(1,N+1):
        if i != parent and i != v and list1[v][i] == 1:
            c_ans, c_num = pways(i, v)
            num += c_num
            ans = (ans*c_ans) / math.factorial(c_num) % (10**9+7)
    
    treenum[parent][v] = num
    treenum[v][v] = N
    dpv[parent][v] = ans * math.factorial(num-1) % (10**9+7)

    return dpv[parent][v], treenum[parent][v]

def revways(v, parent):
    global list1, dpv, treenum, N

    if dpv[parent][parent] == 0:
        treenum[parent][v] = N-treenum[v][parent]
        dpv[parent][v] = (dpv[v][v]/math.factorial(treenum[v][v]-1)*math.factorial(treenum[v][v]-1-treenum[v][parent])*math.factorial(treenum[v][parent])/dpv[v][parent]) % (10**9+7)
        dpv[parent][parent] =  dpv[parent][v] /  math.factorial(treenum[parent][v]) * dpv[v][parent]/math.factorial(treenum[v][parent]-1) * math.factorial(N-1) % (10**9+7)


def main():
    global list1, N, dpv, treenum
    N = int(input())
    ab = [map(int,input().split()) for i in range(N-1)]

    list1 = [[0 for i in range(N+1)] for j in range(N+1)]
    dpv = [[0 for i in range(N+1)] for j in range(N+1)]
    treenum = [[0 for i in range(N+1)] for j in range(N+1)]

    for i in ab:
        l = list(i)
        a = l[0]
        b = l[1]
        list1[a][b] = 1
        list1[b][a] = 1

    pways(1,1)

    bfs = queue.Queue()
    for i in range(1, N+1):
        if list1[1][i] == 1:
            bfs.put([1,i])

    while not bfs.empty():
        i = bfs.get()
        revways(i[0], i[1])
        for j in range(1, N+1):
            if j != i[0] and list1[i[1]][j] == 1:
                bfs.put([i[1],j])

    for i in range(1,N+1):
        print(int(dpv[i][i]))


main()

Submission status: Time Limit Exceeded

Solution code:
import math
list1 = [0]
N = 0

def pways(p, rt):
    global list1
    rt[p] = 1
    ans = 1
    num = 1

    for i in range(1,N+1):
        if list1[p][i] == 1 and rt[i] == 0:
            c_ans, c_num = pways(i, rt)
            num += c_num
            ans = (ans*c_ans) / math.factorial(c_num) % (10**9+7)
    
    ans = ans * math.factorial(num-1) % (10**9+7)

    return ans, num

def main():
    global list1, N
    N = int(input())
    ab = [map(int,input().split()) for i in range(N-1)]

    list1 = [[0 for i in range(N+1)] for j in range(N+1)]

    for i in ab:
        l = list(i)
        a = l[0]
        b = l[1]
        list1[a][b] = 1
        list1[b][a] = 1

    for i in range(1,N+1):
        rt = [0 for i in range(N+1)]
        ans, num = pways(i,rt)
        print(int(ans))

main()

Submission status: Time Limit Exceeded

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

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

mod = 10 ** 9 + 7

fac = [1]
inv = [1]
for i in range(1, N + 5) :
  fac.append(fac[-1] * i)
  inv.append(pow(fac[-1], mod - 2, mod))

def comb(n, r) :
  return fac[n] * inv[n-r] * inv[r] % mod

pattern = [1] * N
subtree = [0] * N

def dfs(cur, pre=-1) :
  for nex in vec[cur] :
    if nex == pre : continue
    dfs(nex, cur)
    pattern[cur] *= pattern[nex] * comb(subtree[cur] + subtree[nex], subtree[nex]) % mod
    pattern[cur] %= mod
    subtree[cur] += subtree[nex]
  subtree[cur] += 1
  
dfs(0)

q = [(0, -1, 1)]
while q :
  cur, pre, cp = q.pop()
  pattern[cur] *= cp * comb(N - 1, subtree[cur] - 1)
  pattern[cur] %= mod
  for nex in vec[cur] :
    if nex == pre : continue
    ncp = pattern[cur] * pow(pattern[nex] * comb(N - 1, subtree[nex]), mod - 2, mod) % mod
    q.append((nex, cur, ncp))
  
for i in range(N) :
  print(pattern[i])

Submission status: Time Limit Exceeded

Solution code:
import sys

def solve():
    input = lambda: sys.stdin.readline().rstrip()
    sys.setrecursionlimit(10 ** 7)
    mod = 10 ** 9 + 7
    
    def comb(n, r):
        if r > n: return 0
        return fac[n] * inv[r] * inv[n - r] % mod

    def dfs(v, Pa=-1):
        for u in to[v]:
            if u == Pa: continue
            dfs(u, v)
            size[v] += size[u]
            dp[v] *= dp[u] % mod
            dp[v] *= comb(size[v], size[u]) % mod
        size[v] += 1

    def bfs(v, Pa=-1, P_val=1, P_sz=0):
        ans[v] = P_val * dp[v] * comb(n - 1, P_sz) % mod
        for u in to[v]:
            if u == Pa: continue
            val = ans[v] * INV(dp[u] * comb(n - 1, size[u])) % mod
            bfs(u, v, val, n - size[u])

    n = int(input())
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = map(lambda x: int(x) - 1, input().split())
        to[a].append(b)
        to[b].append(a)

    fac = [1] * (n + 2)
    inv = [1] * (n + 2)

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

    dp = [1] * n
    size = [0] * n
    ans = [0] * n

    dfs(0)
    bfs(0)
    print(*ans, sep='\n')

if __name__ == '__main__':
    solve()