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:
#!/usr/bin/env python3
import sys
import resource
sys.setrecursionlimit(2 * 10**5)
#resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))


MOD = 1000000007  # type: int

def solve(N: int, a: "List[int]", b: "List[int]"):
    ff = [1] * (N + 1)
    for i in range(1, N+1):
        ff[i] = (ff[i-1] * i) % MOD
    iff = [pow(ff[i], MOD-2, MOD) for i in range(N+1)]
    cache = {}
    def f(source, sink):
        key = (source, sink)
        if key in cache:
            return cache[key]
        c, ic, p = 0,1, 1
        for e in edges[sink]:
            if e == source:
                continue
            cc, pp = f(sink, e)
            p = (p * pp) % MOD
            c += cc
            ic = (ic * iff[cc]) % MOD
        cache[key] = c+1, p * (ff[c] * ic) % MOD
        return cache[key]

    def g(node):
        c, ic, p = 0, 1, 1
        for e in edges[node]:
            cc, pp = f(node, e)
            c += cc
            p = (p * pp) % MOD
            ic = (ic * iff[cc]) 
        return (((ff[c] * ic) % MOD) * p) % MOD
    
    edges = [[] for _ in range(N+1)]
    for aa, bb in zip(a, b):
        edges[aa].append(bb)
        edges[bb].append(aa)

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import os
import sys

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)]
memo2 = [{} for _ in range(N)]


def solve(v, p):
    if p in memo2[v]:
        return memo2[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:
            memo2[v][p] = ret, children_cnt + 1
            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
        memo2[v][p] = ret, children_cnt - cnt + 1
        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
    memo2[v][p] = ret, children_cnt + 1
    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:
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=None)
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:
import itertools
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def jaj(a,patt,i):
    j=False
    for aa in a:
#        print(str(aa)+";"+str(i))
        if patt[i]==aa[0] :
            if aa[1] in patt[0:i]:
                j=True
#    print(j)
    return j

n=ni()
a=[]
for i in range(n-1):
    a1,b1=nm()
    a.append([a1,b1])
    a.append([b1,a1])
#print(a)
all=[0]*n
for pattern in list(itertools.permutations(range(1,n+1), n)):
    j=True
    for i in range(1,n):
#        print(str(pattern)+":"+str(i))
        if not(jaj(a,pattern,i)):
            j=False
    if j:
        all[pattern[0]-1]+=1
for ans in all:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys, resource
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub


sys.setrecursionlimit(10**6)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


M = Mod(10**9 + 7)

fact_ = [1] * (2 * (10**5) + 1)
for i in range(1, 2 * (10**5)+1):
    fact_[i] = M.mul(fact_[i-1], i)


def fact(n):
    return fact_[n]




@mt
def slv(N, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    @lru_cache(maxsize=None)
    def f(u, p):
        n = 0
        r = 1
        nn = []
        for v in g[u]:
            if v == p:
                continue
            n_, r_ = f(v, u)
            r = M.mul(r, r_)
            n += n_
            nn.append(n_)

        ret = M.mul(fact(n), r)
        for i in nn:
            ret = M.div(ret, fact(i))

        return n+1, ret

    for i in range(1, N+1):
        print(f(i, 0)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))

    # N = (10**5) * 2
    # AB = [(_, _+1) for _ in range(N-1)]
    # (slv(N, AB))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys, resource
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

resource.setrlimit(resource.RLIMIT_STACK,
                   (resource.RLIM_INFINITY, resource.RLIM_INFINITY))

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class Mod:
    def __init__(self, m):
        self.m = m

    def add(self, a, b):
        return (a + b) % self.m

    def sub(self, a, b):
        return (a - b) % self.m

    def mul(self, a, b):
        return ((a % self.m) * (b % self.m)) % self.m

    def div(self, a, b):
        return self.mul(a, pow(b, self.m-2, self.m))

    def pow(self, a, b):
        return pow(a, b, self.m)


