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:
from collections import defaultdict
from functools import lru_cache
import sys
input=sys.stdin.readline


class Reroot:
    def __init__(self, N, e, merge, f, g):
        self.G = defaultdict(list)
        self.parents = [-1]*(N+1)
        self.dp = defaultdict(lambda: defaultdict(int))
        self.merge = merge
        self.f = f
        self.g = g
        self.e = e

    def add_edge(self, s, t):
        self.G[s].append(t)

    def build(self):
        self.dfs1(1)
        self.dfs2(1)
        return self.dp

    def dfs1(self, s):
        l = []
        q = [1]
        while q:
            s = q.pop()
            l.append(s)
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                self.parents[t] = s
                q.append(t)

        for s in l[::-1]:
            v = self.e
            for t in self.G[s]:
                if t == self.parents[s]:
                    continue
                v = self.merge(v, self.f(self.dp[s][t], s, t))
            self.dp[self.parents[s]][s] = self.g(v, self.parents[s], s)

    def dfs2(self, s):
        q = [(s, self.e)]
        while q:
            s, dp_p = q.pop()
            par = self.parents[s]
            for t in self.G[s]:
                if t == par:
                    self.dp[s][t] = dp_p

            size = len(self.G[s])
            ac_l = [self.e] * (size+1)
            ac_r = [self.e] * (size+1)
            for i, t in enumerate(self.G[s]):
                ac_l[i+1] = self.merge(ac_l[i], self.f(self.dp[s][t], s, t))
            for i, t in enumerate(self.G[s][::-1]):
                ac_r[size-i-1] = self.merge(ac_r[size-i], self.f(self.dp[s][t], s, t))
            self.ans[s] = self.g(ac_l[size], -1, 1)
            self.dp[-1][s] = self.g(ac_l[size], -1, s)

            for i, t in enumerate(self.G[s]):
                if t == par:
                    continue
                q.append((t, self.g(self.merge(ac_l[i], ac_r[i+1]), t, s)))


def solve():
    N = int(input())

    MOD = 10**9+7
    n = N
    fac = [1]*(n+1)
    rev = [1]*(n+1)
    d = defaultdict(list)

    for i in range(1,n+1):
        fac[i] = i*fac[i-1]%MOD
        rev[i] = pow(fac[i], MOD-2, MOD)

    merge1 = lambda x,y:x+y
    f1 = lambda x, par, s:x
    g1 = lambda x, par, s:x+1
    e1 = 0
    tree1 = Reroot(N, e1, merge1, f1, g1)

    merge2 = lambda x,y:(x*y)%MOD
    f2 = lambda x, par, s:(x*rev[tree1.dp[par][s]])%MOD
    g2 = lambda x, par, s:(x*fac[tree1.dp[par][s]-1])%MOD
    e2 = 1
    tree2 = Reroot(N, e2, merge2, f2, g2)

    for _ in range(N-1):
        a, b = map(int, input().split())
        tree2.add_edge(a, b)
        tree2.add_edge(b, a)
        tree1.add_edge(a, b)
        tree1.add_edge(b, a)

    tree1.build()
    ans = tree2.build()

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


if __name__ == "__main__":
    solve()

Submission status: Runtime Error

Solution code:
from collections import defaultdict
from functools import lru_cache
import sys
sys.setrecursionlimit(1000000)
input=sys.stdin.readline


N = int(input())
MOD = 10**9+7
n = N
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)

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

size = [0]*(N+1)
dp = [0]*(N+1)

@lru_cache(maxsize=None)
def dfs1(s, par):
    ans = 1
    for t in d[s]:
        if t==par:continue
        ans += dfs1(t, s)
    size[s] = ans
    return ans

@lru_cache(maxsize=None)
def dfs2(s, par):
    ans = 1
    l = []
    for t in d[s]:
        if t==par:continue
        ans *= dfs2(t, s)
        ans %= MOD
        l.append(size[t])
    
    m = fac[sum(l)]
    v = 1
    for i in l:
        v *= fac[i]
        v %= MOD
    ans *= (m * pow(v, MOD-2, MOD))
    ans %= MOD
    dp[s] = ans
    return ans


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

Submission status: Runtime Error

