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: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
        if p==0: sys.exit()
        for x in neighbor[p]:
            if x==par[p]: continue
            par[x]=p
            descend[p]+=cur(x)
        return descend[p]


def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[1]+[0]*(n)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

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

Submission status: Runtime Error

Solution code:
from collections import deque


LARGE = 10 ** 9 + 7


def solve(n, edge_list):
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        a, b = edge_list[i]
        g[a].append(b)
        g[b].append(a)

    # root 0
    parent = [-1] * n
    parent[0] = 0
    children = [[] for _ in range(n)]
    queue = deque([0])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if parent[q] == -1:
                parent[q] = p
                children[p].append(q)
                queue.append(q)

    # n_children
    count_children_res = [-1] * n

    def count_children(x):
        if count_children_res[x] != -1:
            return count_children_res[x]
        elif len(children[x]) == 0:
            count_children_res[x] = 0
            return 0
        else:
            r = len(children[x]) + sum([count_children(y) for y in children[x]])
            count_children_res[x] = r
            return r

    r0 = count_children(0)

    factorial = [1] * n
    for i in range(1, n):
        factorial[i] = (factorial[i - 1] * i) % LARGE
    factorial_inv = [1] * n
    factorial_inv[-1] = pow(factorial[-1], LARGE - 2, LARGE)
    for i in range(n - 2, 0, -1):
        factorial_inv[i] = (factorial_inv[i + 1] * (i + 1)) % LARGE

    assign_children_res = [-1] * n

    def assign_children(x):
        if assign_children_res[x] != -1:
            return assign_children_res[x]
        elif len(children[x]) == 0:
            assign_children_res[x] = 1
            return 1
        else:
            r = factorial[count_children_res[x]]
            for y in children[x]:
                r *= assign_children(y)
                r *= factorial_inv[count_children_res[y] + 1]
                r %= LARGE
            assign_children_res[x] = r
            return r

    r0 = assign_children(0)

    # all direction
    assign_parents_res = [-1] * n
    assign_parents_res[0] = 1

    def assign_parents(x):
        if assign_parents_res[x] != -1:
            return assign_parents_res[x]
        else:
            r = factorial[n - 2 - count_children_res[x]]
            for y in children[parent[x]]:
                if y == x:
                    continue
                r *= assign_children_res[y]
                r *= factorial_inv[count_children_res[y] + 1]
                r %= LARGE
            # parent
            r *= assign_parents(parent[x])
            r *= factorial_inv[n - count_children_res[parent[x]] - 1]
            r %= LARGE
            assign_parents_res[x] = r
            return r

    for i in range(n):
        r1 = assign_parents(i)
    res_list = [0] * n
    res_list[0] = r0

    for i in range(1, n):
        res = factorial[n - 1]
        # children
        for j in children[i]:
            res *= assign_children_res[j]
            res *= factorial_inv[count_children_res[j] + 1]
            res %= LARGE
        # parent
        res *= assign_parents_res[i]
        res *= factorial_inv[n - 1 - count_children_res[i]]
        res %= LARGE
        res_list[i] = res
    # print(res_list)
    return res_list


def main():
    n = int(input())
    edge_list = []
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge_list.append((a - 1, b - 1))
    res_list = solve(n, edge_list)
    for res in res_list:
        print(res)


def test():
    assert solve(3, [(0, 1), (0, 2)]) == [2, 1, 1]
    assert solve(2, [(0, 1)]) == [1, 1]
    assert solve(5, [(0, 1), (1, 2), (2, 3), (2, 4)]) == [2, 8, 12, 3, 3]
    assert solve(8, [(0, 1), (1, 2), (2, 3), (2, 4), (2, 5), (5, 6), (5, 7)]) == [40, 280, 840, 120, 120, 504, 72, 72]


if __name__ == "__main__":
    # test()
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
        for x in neighbor[p]:
            if x==par[p]: continue
            par[x]=p
            descend[p]+=cur(x)
        try:
            return descend[p]
        except: print(0);sys.exit()


def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[1]+[0]*(n)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
        for x in neighbor[p]:
            if x==par[p]: continue
            try:
                par[x]=p
            except: print(0);sys.exit()
            descend[p]+=cur(x)
        return descend[p]


def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[1]+[0]*(n)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
        for x in neighbor[p]:
            try:
                if x==par[p]: continue
            except: print(0);sys.exit()
            par[x]=p
            descend[p]+=cur(x)
        return descend[p]


def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[1]+[0]*(n)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

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

Submission status: Runtime Error

Solution code:
from collections import deque


LARGE = 10 ** 9 + 7


