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:
class treedp_rerooting():
    def __init__(self, N, V, MOD):
        self.N = N
        self.V = V
        self.mod = MOD
        self.rep = [0] * N
        self.children = [-1] * N
        self.A = [0] * N
        self.C = combination(N, MOD)
        return

    # 子の数のカウント
    def dfs(self, s):
        size = 1
        nowchild = []
        cur = 1
        self.children[s] = 0
        for i in self.V[s]:
            if self.children[i] != -1:
                continue
            ns, nc = self.dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= self.mod
        self.children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= self.C.comb(rest, k)
            rest -= k
            cur %= self.mod
        self.A[s] = cur
        return size, cur

    def dfs2(self, s, p=-1):
        cur = 1
        rest = self.N - 1
        for to in self.V[s]:
            cur *= self.A[to]
            cur %= mod
        for to in self.V[s]:
            cur *= self.C.comb(rest, children[to])
            rest -= self.children[to]
            cur %= self.mod
        self.rep[s] = rep

        n = len(V[s])
        L = [0] * self.N; R = [0] * self.N
        L2 = [0] * self.N; R2 = [0] * self.N

        for i, ne in enumerate(self.V[s]):
            L[i] = R[i] = self.A[ne] * self.C.inv[self.children[ne]] % self.mod
            L2[i] = R2[i] = self.children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= self.mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= self.mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(self.V[s]):
            if ne == p:
                continue
            self.A[s] = 1
            self.children[s] = 1
            if i > 0:
                self.A[s] *= L[i - 1]
                self.A[s] %= self.mod
                self.children[s] += L2[i - 1]
            if i + 1 < n:
                self.A[s] *= R[i + 1]
                self.A[s] %= self.mod
                self.children[s] += R2[i + 1]
            self.A[s] *= self.C.fac[self.N - self.children[ne] - 1]
            self.A[s] %= self.mod
            self.dfs2(ne, s)
        return

class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

def ABC160():
    N = I()
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    dp_r = treedp_rerooting(N,V,mod)
    dp_r.dfs(0)
    dp_r.dfs2(0)

    ans = dp_r.rep

    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160()

"""
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
"""

# 40
# 280
# 840
# 120
# 120
# 504
# 72
# 72

Submission status: Runtime Error

Solution code:
class treedp_rerooting():
    def __init__(self, N, V, MOD):
        self.N = N
        self.V = V
        self.mod = MOD
        self.rep = [0] * N
        self.children = [-1] * N
        self.A = [0] * N
        self.C = combination(N, MOD)
        return

    # 子の数のカウント
    def dfs(self, s):
        size = 1
        nowchild = []
        cur = 1
        self.children[s] = 0
        for i in self.V[s]:
            if self.children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= self.mod
        self.children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= self.C.comb(rest, k)
            rest -= k
            cur %= self.mod
        self.A[s] = cur
        return size, cur

    def dfs2(self, s, p=-1):
        cur = 1
        rest = self.N - 1
        for to in self.V[s]:
            cur *= self.A[to]
            cur %= mod
        for to in self.V[s]:
            cur *= self.C.comb(rest, children[to])
            rest -= self.children[to]
            cur %= self.mod
        self.rep[s] = rep

        n = len(V[s])
        L = [0] * self.N; R = [0] * self.N
        L2 = [0] * self.N; R2 = [0] * self.N

        for i, ne in enumerate(self.V[s]):
            L[i] = R[i] = self.A[ne] * self.C.inv[self.children[ne]] % self.mod
            L2[i] = R2[i] = self.children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= self.mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= self.mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(self.V[s]):
            if ne == p:
                continue
            self.A[s] = 1
            self.children[s] = 1
            if i > 0:
                self.A[s] *= L[i - 1]
                self.A[s] %= self.mod
                self.children[s] += L2[i - 1]
            if i + 1 < n:
                self.A[s] *= R[i + 1]
                self.A[s] %= self.mod
                self.children[s] += R2[i + 1]
            self.A[s] *= self.C.fac[self.N - self.children[ne] - 1]
            self.A[s] %= self.mod
            dfs2(ne, s)
        return

