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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
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, chain,
                       permutations, product)
from operator import add, mul, sub

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


class ModOperation:

    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))


MOD = 10**9 + 7
mod = ModOperation(MOD)

fact = [1] * (2 * (10**5) + 1)
fact_inv = [0] * (2 * (10**5) + 1)

for i in range(1, 2 * (10**5)+1):
    fact[i] = mod.mul(fact[i-1], i)
    fact_inv[i] = pow(fact[i], MOD-2, MOD)


def solve(g):
    def dfs(pre, cur):
        if (pre, cur) in memo:
            return memo[pre, cur]

        num, ways = 1, 1

        for nxt in g[cur]:
            if nxt == pre:
                continue
            n, w = dfs(cur, nxt)
            num += n
            ways = m.mul(ways, m.mul(w, fi[n]))

        ways = m.mul(ways, f[num-1])
        memo[pre, cur] = num, ways
        return num, ways

    m = mod
    memo = {}
    f, fi = fact, fact_inv

    for i in range(1, len(g)):
        print(dfs(None, i)[1])

    # print(memo)

def main():
    n = int(input())
    g = [[] for _ in range(n+1)]

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

    solve(g)

if __name__ == "__main__":

    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import 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 * b) % self.m

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

    @lru_cache(maxsize=None)
    def pow(self, a, b):
        return pow(a, b, self.m)