def solve(n, edge_list):
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        a, b = edge_list[i]
        g[a].append(b)
        g[b].append(a)

    # root 0
    parent = [-1] * n
    parent[0] = 0
    children = [[] for _ in range(n)]
    queue = deque([0])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if parent[q] == -1:
                parent[q] = p
                children[p].append(q)
                queue.append(q)

    # n_children
    count_children_res = [-1] * n

    def count_children(x):
        if count_children_res[x] != -1:
            return count_children_res[x]
        elif len(children[x]) == 0:
            count_children_res[x] = 0
            return 0
        else:
            r = len(children[x]) + sum([count_children(y) for y in children[x]])
            count_children_res[x] = r
            return r

    r0 = count_children(0)

    factorial = [1] * n
    for i in range(1, n):
        factorial[i] = (factorial[i - 1] * i) % LARGE
    factorial_inv = [1] * n
    factorial_inv[-1] = pow(factorial[-1], LARGE - 2, LARGE)
    for i in range(n - 2, 0, -1):
        factorial_inv[i] = (factorial_inv[i + 1] * (i + 1)) % LARGE

    assign_children_res = [-1] * n

    def assign_children(x):
        if assign_children_res[x] != -1:
            return assign_children_res[x]
        elif len(children[x]) == 0:
            assign_children_res[x] = 1
            return 1
        else:
            r = factorial[count_children_res[x]]
            for y in children[x]:
                r *= assign_children(y)
                r *= factorial_inv[count_children_res[y] + 1]
                r %= LARGE
            assign_children_res[x] = r
            return r

    r0 = assign_children(0)

    # all direction
    assign_parents_res = [-1] * n
    assign_parents_res[0] = 1

    def assign_parents(x):
        if assign_parents_res[x] != -1:
            return assign_parents_res[x]
        else:
            r = factorial[n - 2 - count_children_res[x]]
            for y in children[parent[x]]:
                if y == x:
                    continue
                r *= assign_children_res[y]
                r *= factorial_inv[count_children_res[y] + 1]
                r %= LARGE
            # parent
            r *= assign_parents(parent[x])
            r *= factorial_inv[n - count_children_res[parent[x]] - 1]
            r %= LARGE
            assign_parents_res[x] = r
            return r

    for i in range(n):
        r1 = assign_parents(i)
    res_list = [0] * n
    res_list[0] = r0

    for i in range(1, n):
        res = factorial[n - 1]
        # children
        for j in children[i]:
            res *= assign_children_res[j]
            res *= factorial_inv[count_children_res[j] + 1]
            res %= LARGE
        # parent
        res *= assign_parents_res[i]
        res *= factorial_inv[n - 1 - count_children_res[i]]
        res %= LARGE
        res_list[i] = res
    # print(res_list)
    return res_list


def main():
    n = int(input())
    edge_list = []
    for _ in range(n - 1):
        a, b = map(int, input().split())
        edge_list.append((a - 1, b - 1))
    res_list = solve(n, edge_list)
    for res in res_list:
        print(res)


def test():
    assert solve(3, [(0, 1), (0, 2)]) == [2, 1, 1]
    assert solve(2, [(0, 1)]) == [1, 1]
    assert solve(5, [(0, 1), (1, 2), (2, 3), (2, 4)]) == [2, 8, 12, 3, 3]
    assert solve(8, [(0, 1), (1, 2), (2, 3), (2, 4), (2, 5), (5, 6), (5, 7)]) == [40, 280, 840, 120, 120, 504, 72, 72]


if __name__ == "__main__":
    test()
    main()

Submission status: Runtime Error

Solution code:
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

def modinv2(x,r):
  return pow(x,r-2,r)

def mkfact(n,R):
    global factary
    factary = [1]*(n+1)
    for i in range(2,n+1):
        factary[i] = (factary[i-1]*i)%R

def comb2(n,a,R):
    return (factary[n] * modinv2(factary[n-a]*factary[a],R))%R

def comb(n,a,R):
    dend = 1
    for i in range(a):
        dend = (dend*(n-i))%R
    sor = 1
    for i in range(2,a+1):
        sor = (sor*i)%R
    return (dend*modinv2(sor,R))%R

#import sys,resource
#def setrlim():
#  sys.setrecursionlimit(250000)
#  soft,hard = resource.getrlimit(resource.RLIMIT_STACK)
  # setrlimit works on ubuntu (and atcoder), but not on WSL
#  resource.setrlimit(resource.RLIMIT_STACK, (128*1024*1024,hard))

def dfs(v,f):
    if f in dp[v]:
        return dp[v][f]
    a = 1
    ms = []
    for u in dst[v]:
        if u==f:
            continue
        mm,z = dfs(u,v)
        a = (a*z)%R
        ms.append(mm)
    k = len(dst[v])
    c = 1
    if len(ms)>1:
        t = sum(ms)
        for m in ms[1:]:
            c = (c*comb2(t,m,R))%R
            t -= m
    ret = (sum(ms)+1, (a*c)%R)
    if f>=0:
        dp[v][f] = ret
    return ret