class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

def ABC160():
    N = I()
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    dp_r = treedp_rerooting(N,V,mod)
    dp_r.dfs(0)
    return
    dp_r.dfs2(0)

    ans = dp_r.rep

    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160()

"""
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
"""

# 40
# 280
# 840
# 120
# 120
# 504
# 72
# 72

Submission status: Runtime Error

Solution code:
class treedp_rerooting():
    def __init__(self, N, V, MOD):
        self.N = N
        self.V = V
        self.mod = MOD
        self.rep = [0] * N
        self.children = [-1] * N
        self.A = [0] * N
        self.C = combination(N, MOD)
        return

    # 子の数のカウント
    def dfs(self, s):
        size = 1
        nowchild = []
        cur = 1
        self.children[s] = 0
        for i in self.V[s]:
            if self.children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= self.mod
        self.children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= self.C.comb(rest, k)
            rest -= k
            cur %= self.mod
        self.A[s] = cur
        return size, cur

    def dfs2(self, s, p=-1):
        cur = 1
        rest = self.N - 1
        for to in self.V[s]:
            cur *= self.A[to]
            cur %= mod
        for to in self.V[s]:
            cur *= self.C.comb(rest, children[to])
            rest -= self.children[to]
            cur %= self.mod
        self.rep[s] = rep

        n = len(V[s])
        L = [0] * self.N; R = [0] * self.N
        L2 = [0] * self.N; R2 = [0] * self.N

        for i, ne in enumerate(self.V[s]):
            L[i] = R[i] = self.A[ne] * self.C.inv[self.children[ne]] % self.mod
            L2[i] = R2[i] = self.children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= self.mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= self.mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(self.V[s]):
            if ne == p:
                continue
            self.A[s] = 1
            self.children[s] = 1
            if i > 0:
                self.A[s] *= L[i - 1]
                self.A[s] %= self.mod
                self.children[s] += L2[i - 1]
            if i + 1 < n:
                self.A[s] *= R[i + 1]
                self.A[s] %= self.mod
                self.children[s] += R2[i + 1]
            self.A[s] *= self.C.fac[self.N - self.children[ne] - 1]
            self.A[s] %= self.mod
            dfs2(ne, s)
        return

class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.mod = mod
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod

def ABC160():
    N = I()
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    dp_r = treedp_rerooting(N,V,mod)
    dp_r.dfs(0)
    dp_r.dfs2(0)

    ans = dp_r.rep

    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160()

"""
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
"""

# 40
# 280
# 840
# 120
# 120
# 504
# 72
# 72

Submission status: Runtime Error

Solution code:
class treedp_rerooting():
    def __init__(self, N, V, MOD):
        self.N = N
        self.V = V
        self.mod = MOD
        self.rep = [0] * N
        self.children = [-1] * N
        self.A = [0] * N
        self.C = combination(N, MOD)
        return

    # 子の数のカウント
    def dfs(self, s):
        size = 1
        nowchild = []
        cur = 1
        self.children[s] = 0
        for i in self.V[s]:
            if self.children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= self.mod
        self.children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= C.comb(rest, k, mod)
            rest -= k
            cur %= mod
        self.A[s] = cur
        return size, cur

    def dfs2(self, s, p=-1):
        cur = 1
        rest = self.N - 1
        for to in self.V[s]:
            cur *= self.A[to]
            cur %= mod
        for to in self.V[s]:
            cur *= C.comb(rest, children[to], mod)
            rest -= self.children[to]
            cur %= self.mod
        self.rep[s] = rep

        n = len(V[s])
        L = [0] * self.N; R = [0] * self.N
        L2 = [0] * self.N; R2 = [0] * self.N

        for i, ne in enumerate(self.V[s]):
            L[i] = R[i] = self.A[ne] * C.inv[self.children[ne]] % self.mod
            L2[i] = R2[i] = self.children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= self.mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= self.mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(self.V[s]):
            if ne == p:
                continue
            self.A[s] = 1
            self.children[s] = 1
            if i > 0:
                self.A[s] *= L[i - 1]
                self.A[s] %= self.mod
                self.children[s] += L2[i - 1]
            if i + 1 < n:
                self.A[s] *= R[i + 1]
                self.A[s] %= self.mod
                self.children[s] += R2[i + 1]
            self.A[s] *= C.fac[self.N - self.children[ne] - 1]
            self.A[s] %= self.mod
            dfs2(ne, s)
        return