M = Mod(10**9 + 7)

fact_ = [1] * (2 * (10**5) + 1)
for i in range(1, 2 * (10**5)+1):
    fact_[i] = M.mul(fact_[i-1], i)


def fact(n):
    return fact_[n]




@mt
def slv(N, AB):
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    @lru_cache(maxsize=None)
    def f(u, p):
        n = 0
        r = 1
        nn = []
        for v in g[u]:
            if v == p:
                continue
            n_, r_ = f(v, u)
            r = M.mul(r, r_)
            n += n_
            nn.append(n_)

        ret = M.mul(fact(n), r)
        for i in nn:
            ret = M.div(ret, fact(i))

        return n+1, ret

    for i in range(1, N+1):
        print(f(i, 0)[1])


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    (slv(N, AB))

    # N = (10**5) * 2
    # AB = [(_, _+1) for _ in range(N-1)]
    # (slv(N, AB))



if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200000):
        fact.append(fact[-1]*i % mod)
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    g2 = [set(i) for i in g]
    child = [1]*n  # 子の数
    cnt = 2
    q = [-1, 0]
    while cnt > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            g2[j].remove(i)
            q.append(j)
            cnt += 1
        else:
            q.pop()
            cnt -= 1
            if cnt > 1:
                child[q[-1]] += child[i]
    rank = [(j, i) for i, j in enumerate(child)]
    rank = [j for i, j in sorted(rank)]
    dp = [1]*n
    for i in rank:
        c = child[i]
        ans = fact[c-1]
        temp = 1
        for j in g[i]:
            cj = child[j]
            if cj < c:
                ans = ans*dp[j] % mod
                temp = temp*fact[cj] % mod
        dp[i] = ans*pow(temp, mod-2, mod) % mod
    dp2 = [0]*n
    dp2[0] = dp[0]
    g2 = [set(i) for i in g]
    q = [-1, 0]
    cnt = 2
    while cnt > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            c = child[j]
            temp = fact[n-c]*fact[c-1]
            dp2[j] = dp2[i]*(fact[c]*fact[n-c-1])*pow(temp, mod-2, mod) % mod
            g2[j].remove(i)
            q.append(j)
            cnt += 1
        else:
            q.pop()
            cnt -= 1

    for i in dp2:
        print(i)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200000):
        fact.append(fact[-1]*i % mod)
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    g2 = [set(i) for i in g]
    child = [1]*n  # 子の数
    q = [-1, 0]
    while len(q) > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
            if len(q) > 1:
                child[q[-1]] += child[i]
    rank = [(j, i) for i, j in enumerate(child)]
    rank = [j for i, j in sorted(rank)]
    dp = [1]*n
    for i in rank:
        c = child[i]
        ans = fact[c-1]
        temp = 1
        for j in g[i]:
            if child[j] < c:
                ans = ans*dp[j] % mod
                temp = temp*fact[child[j]] % mod
        dp[i] = ans*pow(temp, mod-2, mod) % mod
    dp2 = [0]*n
    dp2[0] = dp[0]
    g2 = [set(i) for i in g]
    q = [-1, 0]
    while len(q) > 1:  # DFS
        i = q[-1]
        if g2[i]:
            j = g2[i].pop()
            c = child[j]
            temp = fact[n-c]*fact[c-1]
            dp2[j] = dp2[i]*(fact[c]*fact[n-c-1])*pow(temp, mod-2, mod) % mod
            g2[j].remove(i)
            q.append(j)
        else:
            q.pop()
            if len(q) > 1:
                child[q[-1]] += child[i]

    for i in dp2:
        print(i)


main()

Submission status: Time Limit Exceeded

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

n = int(input())

mod = 10**9 + 7