# # # #
#setrlim()
n = inn()
mkfact(2*n+9,R)
dst = [{} for i in range(n)]
for i in range(n-1):
    a,b = inm()
    dst[a-1][b-1] = 1
    dst[b-1][a-1] = 1
dp = [{} for i in range(n)]
for i in range(n):
    z = dfs(i,-1)
    print(z[1])

Submission status: Runtime Error

Solution code:

from functools import lru_cache
import math
import sys

n = int(input())
sys.setrecursionlimit(max(1000, n))

is_leaf = [True] * (n+1)
is_leaf[0] = None
d = {i: [] for i in range(1,n+1)}
for i in range(n-1):
    a,b = [int(c) for c in input().split()]
    d[a].append(b)
    d[b].append(a)
    if len(d[a]) >= 2:
        is_leaf[a] = False
    if len(d[b]) >=2:
        is_leaf[b] = False

def _fact(n, M=10**9+7):
    tmp = 1
    for i in range(2,n+1):
        tmp *= i
        tmp %= M
    return tmp

M=10**9+7

# node : leaf
@lru_cache(2*n)
def _sub(a,b, M=10**9+7):
    # a -> bの枝に対してb以降の組み合わせ数・ノード数を返す
    if is_leaf[b]:
        return (1,1)
    counts = []
    num_nodes = []
    for node in d[b]:
        if node==a:
            continue
        count, num_node = _sub(b,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
#     if len(counts):
#         return ()
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count /= _fact(n)
    count *= _fact(total)
    return (int(count) , total+1)

for start in range(1,n+1):
    counts = []
    num_nodes = []
    for node in d[start]:
        count, num_node = _sub(start,node)
        counts.append(count)
        num_nodes.append(num_node)

    count = 1
    total = sum(num_nodes)
    
    for c in counts:
        count *= c
        count %= M
    for n in num_nodes:
        count /= _fact(n)
    count *= _fact(total)
    print(int(count))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
    for x in neighbor[p]:
        if x!=par[p]:
            par[x]=p
            descend[p]+=cur(x)
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%=mod
ans[1]=ans1

cur2(1)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    else:
        b=m
        (x, lastx) = (0, 1)
        (y, lasty) = (1, 0)
        while b != 0:
            q = a // b
            (a, b) = (b, a % b)
            (x, lastx) = (lastx - q * x, x)
            (y, lasty) = (lasty - q * y, y)
        return lastx % m

def cur(p):
    for x in neighbor[p]:
        if x!=par[p]:
            par[x]=p
            descend[p]+=cur(x)
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])
        ans[x]%=mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])
    ans1%mod
ans[1]=ans1

cur2(1)

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

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

def cur(p):
    for x in neighbor[p]:
        if x!=par[p]:
            par[x]=p
            descend[p]+=cur(x)
    return descend[p]

def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])%mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**12

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

def cur(n):
    for x in neighbor[n]:
        if x!=par[n]:
            par[x]=n
            descend[n]+=cur(x)
    return descend[n]

def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])%mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**9

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

def cur(n):
    for x in neighbor[n]:
        if x!=par[n]:
            par[x]=n
            descend[n]+=cur(x)
    return descend[n]

def cur2(p):
    for x in neighbor[p]:
        if x==par[p]: continue
        ans[x]=ans[p]*descend[x]*modinv(n-descend[x])%mod
        cur2(x)

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i*modinv(descend[i])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
s

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit=10**7

def cur(n):
    for x in neighbor[n]:
        if x!=par[n]:
            par[x]=n
            descend[n]+=cur(x)
    return descend[n]


def cur2(i):
    for x in neighbor[i]:
        if x!=par[i]:
            ans[x]=ans[i]*(descend[x])*modinv(n-descend[x])%mod
            cur2(x)

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

cur(1)
ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i%mod
for x in range(1,n+1):
    ans1=ans1*modinv(descend[x])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
def cur(n):
    for x in neighbor[n]:
        if x!=par[n]:
            par[x]=n
            descend[n]+=cur(x)
    return descend[n]


def cur2(i):
    for x in neighbor[i]:
        if x!=par[i]:
            ans[x]=ans[i]*(descend[x])*modinv(n-descend[x])%mod
            cur2(x)

def modinv(a,m=10**9+7):
    if a==0: return 1
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

cur(1)
ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i%mod
for x in range(1,n+1):
    ans1=ans1*modinv(descend[x])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
