Problem p02728 (python)

Fixed submission:
#!/usr/bin/env python3
import sys
from collections import defaultdict
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()

Buggy submission (verdict: Runtime Error):
#!/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()

Buggy submission (verdict: Runtime Error):
#!/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()