M = Mod(10**9 + 7)
m = 10**9 + 7
fact = [1] * (2 * (10**5) + 1)
fact_inv = [0] * (2 * (10**5) + 1)
for i in range(1, 2 * (10**5)+1):
    fact[i] = M.mul(fact[i-1], i)
    fact_inv[i] = pow(fact[i], m-2, m)


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

    memo = defaultdict(dict)

    def f(u, p, flag=False):
        if u in memo and p in memo[u]:
            return memo[u][p]
        r = 1
        n = 1
        if p == 0 or flag:
            for v in g[u]:
                if v == p:
                    continue
                n_, r_ = f(v, u, flag)
                n += n_
                r = M.mul(r, r_)
                r = M.mul(r, fact_inv[n_])
            r = M.mul(r, fact[n-1])
        else:
            np, rp = f(p, u, False)
            na, ra = f(u, 0, False)
            r = M.div(ra, rp)
            r = M.mul(r, fact[np])
            n = na - np
            r = M.mul(r, fact_inv[na-1])
            r = M.mul(r, fact[n-1])

        # memo[(u, p)] = n, r
        memo[u][p] = n, r
        return n, r

    f(1, 0, True)

    for i in range(1, N+1):
        print(f(i, 0, False)[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
import 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 * b) % self.m

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

    @lru_cache(maxsize=None)
    def pow(self, a, b):
        return pow(a, b, self.m)


M = Mod(10**9 + 7)
m = 10**9 + 7
fact = [1] * (2 * (10**5) + 1)
fact_inv = [0] * (2 * (10**5) + 1)
for i in range(1, 2 * (10**5)+1):
    fact[i] = M.mul(fact[i-1], i)
    fact_inv[i] = pow(fact[i], m-2, m)


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

    memo = {}

    def f(u, p, flag=False):
        if (u, p) in memo:
            return memo[(u, p)]
        r = 1
        n = 1
        if p == 0 or flag:
            for v in g[u]:
                if v == p:
                    continue
                n_, r_ = f(v, u, flag)
                n += n_
                r = M.mul(r, r_)
                r = M.mul(r, fact_inv[n_])
            r = M.mul(r, fact[n-1])
        else:
            np, rp = f(p, u, False)
            na, ra = f(u, 0, False)
            r = M.div(ra, rp)
            r = M.mul(r, fact[np])
            n = na - np
            r = M.mul(r, fact_inv[na-1])
            r = M.mul(r, fact[n-1])

        memo[(u, p)] = n, r
        return n, r

    f(1, 0, True)

    for i in range(1, N+1):
        print(f(i, 0, False)[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
import 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 * b) % self.m

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

    @lru_cache(maxsize=None)
    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)


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

    memo = {}
    def f(u, p, flag=False):
        if (u, p) in memo:
            return memo[(u, p)]
        r = 1
        n =1
        if p == 0 or flag:
            for v in g[u]:
                if v == p:
                    continue
                n_, r_ = f(v, u, flag)
                n += n_
                r = M.mul(r, r_)
                r = M.div(r, fact[n_])
            r = M.mul(r, fact[n-1])
        else:
            np, rp = f(p, u, False)
            na, ra = f(u, 0, False)
            r = M.div(ra, rp)
            r = M.mul(r, fact[np])
            n = na - np
            r = M.div(r, fact[na-1])
            r = M.mul(r, fact[n-1])

        memo[(u, p)] = n, r
        return n, r

    f(1, 0, True)

    for i in range(1, N+1):
        print(f(i, 0, False)[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
import 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)


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

    memo = {}
    def f(u, p, flag=False):
        if (u, p) in memo:
            return memo[(u, p)]
        r = 1
        n =1
        if p == 0 or flag:
            for v in g[u]:
                if v == p:
                    continue
                n_, r_ = f(v, u, flag)
                n += n_
                r = M.mul(r, r_)
                r = M.div(r, fact[n_])
            r = M.mul(r, fact[n-1])
        else:
            np, rp = f(p, u, False)
            na, ra = f(u, 0, False)
            r = M.div(ra, rp)
            r = M.mul(r, fact[np])
            n = na - np
            r = M.div(r, fact[na-1])
            r = M.mul(r, fact[n-1])

        memo[(u, p)] = n, r
        return n, r

    f(1, 0, True)
    # for k, v in memo.items():
    #     print(k, v)

    for i in range(1, N+1):
        print(f(i, 0, False)[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
import 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)


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

    memo = {}
    def f(u, p, flag=False):
        if (u, p) in memo:
            return memo[(u, p)]
        r = 1
        n =1
        if p == 0 or flag:
            for v in g[u]:
                if v == p:
                    continue
                n_, r_ = f(v, u, flag)
                n += n_
                r = M.mul(r, r_)
                r = M.div(r, fact[n_])
            r = M.mul(r, fact[n-1])
        else:
            np, rp = f(p, u, False)
            na, ra = f(u, 0, False)
            r = M.div(ra, rp)
            r = M.mul(r, fact[np])
            n = na - np
            r = M.div(r, fact[na-1])
            r = M.mul(r, fact[n-1])

        memo[(u, p)] = n, r
        return n, r

    f(1, 0, True)
    # for k, v in memo.items():
    #     print(k, v)

    for i in range(1, N+1):
        print(f(i, 0, False)[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:
MOD = 10**9 + 7
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict,deque
N = int(input())

g = defaultdict(list)

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

n = 200010
fact = [1]*(n+1)
inv = [1]*(n+1)
inv = [pow(i,MOD-2,MOD) for i in range(n+1)]
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = (fact[i-1]*i) % MOD
    ifact[i] = (ifact[i-1]*inv[i]) % MOD

dp = [[-1 for p in range(N+1)] for v in range(N+1)]
size = [[-1 for p in range(N+1)] for v in range(N+1)]

def tree(v,p,first=False):
    if dp[v][p] != -1:
        return dp[v][p]
    ds = []
    ls = []
    for nv in g[v]:
        if nv == p:
            continue
        ds.append(tree(nv,v,True))
        ls.append(size[nv][v])
    size[v][p] = sum(ls) + 1
    dp[v][p] = fact[size[v][p]-1]
    for d,l in zip(ds,ls):
        dp[v][p] *= d*ifact[l]
        dp[v][p] %= MOD
    return dp[v][p]

tree(1,0)

dq = deque([(1,0)])
while dq:
    v,p = dq.popleft()
    for nv in g[v]:
        if nv == p:
            continue
        size[v][nv] = N - size[nv][v]
        dp[nv][0] = (dp[v][0] *inv[size[v][nv]]  * size[nv][v]) % MOD
        dq.append((nv,v))

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
import 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)

    memo = {}
    def f(u, p, flag=False):
        if (u, p) in memo:
            return memo[(u, p)]
        r = 1
        n =1
        if p == 0 or flag:
            for v in g[u]:
                if v == p:
                    continue
                n_, r_ = f(v, u, flag)
                n += n_
                r = M.mul(r, r_)
                r = M.div(r, fact(n_))
            r = M.mul(r, fact(n-1))
        else:
            np, rp = f(p, u, False)
            na, ra = f(u, 0, False)
            r = M.div(ra, rp)
            r = mul(r, fact(np))
            n = na - np
            r = M.div(r, fact(na-1))
            r = M.mul(r, fact(n-1))

        memo[(u, p)] = n, r
        return n, r

    f(1, 0, True)
    # for k, v in memo.items():
    #     print(k, v)

    for i in range(1, N+1):
        print(f(i, 0, False)[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:
MOD = 10**9 + 7
from collections import defaultdict,deque
N = int(input())

g = defaultdict(list)

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

n = 200010
fact = [1]*(n+1)
inv = [1]*(n+1)
ifact = [1]*(n+1)
for i in range(1,n+1):
    fact[i] = (fact[i-1]*i) % MOD
    inv[i] = pow(i,MOD-2,MOD)
    ifact[i] = (ifact[i-1]*inv[i]) % MOD

dp = [[-1 for p in range(N+1)] for v in range(N+1)]
size = [[-1 for p in range(N+1)] for v in range(N+1)]

def tree(v,p):
    if dp[v][p] != -1:
        return dp[v][p]
    ds = []
    ls = []
    for nv in g[v]:
        if nv == p:
            continue
        ds.append(tree(nv,v))
        ls.append(size[nv][v])
    size[v][p] = sum(ls) + 1
    dp[v][p] = fact[size[v][p]-1]
    for d,l in zip(ds,ls):
        dp[v][p] *= d
        dp[v][p] %= MOD
        dp[v][p] *= ifact[l]
        dp[v][p] %= MOD
    return dp[v][p]

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    mod = 10**9+7
    
    fact = [1,1]
    finv = [1,1]
    inv = [0,1]
    
    for i in range(2,2*10**5+5):
        fact.append((fact[-1]*i)%mod)
        inv.append((inv[mod%i]*(mod-mod//i))%mod)
        finv.append((finv[-1]*inv[-1])%mod)
    
    def nCr(n,r,mod):
        
        return fact[n]*finv[r]*finv[n-r]%mod

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

    numl = [0]*n
    resl = [0]*n
    def dfs(x,pre):
        num = 0
        res = 1
        for nex in e[x]:
            if nex == pre:
                continue
            dfs(nex,x)
            num += numl[nex]
            res *= nCr(num,numl[nex],mod)*resl[nex]
            res %= mod
        numl[x] = num+1
        resl[x] = res

        return 

    dfs(0,-1)

    ans = [0]*n
    ans[0] = resl[0]
    def dfs2(x,pre):
        
        for nex in e[x]:
            if nex == pre:
                continue
            pres = [resl[x], numl[x], resl[nex], numl[nex]]
            resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
            resl[x] %= mod
            numl[x] -= numl[nex]
            resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
            resl[nex] %= mod
            numl[nex] += numl[x]
            ans[nex] = resl[nex]
            dfs2(nex,x)
            resl[x], numl[x], resl[nex], numl[nex] = pres
        return
    dfs2(0,-1)
    for i in ans:
        print(i)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**6)
    mod = 10**9+7
    
    fact = [1,1]
    finv = [1,1]
    inv = [0,1]
    
    for i in range(2,2*10**5+5):
        fact.append((fact[-1]*i)%mod)
        inv.append((inv[mod%i]*(mod-mod//i))%mod)
        finv.append((finv[-1]*inv[-1])%mod)
    
    def nCr(n,r,mod):
        
        return fact[n]*finv[r]*finv[n-r]%mod

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

    numl = [0]*n
    resl = [0]*n
    def dfs(x,pre):
        num = 0
        res = 1
        for nex in e[x]:
            if nex == pre:
                continue
            dfs(nex,x)
            num += numl[nex]
            res *= nCr(num,numl[nex],mod)*resl[nex]
            res %= mod
        numl[x] = num+1
        resl[x] = res

        return 

    dfs(0,-1)

    ans = [0]*n
    ans[0] = resl[0]
    def dfs2(x,pre):
        
        for nex in e[x]:
            if nex == pre:
                continue
            pres = [resl[x], numl[x], resl[nex], numl[nex]]
            resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
            resl[x] %= mod
            numl[x] -= numl[nex]
            resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
            resl[nex] %= mod
            numl[nex] += numl[x]
            ans[nex] = resl[nex]
            dfs2(nex,x)
            resl[x], numl[x], resl[nex], numl[nex] = pres
        return
    dfs2(0,-1)
    print(*ans,sep="\n")
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
MOD = 10 ** 9 + 7
MAX_N = 2 * 10 ** 5

fact = [1] * (MAX_N + 1)
inverse = [1] * (MAX_N + 1)
inv_fact = [1] * (MAX_N + 1)
for i in range(2, MAX_N + 1):
  fact[i] = fact[i-1] * i % MOD
  inverse[i] = -inverse[MOD % i] * (MOD // i) % MOD
  inv_fact[i] = inv_fact[i-1] * inverse[i] % MOD

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

for root in range(n):
  stack = [root]
  parent = [root] * n
  route = []
  while stack:
    vertex = stack.pop()
    route.append(vertex)
    for child in edge[vertex]:
      if parent[vertex] != child:
        parent[child] = vertex
        stack.append(child)

  dp = [1] * n
  size = [1] * n
  for vertex in route[:0:-1]:
    pa = parent[vertex]
    sz = size[vertex]
    dp[vertex] = dp[vertex] * fact[sz-1] % MOD
    dp[pa] = dp[pa] * dp[vertex] * inv_fact[sz] % MOD
    size[pa] += sz
  print(dp[root] * fact[size[root] - 1] % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
mod = 10**9+7
 
fact = [1,1]
finv = [1,1]
inv = [0,1]
 
for i in range(2,2*10**5+5):
    fact.append((fact[-1]*i)%mod)
    inv.append((inv[mod%i]*(mod-mod//i))%mod)
    finv.append((finv[-1]*inv[-1])%mod)
 
def nCr(n,r,mod):
      
    return fact[n]*finv[r]*finv[n-r]%mod

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

numl = [0]*n
resl = [0]*n
def dfs(x,pre):
    num = 0
    res = 1
    for nex in e[x]:
        if nex == pre:
            continue
        dfs(nex,x)
        num += numl[nex]
        res *= nCr(num,numl[nex],mod)*resl[nex]
        res %= mod
    numl[x] = num+1
    resl[x] = res

    return 

dfs(0,-1)

ans = [0]*n
ans[0] = resl[0]
def dfs2(x,pre):
    
    for nex in e[x]:
        if nex == pre:
            continue
        pres = [resl[x], numl[x], resl[nex], numl[nex]]
        resl[x] *= pow(nCr(numl[x]-1,numl[nex],mod)*resl[nex],mod-2,mod)
        resl[x] %= mod
        numl[x] -= numl[nex]
        resl[nex] *=  nCr(numl[x]+numl[nex]-1,numl[x],mod)*resl[x]
        resl[nex] %= mod
        numl[nex] += numl[x]
        ans[nex] = resl[nex]
        dfs2(nex,x)
        resl[x], numl[x], resl[nex], numl[nex] = pres
    return
dfs2(0,-1)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

MOD = 1000000007
def modpow(a, b):
    if b == 0:
       return 1
    if b % 2 == 0:
       d = modpow(a, b / 2)
       return (d ** 2) % MOD
    d = modpow(a, b - 1)
    return (a * d) % MOD


M = 2*10**5 + 10
fact = [1] * M
ifact = [1] * M
for i in range(2, M):
    fact[i] = (fact[i - 1] * i) % MOD
ifact[M - 1] = modpow(fact[M - 1], MOD - 2)
for i in range(2, M - 1)[::-1]:
    ifact[i] = (ifact[i + 1] * (i + 1)) % MOD


def comb(n, k):
    if n < 0 or k > n:
        return 0
    return (((fact[n] * ifact[k]) % MOD) * ifact[n - k]) % MOD


class DP:
    def __init__(self, dp = 1, size = 0):    
        self.dp = dp
        self.size = size

    def __add__(self, other):
        dp = self.dp
        dp *= other.dp
        dp %= MOD
        size = self.size + other.size
        dp *= comb(size, self.size)
        dp %= MOD
        return DP(dp, size)

    def __sub__(self, other):
        size = self.size - other.size
        dp = self.dp
        dp *= modpow(comb(self.size, size), MOD - 2)
        dp %= MOD
        dp *= modpow(other.dp, MOD - 2)
        dp %= MOD
        return DP(dp, size)

    def addRoot(self):
        return DP(self.dp, self.size + 1)


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


dp = [DP() for _ in range(N)]
def dfs(v, p = -1):
    for c in e[v]:
        if c == p:
            continue
        dfs(c, v)
        dp[v] += dp[c].addRoot()


def dfs2(v, p = -1):
    for c in e[v]:
        if c == p:
            continue
        d = dp[v] - dp[c].addRoot()
        dp[c] += d.addRoot()
        dfs2(c, v)


dfs(0)
dfs2(0)
for d in dp:
    print(d.dp)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(200000)

n = int(input())
an= []
for i in range(0,n+1):
    an.append([])
for i in range(0,n-1):
    tmp1,tmp2 = list(map(int, input().split()))
    an[tmp1].append(tmp2)
    an[tmp2].append(tmp1)

def calcCount(used,canUse):
    global an
    if len(canUse) == 0:
        return 1

    ret = 0
    for use in canUse:
        used2 = used[:]
        canUse2 = canUse[:]
        used2.append(use)
        canUse2 = canUse2 + an[use]
        canUse2 = list(set(canUse2))
        for tmp in used2:
            try:
                canUse2.remove(tmp)
            except:
                pass

        ret += calcCount(used2, canUse2)
    return ret

for k in range(1,n+1):
    used =[k]
    canUse = an[k]
    print(calcCount(used, canUse))