# def expo(x,n): # o(log n)
#     var = 1
#     while n>0:
#         if n%2 == 1:
#             var = (var*x) % mod
#         x = (x*x)%mod
#         n = n>>1
#     return var
fact = [1] * (n+10)
fact_inv = [1] * (n+10)
for i in range(1,n+10):
    fact[i] = fact[i-1] * i %mod
fact_inv[-1] = pow(fact[-1], mod-2,mod)
for i in range(1,n+10)[::-1]:
    fact_inv[i-1] = fact_inv[i]*i%mod
def conbi(*x): # o()
    num = 1
    den = 1
    # for i in range(1,sum(x)+1):
        # num = (num*i)%mod
    num = fact[sum(x)]
    for i in x:
        den = den*fact_inv[i]%mod
        # for j in range(1,i+1):
        #     den = (den * j)%mod
    return (num*den)%mod

path = [set() for _ in range(n)]
pathq= [0]*n

for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].add(b)
    pathq[a] += 1
    path[b].add(a)
    pathq[b] += 1

memo = {}
def go(i,j):
    if (i,j) in memo.keys():
        return memo[(i,j)]
    else:
        memo[(i,j)] = [1,1]
        cnt = []
        meth = 1
        for k in path[j]:
            if i != k:
                [x,y] = go(j,k)
                meth *= y
                meth %= mod
                cnt.append(x)
        memo[(i,j)] = [sum(cnt)%mod + 1, meth*conbi(*cnt)%mod]
        return memo[(i,j)]

for i in range(n):
    ans = 1
    cnt = []
    meth = 1
    for j in path[i]:
        [x,y] = go(i,j)
        meth *= y
        meth %= mod
        cnt.append(x)
    print(meth*conbi(*cnt)%mod)

Submission status: Time Limit Exceeded

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

n = int(input())

mod = 10**9 + 7

def expo(x,n): # o(log n)
    var = 1
    while n>0:
        if n%2 == 1:
            var = (var*x) % mod
        x = (x*x)%mod
        n = n>>1
    return var
fact = [1] * (n+10)
for i in range(1,n+10):
    fact[i] = fact[i-1] * i %mod
def conbi(*x): # o()
    num = 1
    den = 1
    # for i in range(1,sum(x)+1):
        # num = (num*i)%mod
    num = fact[sum(x)]
    for i in x:
        den = den*fact[i]%mod
        # for j in range(1,i+1):
        #     den = (den * j)%mod
    return (num*expo(den,mod-2))%mod

path = [set() for _ in range(n)]
pathq= [0]*n

for _ in range(n-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    path[a].add(b)
    pathq[a] += 1
    path[b].add(a)
    pathq[b] += 1

memo = {}
def go(i,j):
    if (i,j) in memo.keys():
        return memo[(i,j)]
    else:
        memo[(i,j)] = [1,1]
        cnt = []
        meth = 1
        for k in path[j]:
            if i != k:
                [x,y] = go(j,k)
                meth *= y
                meth %= mod
                cnt.append(x)
        memo[(i,j)] = [sum(cnt)%mod + 1, meth*conbi(*cnt)%mod]
        return memo[(i,j)]

for i in range(n):
    ans = 1
    cnt = []
    meth = 1
    for j in path[i]:
        [x,y] = go(i,j)
        meth *= y
        meth %= mod
        cnt.append(x)
    print(meth*conbi(*cnt)%mod)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)
mod = 10**9 + 7
factorial = [1]*(n+1)
factorial_inv = [1]*(n+1)
for i in range(1,n+1):
    factorial[i] = factorial[i-1]*i
factorial_inv[n] = pow(factorial[n],mod-2,mod)
for i in range(n,0,-1):
    factorial_inv[i-1] = factorial_inv[i]*i%mod