Solution code:
from collections import defaultdict

N = int(input())

MOD = 10**9+7
n = N
fac = [1]*(n+1)
rev = [1]*(n+1)
 
for i in range(1,n+1):
  fac[i] = i*fac[i-1]%MOD
  rev[i] = pow(fac[i], MOD-2, MOD)

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

size = [0]*(N+1)
dp = [0]*(N+1)

def dfs1(s, par):
    ans = 1
    for t in d[s]:
        if t==par:continue
        ans += dfs1(t, s)
    size[s] = ans
    return ans

def dfs2(s, par):
    ans = 1
    l = []
    for t in d[s]:
        if t==par:continue
        ans *= dfs2(t, s)
        ans %= MOD
        l.append(size[t])
    
    m = fac[sum(l)]
    v = 1
    for i in l:
        v *= fac[i]
        v %= MOD
    ans *= (m * pow(v, MOD-2, MOD))
    ans %= MOD
    dp[s] = ans
    return ans


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

Submission status: Runtime Error

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

MOD = 10**9 + 7
MOD_t_MAX = 2 * 10**5 + 10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD
def MOD_inv(a):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u = u % MOD
    if u < 0:
        u += MOD
    return u

def init_Graph(G):
    for _ in range(len(G)-1):
        a, b = map(int, input().split())
        a, b = a-1, b-1
        G[a].append(b)
        G[b].append(a)

def dfs(G, dp, t, perm, crr, pre):
    tmp = 1
    f = False
    for nxt in G[crr]:
        if nxt == pre:
            continue
        dfs(G, dp, t, perm, nxt, crr)
        t[crr] += t[nxt]
        tmp *= dp[nxt]
        f = True
    if f:
        dp[crr] = perm[t[crr]-1]
        for nxt in G[crr]:
            if nxt == pre:
                continue
            dp[crr] *= inv[perm[t[nxt]]] * dp[nxt]
            dp[crr] %= MOD
    else:
        dp[crr] = 1

def solve(G, dp, t, perm, crr, pre, mul):
    dp[crr] *= inv[perm[t[crr]-1]] * perm[len(G)-1] * mul
    dp[crr] %= MOD
    for nxt in G[crr]:
        if nxt == pre:
            continue
        crr_t = len(G)
        crr_t -= t[nxt]
        crr_dp = dp[crr]
        crr_dp *= perm[t[nxt]] * inv[perm[len(G)-1]] * perm[len(G)-t[nxt]-1] * inv[dp[nxt]]
        crr_dp %= MOD
        tmp = inv[perm[crr_t]] * crr_dp % MOD
        solve(G, dp, t, perm, nxt, crr, tmp)

def main():
    n = int(input())
    G = [[] for _ in range(n)]
    init_Graph(G)
    MOD_COM_init()
    t = [1]*n
    dp = [0]*n
    perm = [1]*(2 * 10**5 + 10)
    for i in range(2, 2 * 10**5 + 10):
        perm[i] = perm[i-1] * i % MOD
    dfs(G, dp, t, perm, 0, -1)
    solve(G, dp, t, perm, 0, -1, 1)
    for v in dp:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#%%
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math

#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率


def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]

        
class comb:
    def __init__(self,N,mod=10**9+7):#コンビネーションnCrをmodで求める、Nは最大のn 
        self.mod=mod
        self.fact=[0]*(N+1)
        self.ifact=[0]*(N+1)
        fact,ifact=self.fact,self.ifact
        fact[0],fact[1],ifact[0],ifact[1]=1,1,1,1
        for i in range(2,N+1):
            x=(fact[i-1]*i)%mod
            fact[i]=x
            ifact[i]=self.extgcd1(x,mod)
        

    @lru_cache(maxsize = None)
    def extgcd1(self,a0,b0):#計算量log(b0),フェルマーの小定理より早い
        u,v,a,b=1,0,a0,b0
        while b:
            t,a=divmod(a,b)
            a,b,u,v=b,a,v,u-t*v
        if a!=1: 
            print("not 素")
            return -1
        return u%b0

    @lru_cache(maxsize = None)
    def comb(self,n,r): return (self.fact[n]*self.ifact[r]%self.mod)*self.ifact[n-r]%self.mod

    @lru_cache(maxsize = None)
    def mulcomb(self,n,*rs):#n!/(r1!*r2!*r3!*...)
        ans=self.fact[n]
        for r in rs: ans=(ans*self.ifact[r])%self.mod
        return ans