M = 10 ** 9 + 7
def inv(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return x0

def comb(n, k):
    r1 = 1
    for i in range(k):
        r1 = r1 * (n - i) % M
    r2 = 1
    for i in range(k):
        r2 = r2 * (i + 1) % M
    return r1 * inv(r2, M) % M

n = int(input())
g = [[] for i in range(n)]
for i in range(n - 1):
    a, b = [int(x) for x in input().split()]
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
r = 0

def count(i, last):
    rs = []
    for n in g[i]:
        if n != last:
            rs.append(count(n, i))
    if len(rs) == 0:
        return (1, 1)
    if len(rs) == 0:
        return (rs[0][0], rs[0][1] + 1)
    sz = sum(v[1] for v in rs)
    allsz = sz + 1
    r = 1
    for v in rs:
        r = r * comb(sz, v[1]) * v[0] % M
        sz -= v[1]
    return (r, allsz)

    
for i in range(n):
    print((r + count(i, -1)[0]) % M)

Submission status: Runtime Error

Solution code:
def cur(n):
    for x in neighbor[n]:
        if x!=par[n]:
            par[x]=n
            descend[n]+=cur(x)
    return descend[n]


def cur2(i):
    for x in neighbor[i]:
        if x!=par[i]:
            ans[x]=ans[i]*(descend[x])*modinv(n-descend[x])%mod
            cur2(x)

def modinv(a,m=10**9+7):
    b=m
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return lastx % m

mod=10**9+7
n=int(input())
neighbor=[[]  for _ in range(n+1)]
descend=[1]*(n+1)
par=[0]*(n+1)

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

cur(1)
ans=[1]*(n+1)
ans1=1
for i in range(1,n+1):
    ans1=ans1*i%mod
for x in range(1,n+1):
    ans1=ans1*modinv(descend[x])%mod
ans[1]=ans1
cur2(1)
for i in range(1,n+1):
    print(ans[i])

Submission status: Runtime Error

Solution code:
N = int(input())
G = [[] for _ in range(N)]
for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)
MOD = 10 ** 9 + 7
mod = MOD
n = N
fac = [1]
caf = [1]


def pow(n, p):
    res = 1
    while p > 0:
        if p % 2 == 0:
            n = n ** 2 % mod
            p //= 2
        else:
            res = res * n % mod
            p -= 1
    return res % mod


for i in range(1, n):
    fac.append((fac[i - 1] * i) % mod)
    caf.append(pow(fac[i], mod - 2))


def ncr(n, r):
    if n < r or r < 0:
        return 0
    return fac[n] * caf[r] * caf[n - r]


D = [{} for _ in range(N)]
D2 = [{} for _ in range(N)]


def dfs(s, d):
    if s in D[d]:
        return [D[d][s], D2[d][s]]
    res = []
    res2 = 1
    for sg in G[d]:
        if sg != s:
            tres = dfs(d, sg)
            res.append(tres[0] + 1)
            res2 *= tres[1]
    sres = sum(res)
    D[d][s] = sres
    for sr in res:
        res2 *= ncr(sres, sr)
        res2 %= MOD
        sres -= sr
    D2[d][s] = res2
    return [D[d][s], D2[d][s]]


for i in range(N):
    dfs(N + 1, i)

for i in range(N):
    print(D2[i][N + 1])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
from __future__ import division, print_function

import os
import sys
from io import BytesIO, IOBase

if sys.version_info[0] < 3:
    from __builtin__ import xrange as range
    from future_builtins import ascii, filter, hex, map, oct, zip


def main():
    n = int(input().strip())
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = [int(s) for s in input().strip().split()]
        adj[a - 1].append(b - 1)
        adj[b - 1].append(a - 1)
    
    M = 10 ** 9 + 7
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = (fact[i - 1] * i) % M
    
    def inv(x):
        return pow(x, M - 2, M)

    def comb(m, k):
        return (((fact[m] * inv(fact[k])) % M) * inv(fact[m - k])) % M

    result = [0] * n
    size = [1] * n
    low = [1] * n

    def dfs1(u, parent=-1):
        for v in adj[u]:
            if v == parent:
                continue
            dfs1(v, u)
            size[u] += size[v]
        remain = size[u] - 1
        for v in adj[u]:
            if v == parent:
                continue
            low[u] = (low[u] * comb(remain, size[v]) * low[v]) % M
            remain -= size[v]
    
    def dfs2(u, parent=-1, up=1):
        result[u] = (comb(n - 1, size[u] - 1) * low[u] * up) % M
        for v in adj[u]:
            if v == parent:
                continue
            dfs2(v, u, (result[u] * inv(comb(n - 1, size[v])) * inv(low[v])) % M)
    
    dfs1(0)
    # print(size)
    # print(low)
    dfs2(0)
    for x in result:
        print(x)


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()