for i in range(1,n+1):
    ch = [[] for _ in range(n+1)]
    pa = [0]*(n+1)
    dp = [[1,1] for _ in range(n+1)]
    checked = []
    stack = [i]
    stack2 = []
    while stack:
        a = stack.pop()
        checked.append(a)
        if a != i and len(graph[a]) == 1:
            stack2.append(a)
        else:
            for j in graph[a]:
                if j in checked:
                    continue
                else:
                    checked.append(j)
                    stack.append(j)
                    pa[j] = a
                    ch[a].append(j)
    checked = []
    while stack2:
        a = stack2.pop()
        if a == i:
            print(dp[i][0])
            break
        else:
            p = pa[a]
            dp[p][0] *= dp[a][0]*factorial_inv[dp[a][1]]
            dp[p][0] %= mod
            dp[p][1] += dp[a][1]
            ch[p].remove(a)
            if len(ch[p]) == 0:
                dp[p][0] *= factorial[dp[p][1]-1]
                dp[p][0] %= mod
                stack2.append(p)
            checked.append(a)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
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
    if x0 < 0:
        x0 += M
    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)

rs_memo = [None] * n
v_memo = [None] * n
def count(i, last):
    rs = []
    for n in g[i]:
        if n != last:
            rs.append(count(n, i))
    rs_memo[i] = rs
    if len(rs) == 0:
        v_memo[i] = (1, 1, i)
        return (1, 1, i)
    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]
    v_memo[i] = (r, allsz, i)
    return (r, allsz, i)

def visit(i, last, top, ret):
    rs = rs_memo[i]
    if len(rs) == 0:
        ret[i] = top[0]
        return
    allr, allsz, j = v_memo[i]
    ret[i] = comb(n - 1, top[1]) * top[0] * allr % M
    for v in rs:
        r = comb(n - v[1] - 1, top[1]) * top[0] * allr * inv(comb(allsz - 1,  v[1]), M) * inv(v[0], M) % M
        sz = n - v[1]
        visit(v[2], i, (r, sz), ret)
    return
    
count(0, -1)
ret = [0] * n
visit(0, -1, (1, 0), ret)
for r in ret:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
# 解説動画の通り
import sys

# grobalにmdを設定すること
class mint:
    def __init__(self, x):
        self.__x = x % md

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

    def __neg__(self):
        return mint(-self.__x)

    def __add__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x + other)

    def __sub__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x - other)

    def __rsub__(self, other):
        return mint(other - self.__x)

    def __mul__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * other)

    __radd__ = __add__
    __rmul__ = __mul__

    def __truediv__(self, other):
        if isinstance(other, mint): other = other.__x
        return mint(self.__x * pow(other, md - 2, md))

    def __rtruediv__(self, other):
        return mint(other * pow(self.__x, md - 2, md))

    def __pow__(self, power, modulo=None):
        return mint(pow(self.__x, power, md))

md = 10 ** 9 + 7

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def nCr(com_n, com_r):
    if com_n < com_r: return 0
    return fac[com_n] * ifac[com_r] * ifac[com_n - com_r]

n_max = 200005
fac = [mint(1)]
for i in range(1, n_max + 1): fac.append(fac[-1] * i)
ifac = [mint(1)] * (n_max + 1)
ifac[n_max] /= fac[n_max]
for i in range(n_max - 1, 1, -1): ifac[i] = ifac[i + 1] * (i + 1)

class SubTree:
    # vが場合の数、sが頂点数（根を除く）
    def __init__(self, v, s):
        self.v = v
        self.s = s

    def __add__(self, other):
        t = other.s + 1
        v = self.v * other.v * nCr(self.s + t, t)
        s = self.s + t
        return SubTree(v, s)

    def __sub__(self, other):
        t = other.s + 1
        s = self.s - t
        v = self.v / (other.v * nCr(self.s, t))
        return SubTree(v, s)

def main():
    def dfs1(u=0, pu=-1):
        for v in to[u]:
            if v == pu: continue
            dfs1(v, u)
            dp[u] += dp[v]

    def dfs2(u=0, pu=-1):
        dpu = dp[u]
        for v in to[u]:
            if v == pu: continue
            dp[v] += dpu - dp[v]
            dfs2(v, u)

    n = II()
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = MI1()
        to[a].append(b)
        to[b].append(a)
    dp = [SubTree(mint(1),0) for _ in range(n)]
    dfs1()
    dfs2()
    for a in dp: print(a.v)