class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r, mod):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

def ABC160():
    N = I()
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    dp_r = treedp_rerooting(N,V,mod)
    dp_r.dfs(0)
    dp_r.dfs2(0)

    ans = dp_r.rep

    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160()

"""
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
"""

# 40
# 280
# 840
# 120
# 120
# 504
# 72
# 72

Submission status: Runtime Error

Solution code:
class treedp_rerooting():
    def __init__(self, N, V, MOD):
        self.N = N
        self.V = V
        self.mod = MOD
        self.rep = [0] * N
        self.children = [-1] * N
        self.A = [0] * N
        self.C = combination(N, MOD)
        return

    # 子の数のカウント
    def dfs(self, s):
        size = 1
        nowchild = []
        cur = 1
        self.children[s] = 0
        for i in self.V[s]:
            if self.children[i] != -1:
                continue
            ns, nc = dfs(i)
            nowchild.append(ns)
            size += ns
            cur *= nc
            cur %= self.mod
        self.children[s] = size
        rest = size - 1
        for k in nowchild:
            cur *= C.comb(rest, k, mod)
            rest -= k
            cur %= mod
        self.A[s] = cur
        return size, cur

    def dfs2(self, s, p=-1):
        cur = 1
        rest = self.N - 1
        for to in self.V[s]:
            cur *= self.A[to]
            cur %= mod
        for to in self.V[s]:
            cur *= C.comb(rest, children[to], mod)
            rest -= self.children[to]
            cur %= self.mod
        self.rep[s] = rep

        n = len(V[s])
        L = [0] * self.N; R = [0] * self.N
        L2 = [0] * self.N; R2 = [0] * self.N

        for i, ne in enumerate(self.V[s]):
            L[i] = R[i] = self.A[ne] * C.inv[self.children[ne]] % self.mod
            L2[i] = R2[i] = self.children[ne]
        for i in range(1, n):
            L[i] *= L[i - 1]
            L[i] %= self.mod
            L2[i] += L2[i - 1]
        for i in range(1, n - 1)[::-1]:
            R[i] *= R[i + 1]
            R[i] %= self.mod
            R2[i] += R2[i + 1]
        for i, ne in enumerate(self.V[s]):
            if ne == p:
                continue
            self.A[s] = 1
            self.children[s] = 1
            if i > 0:
                self.A[s] *= L[i - 1]
                self.A[s] %= self.mod
                self.children[s] += L2[i - 1]
            if i + 1 < n:
                self.A[s] *= R[i + 1]
                self.A[s] %= self.mod
                self.children[s] += R2[i + 1]
            self.A[s] *= C.fac[self.N - self.children[ne] - 1]
            self.A[s] %= self.mod
            dfs2(ne, s)
        return

class combination():
    # 素数のmod取るときのみ　速い
    def __init__(self, n, mod):
        self.n = n
        self.fac = [1] * (n + 1)
        self.inv = [1] * (n + 1)
        for j in range(1, n + 1):
            self.fac[j] = self.fac[j - 1] * j % mod

        self.inv[n] = pow(self.fac[n], mod - 2, mod)
        for j in range(n - 1, -1, -1):
            self.inv[j] = self.inv[j + 1] * (j + 1) % mod

    def comb(self, n, r, mod):
        if r > n or n < 0 or r < 0:
            return 0
        return self.fac[n] * self.inv[n - r] * self.inv[r] % mod

def ABC160():
    N = I()
    V = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    dp_r = treedp_rerooting(N,V,mod)
    dp_r.dfs(0)
    dp_r.dfs2(0)

    ans = dp_r.rep

    for v in ans:
        print(v)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC160()

