Problem: 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).

Submission attempts (in order):
def main():
    from sys import stdin
    input=stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    for a, b in ab:
        g[a-1].add(b-1)
        g[b-1].add(a-1)

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    def rerooting(tree, ini):
        
        def __init__(self, tree, ini):
            
            
            
            
            def merge(a, b): return a * b % mod
            def adj_bu(a, i): return a * inv[size[i]] % mod
            def adj_td(a, i, p): return a * inv[n-size[i]] % mod
            def adj_fin(a, i): return a * fact[n-1] % mod

            
            
            
            
            
            T = g
            P = [-1]*n
            q = [0]
            order = []
            while q:
                i = q.pop()
                order.append(i)
                for a in T[i]:
                    if a != P[i]:
                        P[a] = i
                        T[a].remove(i)
                        q.append(a)

            
            T = [list(i) for i in T]

            
            
            size = [1]*n
            for i in order[1:][::-1]:
                size[P[i]] += size[i]

            
            
            
            ME = [ini]*n
            DP = [0]*n
            for i in order[1:][::-1]:
                DP[i] = adj_bu(ME[i], i)
                p = P[i]
                ME[p] = merge(ME[p], DP[i])
            DP[order[0]] = adj_fin(ME[order[0]], order[0])
            TD = [ini]*n

            
            for i in order:
                
                ac = TD[i]
                for j in T[i]:
                    TD[j] = ac
                    ac = merge(ac, DP[j])
                
                ac = ini
                for j in T[i][::-1]:
                    TD[j] = adj_td(merge(TD[j], ac), j, i)
                    ac = merge(ac, DP[j])
                    DP[j] = adj_fin(merge(ME[j], TD[j]), j)
            for i in DP:
                print(i)

    rerooting(g, 1)


main()

def main():
    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]
    mod = 10**9+7
    fact = [1, 1]
    for i in range(2, 200001):
        fact.append(fact[-1]*i % mod)

    def nCr(n, r, mod=10**9+7):
        return pow(fact[n-r]*fact[r], mod-2, mod)*fact[n] % mod

    class rerooting():
        
        def __init__(self, tree, ini):
            
            def add(i, j, x):
                return x+1

            def monoid(i, j):
                return i+j

            def monoid2(i, j):
                return i*j % mod

            def calc(i, j):
                root = tree_d[i][j]+1
                try:
                    return monoid(tc_l[i][root-1], tc_r[i][root])
                except:
                    return tc_l[i][root-1]

            def calc2(i, j):
                root = tree_d[i][j]+1
                try:
                    return monoid2(tc_l2[i][root-1], tc_r2[i][root]) *\
                        nCr(tc_l[i][root-1]+tc_r[i][root], tc_l[i][root-1])
                except:
                    return tc_l2[i][root-1]

            size = len(tree)
            dp, dp2, order, q, anc = [ini]*size, [1]*size, [], [0], [-1]*n
            oa, qa, qp = order.append, q.append, q.pop
            tree_d = [{k: j for j, k in enumerate(i)} for i in g]
            g_size = [len(i) for i in g]
            tc_l = [[ini]*(i+1) for i in g_size]
            tc_r = [[ini]*i for i in g_size]
            tc_l2 = [[1]*(i+1) for i in g_size]
            tc_r2 = [[1]*i for i in g_size]

            
            while q:
                i = qp()
                a = anc[i]
                oa(i)
                for j in g[i]:
                    if j != a:
                        qa(j)
                        anc[j] = i

            
            for i in order[:0:-1]:
                a = anc[i]
                t = tree_d[a][i]
                d = dp2[i]
                tc_l2[a][t+1], tc_r2[a][t] = d, d
                d = add(a, i, dp[i])
                tc_l[a][t+1], tc_r[a][t], dp[a] = d, d, monoid(dp[a], d)
                dp2[a] = dp2[a]*dp2[i]*nCr(dp[a], dp[i]+1) % mod

            
            for j in range(1, g_size[0]+1):
                tc_l[0][j] = monoid(tc_l[0][j], tc_l[0][j-1])
                tc_l2[0][j] = tc_l2[0][j]*tc_l2[0][j-1] * \
                    nCr(tc_l[0][j], tc_l[0][j-1]) % mod
            for j in range(g_size[0]-1, 0, -1):
                tc_r[0][j] = monoid(tc_r[0][j], tc_r[0][j+1])
                tc_r2[0][j] = tc_r2[0][j]*tc_r2[0][j+1] * \
                    nCr(tc_r[0][j], tc_r[0][j+1]) % mod

            
            for i in order[1:]:
                a = anc[i]
                d, c, c2, length = tree_d[i][a], add(
                    a, i, calc(a, i)), calc2(a, i), g_size[i]

                tc_l[i][d+1], tc_r[i][d] = c, c
                tc_l2[i][d+1], tc_r2[i][d] = c2, c2

                for j in range(1, length+1):
                    tc_l[i][j] = monoid(tc_l[i][j], tc_l[i][j-1])
                    tc_l2[i][j] = tc_l2[i][j]*tc_l2[i][j-1] * \
                        nCr(tc_l[i][j], tc_l[i][j-1]) % mod
                for j in range(length-2, 0, -1):
                    tc_r[i][j] = monoid(tc_r[i][j+1], tc_r[i][j])
                    tc_r2[i][j] = tc_r2[i][j]*tc_r2[i][j+1] * \
                        nCr(tc_r[i][j], tc_r[i][j+1]) % mod
                dp[i] = tc_l[i][-1]
                dp2[i] = tc_l2[i][-1]

            
            for i in dp2:
                print(i)

    rerooting(g, 0)


main()


def main():
    from sys import stdin
    input = stdin.readline
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    for a, b in ab:
        g[a-1].add(b-1)
        g[b-1].add(a-1)

    mod = 10**9+7
    fact = [1, 1]
    inv = [pow(i, mod-2, mod) for i in range(n+1)]
    for i in range(2, n+1):
        fact.append(fact[-1]*i % mod)

    class rerooting():
        
        def __init__(self, tree, ini):
            
            
            
            
            def merge(a, b): return a * b % mod
            def adj_bu(a, i): return a * inv[size[i]] % mod
            def adj_td(a, i, p): return a * inv[n-size[i]] % mod
            def adj_fin(a, i): return a * fact[n-1] % mod

            
            
            
            
            
            T = g
            P = [-1]*n
            q = [0]
            order = []
            while q:
                i = q.pop()
                order.append(i)
                for a in T[i]:
                    if a != P[i]:
                        P[a] = i
                        T[a].remove(i)
                        q.append(a)

            
            T = [list(i) for i in T]

            
            
            size = [1]*n
            for i in order[1:][::-1]:
                size[P[i]] += size[i]

            
            
            
            ME = [ini]*n
            DP = [0]*n
            for i in order[1:][::-1]:
                DP[i] = adj_bu(ME[i], i)
                p = P[i]
                ME[p] = merge(ME[p], DP[i])
            DP[order[0]] = adj_fin(ME[order[0]], order[0])
            TD = [ini]*n

            
            for i in order:
                
                ac = TD[i]
                for j in T[i]:
                    TD[j] = ac
                    ac = merge(ac, DP[j])
                
                ac = ini
                for j in T[i][::-1]:
                    TD[j] = adj_td(merge(TD[j], ac), j, i)
                    ac = merge(ac, DP[j])
                    DP[j] = adj_fin(merge(ME[j], TD[j]), j)
            for i in DP:
                print(i)

    rerooting(g, 1)


main()


Verdicts: Wrong Answer

Runtime Error

Accepted