main()

Submission status: Time Limit Exceeded

Solution code:
def main():  
  from collections import deque
  N = int(input())
  ab = [list(map(int,input().split())) for _ in range(N-1)]
  mod = 10**9+7
  fact = [1]*(N+1)
  fact_inv = [1]*(N+1)
  for i in range(1,N+1):
    fact[i] = (fact[i-1]*i)%mod
    fact_inv[i] = pow(fact[i], mod-2, mod)

  g = [deque([]) for _ in range(N+1)]
  for a,b in ab:
    g[a].append(b)
    g[b].append(a)

  parents = [0]*(N+1)
  q = deque([])
  s = deque([1])
  while s:
    x = s.pop()
    q.append(x)
    for y in g[x]:
      if y==parents[x]:
        continue
      else:
        parents[y] = x
        s.append(y)

  q = list(q)
  size_forward = [0]*(N+1)
  dp_forward = [1]*(N+1)
  for i in q[::-1]:
    p = parents[i]
    s = size_forward[i] + 1
    size_forward[p] += s
    dp_forward[i] *= fact[size_forward[i]]
    dp_forward[p] *= dp_forward[i] * fact_inv[s]
    dp_forward[p] %= mod

  size_back = [N-1-i for i in size_forward]
  dp_back = [1]*(N+1)
  for i in q[1:]:
    p = parents[i]
    x = dp_back[p]
    x *= fact_inv[size_back[p]]
    x *= dp_forward[p]
    x *= fact_inv[size_forward[p]]
    x *= fact[size_forward[i]+1]
    x *= pow(dp_forward[i],mod-2,mod)
    x *= fact[size_back[i]-1]
    dp_back[i] = x % mod

  for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
    ans = b * d * fact[a+c] * fact_inv[a] * fact_inv[c]
    ans %= mod
    print(ans)
    
main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N = int(input())
ab = [list(map(int,input().split())) for _ in range(N-1)]
mod = 10**9+7
fact = [1]*(N+1)
fact_inv = [1]*(N+1)
for i in range(1,N+1):
  fact[i] = (fact[i-1]*i)%mod
  fact_inv[i] = pow(fact[i], mod-2, mod)

g = [deque([]) for _ in range(N+1)]
for a,b in ab:
  g[a].append(b)
  g[b].append(a)
  
parents = [0]*(N+1)
q = deque([])
s = deque([1])
while s:
  x = s.pop()
  q.append(x)
  for y in g[x]:
    if y==parents[x]:
      continue
    else:
      parents[y] = x
      s.append(y)
      
q = list(q)
size_forward = [0]*(N+1)
dp_forward = [1]*(N+1)
for i in q[::-1]:
  p = parents[i]
  s = size_forward[i] + 1
  size_forward[p] += s
  dp_forward[i] *= fact[size_forward[i]]
  dp_forward[p] *= dp_forward[i] * fact_inv[s]
  dp_forward[p] %= mod
  
size_back = [N-1-i for i in size_forward]
dp_back = [1]*(N+1)
for i in q[1:]:
  p = parents[i]
  x = dp_back[p]
  x *= fact_inv[size_back[p]]
  x *= dp_forward[p]
  x *= fact_inv[size_forward[p]]
  x *= fact[size_forward[i]+1]
  x *= pow(dp_forward[i],mod-2,mod)
  x *= fact[size_back[i]-1]
  dp_back[i] = x % mod
  
for a,b,c,d in zip(size_forward[1:], dp_forward[1:], size_back[1:], dp_back[1:]):
  ans = b * d * fact[a+c] * fact_inv[a] * fact_inv[c]
  ans %= mod
  print(ans)