class rerooting:#全方位木
    def __init__(self,N,edge):#単位元self.unitとモノイドdef funcを設定すること,
        #dics[親][根（親の隣接点)]=その部分木での値
        self.unit=(1,0)
        self.mod=10**9+7
        self.edge=edge
        cb=comb(N)
        self.fact=cb.fact
        self.ifact=cb.ifact
        self.par=[-1]*N
        self.N=N
        self.visited=[0]*N
        self.dics=[dict() for _ in range(N)]
        self.ikigake=[]
        self.tot=[self.unit]*N
    
    #@lru_cache(maxsize = None)
    def func(self,x,y):
        #ifact=self.ifact
        #mod=self.mod
        p1,s1=x
        p2,s2=y
        ans=(p1*p2)%self.mod
        ssum=s1+s2
        ans*=(self.fact[ssum]*self.ifact[s1])%self.mod*self.ifact[s2]%mod
        ans%=self.mod
        return ans,ssum 

    def addnode(self,x):#部分木に親のノードを結合する処理,dfsとforwardに出現
        return x[0],x[1]+1

    def _dfs(self,e,pa):
        edge=self.edge
        self.par[e]=pa
        self.ikigake.append(e)
        ans=self.unit
        for ne in edge[e]:
            if self.par[ne]!=-1:
                continue
            ans=self.func(ans,self.addnode(self._dfs(ne,e)))
            #print(ans)
        if pa!=e:
            self.dics[pa][e]=ans
        
        return ans
    
    def forward(self,start):
        self._dfs(start,start)
        #print(t2-t1)
        #count=0
        for e in self.ikigake:
            pa=self.par[e]
            de=self.dics[e]
            nes=tuple(de.keys())
            nvals=tuple(de.values())
            l=len(nes)
            aleft=[self.unit]
            aright=[self.unit]
            cleft=self.unit
            cright=self.unit
            for i in range(l-1):
                aleft.append(self.func(aleft[-1],self.addnode(nvals[i])))
                aright.append(self.func(aright[-1],self.addnode(nvals[-i-1])))
                #count+=4
            self.tot[e]=self.func(aright[-1],self.addnode(nvals[0]))
            for i,ne in enumerate(nes):
                if ne==pa:
                    continue
                self.dics[ne][e]=self.func(aleft[i],aright[-1-i])
                #count+=1
        #print(t3-t2)

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    def tree_init(N):
        edgelist = [[] for _ in range(N)]
        elist=set()
        for a, b in [map(int, input().split()) for i in range(N-1)]:#木じゃない場合N-1をNに変える
            edgelist[a-1].append(b-1)#ノードの番号が0から始まる場合-1を消す
            edgelist[b-1].append(a-1)
            elist.add((a-1,b-1))
        return edgelist,elist

    edge,elist=tree_init(N)
    cb=comb(N)
    rt=rerooting(N,edge)
    rt.forward(0)

    for a in range(N):
        print(rt.tot[a][0])

if __name__ == "__main__":
    main()

#%%

Submission status: Runtime Error

Solution code:
MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

NN = 2020200

f = [0]*NN
rf = [0]*NN
inv = [0]*NN
f[0], f[1] = 1, 1
rf[0], rf[1] = 1, 1
inv[1] = 1