"""
8
1 2
2 3
3 4
3 5
3 6
6 7
6 8
"""

# 40
# 280
# 840
# 120
# 120
# 504
# 72
# 72

Submission status: Runtime Error

Solution code:
# coding: utf-8
N = int(input())
branches = {}
for i  in range(N-1):
    branches[i] = list(map(int, input().split()))
tr = {}
to = {}
dp = {}
dp2 = {}
fact_val = {}
mod = 1e9 + 7

def fact(n):
    if n in fact_val.keys():
        return fact_val[n]
    ret = 1
    if n == 0:
        fact_val[n] = 1
        return 1
    for i in range(1, n+1):
        ret *= i
    fact_val[n] = ret
    return ret

def perm(n, k):
    return fact(n) / fact(n-k)

def _to(node):
    if node in to.keys():
        return to[node]
    else:
        to[node] = []
        for i in range(N-1):
            if branches[i][0] == node:
                to[node].append(branches[i][1])
            elif branches[i][1] == node:
                to[node].append(branches[i][0])
        return to[node]

def dps(node, p=-1):
    go = False
    a, b, childs = 0, 1, 1
    if node in dp.keys():
        return dp[node]
    
    for branch in _to(node):
        if branch == p:
            continue
        _dp, _wt = dps(branch, p=node)
        b *= fact(_wt + 1)
        a += _wt + 1
        childs *= _dp

    dp[node] = [int((fact(a) / b * childs) % mod), a]
    return dp[node]

def bps(node, p=-1):
    if p == -1:
        dp2[node] = dp[node]
    dp_p, wt_p = dp2[node]
    for branch in _to(node):
        if branch == p:
            continue
        dp_branch, wt_branch = dp[branch]
        if branch in dp2.keys():
            bps(branch, p=node)
        else:
            tmp = [int(dp_p / perm(wt_p, wt_branch + 1) * fact(wt_branch + 1) / dp_branch),
                   wt_p-wt_branch-1]
            dp_new = dp_branch / fact(tmp[1]+1) * perm(wt_p, tmp[1]+1) * tmp[0]
            dp2[branch] = [int(dp_new % mod), wt_p]
            bps(branch, p=node)
    return None
        
if __name__ == "__main__":
    dps(3)
    bps(3)
    for i in range(1, N+1):
        print(dp2[i][0])

Submission status: Runtime Error

Solution code:
import sys
def input(): return sys.stdin.readline().strip()


"""
ABC160-Fの解説放送での実装をPythonで焼きなおしてみました。
内訳：
    class Combination : mod付きの組み合わせの計算用クラス
    class DP : 木DPを行うためのクラス（本問用に特殊化）
    dfs(v, p=-1) : 頂点v以下の部分木に対してdpした結果を返す
    bfs(v, p=-1) : 頂点vに入ってくるdp値の総和を取り、頂点vの子供に親からのdp値を渡す
"""

class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

# 早速グローバル変数として用意しておく
cmb = Combination(2 * 10 ** 5)


class DP:
    """
    木DPをする準備として、dpの値と木のサイズを両方保持するクラスを定義する。
    さらに演算子オーバーロードにより足し算記号でdpの値の更新（今回は組み合わせ含む掛け算）と
    木のサイズの合算を同時にやってくれるようにする。
    dp計算は全てmodを取ることに注意。
    """
    def __init__(self, m_dp=1, m_t=0, mod=10**9+7):
        self.dp = m_dp
        self.t = m_t
        self.mod = mod
    
    def __iadd__(self, other):
        """
        a = DP(3, 2); b = DP(4, 5)として
        a += bによりa = DP(12, 7)みたいになる。
        二つの木を合わせるために新しくつける根はまだ足していないことに注意。
        """
        self.dp *= other.dp * cmb(self.t + other.t, self.t)
        self.dp %= self.mod
        self.t += other.t
        return self
    
    def __sub__(self, other):
        """
        引き算も同様にオーバーロード（ただしこっちは二項演算）。
        また、こちらはbfsで親の木のdp値を送ることを念頭においていることに注意。
        """
        dp = self.dp * pow(other.dp * cmb(self.t - 1, other.t), self.mod - 2, self.mod) # dp = self.dp / other.dp * cmb(self.t - 1, other.t)
        t = self.t - other.t
        return DP(dp, t)
    
    def addRoot(self):
        self.t += 1
        return self
    
    def subroot(self):
        self.t -= 1
        return self