for i in range(2, NN):
    f[i] = (f[i-1] * i) % MOD
    inv[i] = (-inv[MOD % i] * (MOD // i)) % MOD
    rf[i] = (rf[i-1] * inv[i]) % MOD


def C(n, r):
    return (f[n] * rf[r] * rf[n-r]) % MOD


def dfs1(node, par):
    num[node] += 1
    for ne in graph[node]:
        if ne == par:
            continue
        dfs1(ne, node)
        num[node] += num[ne]

    n = num[node] - 1
    res = 1
    for ne in graph[node]:
        if ne == par:
            continue
        res *= C(n, num[ne]) * val[ne] % MOD
        res %= MOD
        n -= num[ne]
    val[node] = res


def dfs2(node, par):
    val_ori_ori = val[node]
    num_ori_ori = num[node]
    ori = 1
    n = 0
    for ne in graph[node]:
        n += num[ne]

    num_ori = n + 1
    for ne in graph[node]:
        ori *= C(n, num[ne]) * val[ne] % MOD
        ori %= MOD
        n -= num[ne]

    ans[node] = ori

    for ne in graph[node]:
        if ne == par:
            continue
        val[node] = ori * inv[C(num_ori - 1, num[ne])] % MOD * inv[val[ne]] % MOD
        num[node] = num_ori - num[ne]
        dfs2(ne, node)

    num[node] = num_ori_ori
    val[node] = val_ori_ori


n = int(input())
Edge = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for _ in range(n)]
for e in Edge:
    graph[e[0] - 1].append(e[1] - 1)
    graph[e[1] - 1].append(e[0] - 1)

num = [0]*n
val = [0]*n
ans = [0]*n

dfs1(0, -1)
dfs2(0, -1)
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7
# MOD = 998244353
# sys.setrecursionlimit(10**8)

NN = 202020

f = [0]*NN
rf = [0]*NN
inv = [0]*NN
f[0], f[1] = 1, 1
rf[0], rf[1] = 1, 1
inv[1] = 1

for i in range(2, NN):
    f[i] = (f[i-1] * i) % MOD
    inv[i] = (-inv[MOD % i] * (MOD // i)) % MOD
    rf[i] = (rf[i-1] * inv[i]) % MOD


def C(n, r):
    return (f[n] * rf[r] * rf[n-r]) % MOD


n = int(input())
Edge = [list(map(int, input().split())) for i in range(n-1)]
graph = [[] for _ in range(n)]
for e in Edge:
    graph[e[0] - 1].append(e[1] - 1)
    graph[e[1] - 1].append(e[0] - 1)

num = [0]*n
val = [0]*n
ans = [0]*n


def dfs1(node, par):
    num[node] += 1
    for ne in graph[node]:
        if ne == par:
            continue
        dfs1(ne, node)
        num[node] += num[ne]

    n = num[node] - 1
    res = 1
    for ne in graph[node]:
        if ne == par:
            continue
        res *= C(n, num[ne]) * val[ne] % MOD
        res %= MOD
        n -= num[ne]
    val[node] = res


def dfs2(node, par):
    val_ori_ori = val[node]
    num_ori_ori = num[node]
    ori = 1
    n = 0
    for ne in graph[node]:
        n += num[ne]

    num_ori = n + 1
    for ne in graph[node]:
        ori *= C(n, num[ne]) * val[ne] % MOD
        ori %= MOD
        n -= num[ne]

    ans[node] = ori

    for ne in graph[node]:
        if ne == par:
            continue
        val[node] = ori * inv[C(num_ori - 1, num[ne])] % MOD * inv[val[ne]] % MOD
        num[node] = num_ori - num[ne]
        dfs2(ne, node)

    num[node] = num_ori_ori
    val[node] = val_ori_ori


dfs1(0, -1)
dfs2(0, -1)
for i in range(n):
    print(ans[i])

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
INF = float("inf")

tol = 1e-9


def ctc(x1, y1, r1, x2, y2, r2):
    # 二つの円の共通接線の数
    # common tangent count?
    # common tangent of circle?
    # 2円の関係性は、
    # 同一(=INF), 離れている(=4)、外接(=3)、交わる(=2)、内接(=1)、内包(=0)がある
    tol = 1e-9
    # r1 <= r2として一般性を失わない
    if r2 < r1:
        x1, x2 = x2, x1
        y1, y2 = y2, y1
        r1, r2 = r2, r1

    d = ((x1-x2)**2 + (y1-y2)**2)**0.5

    if x1 == x2 and y1 == y2 and d < tol:
        # 同一の円
        return INF
    elif (d - (r2+r1)) > tol:
        # 離れている
        return 4
    elif (d - (r2+r1)) > -tol:
        # 外接している
        return 3
    elif (d-(r2-r1)) > tol:
        # 交わっている
        return 2
    elif (d-(r2-r1)) > -tol:
        # 内接している
        return 1
    else:
        # 内包している
        return 0


def inner(x1, y1, c1, x2, y2, c2):
    coeff1 = c1/(c1+c2)
    coeff2 = c2/(c1+c2)
    b = (x1*coeff1+x2*coeff2, y1*coeff1+y2*coeff2)
    return b


def intersection(x1, y1, r1, x2, y2, r2):
    status = ctc(x1, y1, r1, x2, y2, r2)

    if not (1 <= status <= 3):
        return []
    elif status == 3:
        # 外接している場合
        return [inner(x1, y1, r1, x2, y2, r2)]
    elif status == 1:
        # 内接している場合
        return [(x1 + r1*(x1-x2)/d, y1 + r1*(y1-y2)/d)]
    else:
        # 交わっている場合
        L = ((x1-x2)**2 + (y1-y2)**2)**0.5
        cos = ((L**2+r1**2)-r2**2)/(2*r1*L)
        e1 = ((x2-x1)/L, (y2-y1)/L)
        e2 = (-(y2-y1)/L, (x2-x1)/L)
        P1H = ((r1*cos/L)*(x2-x1), (r1*cos/L)*(y2-y1))
        ah = (r1**2-(r1*cos)**2)**0.5
        HA = (e2[0]*ah, e2[1]*ah)
        A = (x1 + P1H[0]+HA[0], y1+P1H[1]+HA[1])
        B = (x1 + P1H[0]-HA[0], y1+P1H[1]-HA[1])
        return [A, B]


def circle_in(x, y, x1, y1, r1):
    tol = 1e-9
    L = (x1-x)**2 + (y1-y)**2
    R = r1**2
    LR = L-R

    if LR > tol:
        return False
    elif LR > -tol:
        return True
    else:
        return True


def solve(N: int, K: int, x: "List[int]", y: "List[int]", c: "List[int]"):

    # 時刻Tの時点でK枚以上の肉が焼ける熱源の配置はあるか

    left = -1
    right = ((max(x)-min(x))**2+(max(y)-min(y))**2)**0.7
    for _ in range(100):
        mid = (left + right)/2
        yakiniku = 0
        for i in range(N):
            for j in range(i+1, N):
                b = intersection(x[i], y[i], mid/c[i], x[j], y[j], mid/c[j])
                for xx, yy in b:
                    count = [circle_in(xx, yy, x[k], y[k], mid/c[k])
                             for k in range(N)]
                    if yakiniku < sum(count):
                        yakiniku = max(yakiniku, sum(count))
        for i in range(N):
            count = [circle_in(x[i], y[i], x[k], y[k], mid/c[k])
                     for k in range(N)]
            if yakiniku < sum(count):
                yakiniku = max(yakiniku, sum(count))
        # print(mid)
        # for i in range(N):
        #     print("(x-({}))^2+(y-({}))^2=({})^2".format(
        #         x[i], y[i], mid/c[i]))
        if yakiniku >= K:
            right = mid
        else:
            left = mid

    print(mid)
    return


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
    K = int(next(tokens))  # type: int
    x = [int()] * (N)  # type: "List[int]"
    y = [int()] * (N)  # type: "List[int]"
    c = [int()] * (N)  # type: "List[int]"
    for i in range(N):
        x[i] = int(next(tokens))
        y[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, K, x, y, c)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
from functools import lru_cache
from collections import deque


sys.setrecursionlimit(10**8)
INF = float("inf")

MOD = 1000000007  # type: int


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)

    def add_edge(self, src, dest, w=1):
        self.E[src].append((dest, w))
        self.E[dest].append((src, w))


@lru_cache(maxsize=None)
def div(a, b):
    return (a * pow(b, MOD-2, MOD)) % MOD


class Combination(object):

    def __init__(self, N, mod=MOD):
        fac, finv, inv = [0]*(N+1), [0]*(N+1), [0]*(N+1)
        fac[:2] = 1, 1
        finv[:2] = 1, 1
        inv[1] = 1
        for i in range(2, N+1):
            fac[i] = fac[i-1]*i % mod
            inv[i] = -inv[mod % i]*(mod//i) % mod
            finv[i] = finv[i-1]*inv[i] % mod
        self.N = N
        self.MOD = mod
        self.fac = fac
        self.finv = finv
        self.inv = inv

    @lru_cache(maxsize=None)
    def __call__(self, n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        b = (self.finv[k]*self.finv[n-k] % self.MOD)
        return (self.fac[n] * b) % self.MOD


def solve(N: int, a: "List[int]", b: "List[int]"):
    # print(div(3, 2))

    # 全方位木DPをやるぞ！
    # 1. 木DPによって頂点ごとにhogeを求める
    # 2. 木DPで求めたhogeを使って、上手く求める

    # グラフの構築
    g = Graph(N)
    for aa, bb in zip(a, b):
        g.add_edge(aa-1, bb-1)

    # 組み合わせの初期化
    cmb = Combination(N)

    dp = [1]*N                  # 節点vを根とした部分木の塗り方dp[v]
    size = [0]*N                # 節点vを根とした部分木のサイズsize[v]+1

    # 木DPを行うDFS
    queue = [(0, -1)]
    seen = [False]*N

    while queue:
        v, p = queue[-1]
        flag = True
        if seen[v] is False:
            for u, _ in g.E[v]:
                if u == p:
                    continue
                if seen[u] is False:
                    queue.append((u, v))
                    flag = False
        if flag is True:
            # 処理
            for u, _ in g.E[v]:
                if u == p:
                    continue
                size[v] += size[u]+1
                dp[v] *= cmb(size[v], size[u]+1)
                dp[v] %= MOD
                dp[v] *= dp[u]
                dp[v] %= MOD
            # print(v, p)
            queue.pop()
            seen[v] = True
    # print(*queue)
    # print(*[(d, s) for d, s in zip(dp, size)])

    # 節点0には木の根としての値を求めた。
    # 0以外の節点には部分木の根としての値を求めた。
    # 木の根としての値を求めた節点を親としてもつ節点は、自身を木の根とした値を求めることができる

    # 全方位木DPを行うBFS
    queue = deque()
    queue.append((0, -1))

    while len(queue) > 0:
        v, p = queue.popleft()
        for u, _ in g.E[v]:
            if u == p:
                continue
            d = div(dp[v], cmb(N-1, size[u]+1))
            d = div(d, dp[u])
            dp[u] *= cmb(N-1, size[u])
            dp[u] %= MOD
            dp[u] *= d
            dp[u] %= MOD
            queue.append((u, v))

    for v in dp:
        print(v)
    return


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

Solution code:
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n-1)]
mod=pow(10,9)+7
ki=[[] for _ in range(n)]
todo=[]
for a,b in ab:
  ki[a-1].append(b-1)
  ki[b-1].append(a-1)
  todo.append((a-1,b-1))
  todo.append((b-1,a-1))
import sys
sys.setrecursionlimit(100000)
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]%mod

dp=[[0]*n for _ in range(n)]
def node(i,j):
  if dp[i][j]!=0:
    return dp[i][j]
  l=ki[j]
  pat,size=1,0
  for li in l:
    if li!=i:
      if dp[j][li]!=0:
        sizei,pati=dp[j][li]
      else:
        sizei,pati=node(j,li)
        sizei,pati=sizei%mod,pati%mod
        dp[j][li]=(sizei,pati)
      size+=sizei
      size%=mod
      pat*=cmb(size,sizei)
      pat*=pati
      pat%=mod
  return size+1,pat
while todo:
    t=todo.pop()
    if dp[t[0]][t[1]]==0:
        size,pat=node(t[0],t[1])
        dp[t[0]][t[1]]=(size,pat)

for i in range(n):
  l=ki[i]
  size=0
  pat=1
  for li in l:
    sizei,pati=dp[i][li]
    size+=sizei
    pat*=cmb(size,sizei)
    pat*=pati
    pat%=mod
  print(pat)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri May  8 16:53:25 2020

@author: ybt07
"""

# -*- coding: utf-8 -*-
"""
Created on Fri May  8 12:10:59 2020
 
@author: ybt07
"""
 
import sys
sys.setrecursionlimit(3*10**5)  # 繰り返し制限
 
# 組み合わせ
N = 2*10**5   # 問題サイズに合わせて変えておく
MOD = 10**9 + 7
 
# 入力高速化
input = lambda : sys.stdin.readline().rstrip()
 
# modint
# https://qiita.com/wotsushi/items/c936838df992b706084c
 
class ModInt:
    def __init__(self, x):
        self.x = x % MOD
 
    def __str__(self):
        return str(self.x)
 
    __repr__ = __str__
 
    def __add__(self, other):
        return (
            ModInt(self.x + other.x) if isinstance(other, ModInt) else
            ModInt(self.x + other)
        )
 
    def __sub__(self, other):
        return (
            ModInt(self.x - other.x) if isinstance(other, ModInt) else
            ModInt(self.x - other)
        )
 
    def __mul__(self, other):
        return (
            ModInt(self.x * other.x) if isinstance(other, ModInt) else
            ModInt(self.x * other)
        )
 
    # / : 商。　逆元はフェルマーの小定理を利用している
    def __truediv__(self, other):
        return (
            ModInt(
                self.x * inv[other.x]
            ) if isinstance(other, ModInt) else
            ModInt(self.x * inv[other])
        )
 
    # ** : 指数
    def __pow__(self, other):
        return (
            ModInt(pow(self.x, other.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(self.x, other, MOD))
        )
 
    # x が Modint、y が通常の int の場合に、y.__add__(x) に対して、何を適用するか、定義している（→ x.__add__(y)を呼べ） 
    __radd__ = __add__
 
    def __rsub__(self, other):
        return (
            ModInt(other.x - self.x) if isinstance(other, ModInt) else
            ModInt(other - self.x)
        )
 
    __rmul__ = __mul__
 
    def __rtruediv__(self, other):
        return (
            ModInt(
                other.x * inv[self.x]
            ) if isinstance(other, ModInt) else
            ModInt(other * inv[self.x])
        )
 
    def __rpow__(self, other):
        return (
            ModInt(pow(other.x, self.x, MOD)) if isinstance(other, ModInt) else
            ModInt(pow(other, self.x, MOD))
        )
 
def cmb(n, r):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return fac[n] * facinv[r] * facinv[n-r] % MOD
 
fac = [1, 1] # 元テーブル
facinv = [1, 1] # 逆元テーブル
inv = [0, 1] # 逆元テーブル計算用テーブル
 
for i in range(2, N):
    fac.append( ( fac[-1] * i ) % MOD )
    inv.append( ( -inv[MOD % i] * (MOD//i) ) % MOD )
    facinv.append( (facinv[-1] * inv[-1]) % MOD )
 
# 部分木のDP値を求めていく
# u : 求める頂点
# 親（親側に辿らないように） p
 
def dfs(u, p = -1):
 
    global DP, CN, E
    
    # tmp_ans = 1
    # tmp_cn = 0  # （自分を含む）部分木のノード数
 
    # u から出ている頂点 v
    for v in E[u]:
        if not v == p:  # 親への辺以外について
            DP[v], CN[v] = dfs(v, u)
            CN[u] += CN[v]
            DP[u] *= DP[v] * cmb(CN[u], CN[v])
    CN[u] += 1
            
    return DP[u], CN[u]
 
# 各頂点の真のDP値を求めていく
 
def bfs(u, p=-1):
    
    global DP, E
        
    for v in E[u]:  # 各vに対して「真のDP値」を求めていく
        if v == p:
            continue
            
        # DP[u] と DP[v] から DP[v <- u] を求める
        cnv = CN[v]
        tmp_cn = N - cnv  # v から見たときの u の部分木の要素数
        DP[v] = DP[u] * cnv / tmp_cn 
 
        bfs(v, u)
    
    return

def main(): 
    # 入力処理
    N = int(input())  # 頂点数
    
    E = [[]*N for _ in range(N)]  # 辺の情報
     
    for _ in range(N - 1):
        a, b = map(int, input().split())
        E[a-1].append(b-1)  # 双方向の情報
        E[b-1].append(a-1)
        
    DP = [ModInt(1)] * N
    CN = [0] * N
     
    dfs(0)
    bfs(0)
    	 
    print(*DP, sep="\n")

main()