def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    mod = 10**9+7

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

    """
    まずは頂点0を根として木DPをする、すなわち頂点0に数字1を書き込んだ場合の
    残りの数の書き込み方の場合の数を計算する。
    """

    # 最初の木DPの途中経過を記録する配列を準備
    # dp[v][i] = (頂点vのi番目の子を根とする部分木から頂点vに渡されるdp値)
    dp = [[DP() for u in repn[v]] for v in range(N)]
    # dpSum[v] = (頂点vの子供を根とする部分木からそれぞれ頂点vに渡されるdp値の総和)
    dpSum = [DP() for _ in range(N)]

    def dfs(v, p=-1):
        """
        dfsというよりは木DPをした結果を返す関数。

        根がvの部分木（頂点pはvの親として含めない）のdp結果を返すが、
        そのためにvの各子供に対する部分木dpの結果を足し合わせて、
        最後に木のサイズを1(v自身の分)だけ増やしている。

        v自身が葉ノードの場合はDPクラス内で既に初期化が済んでいることに注意。
        """
        for i, u in enumerate(repn[v]):
            if u == p:
                continue
            dp[v][i] = dfs(u, v)
            dpSum[v] += dp[v][i]
        return dpSum[v].addRoot()

    dfs(0)
    # この時点で各dpSum[v]には、子供らのdp値を総和した値と、頂点vを含む木のサイズが記録される
    # for i in range(N):
    #     print("dpSum[{}]=[{}, {}]".format(i, dpSum[i].dp, dpSum[i].t))

    """
    次に全方位木DPのためのbfsを行う。
    全方位木そのもののアルゴリズムは解説放送を参照。
    あえてポイントを述べるとすれば、
        1. 木の各辺の向きが、部分木と１対１対応する。
        2. dfs時点で各辺の根に上がる向きの部分木dpは記録済み
        3. 逆向きの辺のdp値は、全ての隣接辺に対して入ってくる向きの
        　　dp値がわかっている頂点（例えば根）に関してならdp値の総和を
        　　考えることで出ていく向きのdp値がO(1)で求まる。
        4. これを隣接する頂点ごとに計算すればよい。
    """

    def bfs(v, dpP=DP(), p=-1):
        """
        頂点vからのbfsというかdfsで求めたdp値の逆伝搬（出ていく方のdp値）の計算を行う。
        dpPは頂点vの親から来る部分木のdp値。

        まず親から来る部分木のdp値を加えることで、頂点vに隣接する全ての辺から入ってくる
        dp値の総和を完成させる。
        
        このときdpSum[v]自体が頂点vを含んでしまうとdp計算で木のサイズを使う際に狂いが生じるので、
        一旦頂点vを除いたうえでdpPを加えて、その後頂点vを戻す（これで頂点vに対する解は求まった）。
        """
        
        if p != -1:
            dpSum[v].subroot()
            dpSum[v] += dpP
            dpSum[v].addRoot()

        # 次に頂点vのそれぞれの子（頂点u）に対して、頂点uを主役と見たときの親からのdp値を渡す。、
        for i, u in enumerate(repn[v]):
            if u == p:
                dp[v][i] = dpP
            else:
                d = dpSum[v] - dp[v][i]
                bfs(u, d, v)
    
    bfs(0)
    for i in range(N):
        # print("dpSum[{}]=[{}, {}]".format(i, dpSum[i].dp, dpSum[i].t))
        print(int(dpSum[i].dp))



if __name__ == "__main__":
    main()