AtCoder Beginner Contest 401 E,F,G問題メモ

class UnionFind:
    def __init__(self, n):
        self.table = [-1] * n

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return False
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            self.table[r1] += d2
        else:
            self.table[r1] = r2
            self.table[r2] += d1
        return True

    def get_size(self, x):
        return -self.table[self.root(x)]


def solve(n, m, edges):
    small_edges = [set() for _ in range(n)]
    large_edges = [set() for _ in range(n)]
    for u, v in edges:
        u -= 1
        v -= 1
        small_edges[u].add(v)
        large_edges[v].add(u)
    ans = []
    uft = UnionFind(n)
    remove = set()
    for i in range(n):
        remove.update(small_edges[i])
        remove.discard(i)
        for j in large_edges[i]:
            uft.unite(i, j)
        if uft.get_size(0) != i + 1:
            ans.append(-1)
            continue
        ans.append(len(remove))
    return ans


n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
ans = solve(n, m, edges)
print('\n'.join(map(str, ans)))

from bisect import bisect_left
from itertools import accumulate

from dataclasses import dataclass
from typing import List, Callable, TypeVar

T = TypeVar('T')
U = TypeVar('U')


@dataclass
class RerootingEdge:
    src: int
    tgt: int
    value: U


class Rerooting:
    """
    抽象化 全方位木DP
    ・r = 1,2,...,N について、頂点 r を根とした木DPの結果（DP[r]）を求める。
    ・merge 演算に逆演算が成り立たない場合に対応
    ・頂点に対して値が決められている場合、辺に対して値が決められている場合（あるいは両方）のいずれにも対応

    【使い方】
    ① __init__()に示された関数を定義する
    ② add_edge()にてN-1本の辺を与える。u→v と v→u で2回呼んで双方向で与える。
    ③ solve()

    【apply, merge 関数で処理すべき内容】
       (u)      ans[v] には、"v 自身の値は未反映の" v 以下の部分木に対するDP結果が入る。（その方が定義する関数の数を減らせるため）
      ／|＼      （※ たとえば「ans[i] = i 以下の部分木の頂点数」とした場合、ans[v] には v 自身は加算されていない）
    (v)(w)(x)   ans[u] を求める際に呼ばれる apply(ans[v]) 内で、v についての情報を反映する。
                apply では↑と同時に、辺をu→vとたどる際に何らかの処理が行われる場合はそれも反映する。頂点 u の値の反映は行わない。
                merge は、[ unit, apply(ans[v]), apply(ans[w]), apply(ans[x]) ] を左から2つずつ累積的に合成していく処理を行う。
                全てマージされた結果が、ans[u] となる。
    """

    def __init__(self,
                 n: int,
                 leaf_factory: Callable[[], T],  # 1回目のDFSで葉に適用する値
                 unit_factory: Callable[[], T],  # 単位元
                 merge: Callable[[T, T], T],  # 演算
                 apply: Callable[[T, RerootingEdge], T],  # [子の値, 親→子への辺] から、親に伝える情報を計算
                 ) -> None:
        self.n: int = n
        self.links: List[List[RerootingEdge]] = [[] for _ in range(n)]
        self.leaf = leaf_factory
        self.unit = unit_factory
        self.merge = merge
        self.apply = apply

    def add_edge(self, s, t, value) -> None:
        self.links[s].append(RerootingEdge(src=s, tgt=t, value=value))

    def solve(self) -> List[T]:
        links = self.links
        status = [0] * self.n

        leaf = self.leaf
        unit = self.unit
        merge = self.merge
        apply = self.apply

        # 1回目のDFSで、自身の子のapply済み結果の左からの累積和
        acc_left: List[List[T]] = [[unit()] for _ in range(self.n)]
        # 1回目のDFSで、自身の子のapply済み結果の右からの累積和
        acc_right: List[List[T]] = [[unit()] for _ in range(self.n)]

        # 最終結果（1回目のDFSでは自身のsubtreeのみの結果が入る）
        ans: List[T] = [unit() for _ in range(self.n)]
        # 親に向かう辺
        parents: List[RerootingEdge | None] = [None for _ in range(self.n)]
        # 2回目のDFSで、親から伝播される値（apply済）
        from_parent: List[T] = [unit() for _ in range(self.n)]

        q = [0]
        while q:
            v = q[-1]
            if status[v] == 0:
                status[v] = 1

                # 親頂点をリンクリストから除く
                children_links = []
                for e in links[v]:
                    if status[e.tgt] == 0:
                        children_links.append(e)
                    else:
                        parents[v] = e
                links[v] = children_links

                for e in links[v]:
                    q.append(e.tgt)
            else:
                q.pop()

                if len(links[v]) == 0:
                    ans[v] = leaf()

                else:
                    acl = acc_left[v]

                    for e in links[v]:
                        acl.append(apply(ans[e.tgt], e))

                    acr = acc_right[v]
                    for i in range(len(acl) - 1, 0, -1):
                        acr.append(merge(acl[i], acr[-1]))
                    acr.reverse()

                    for i in range(1, len(acl)):
                        acl[i] = merge(acl[i - 1], acl[i])

                    ans[v] = acl[-1]

                status[v] = 2

        q = [0]
        while q:
            v = q.pop()
            fp = from_parent[v]
            ans[v] = merge(ans[v], fp)

            acl = acc_left[v]
            acr = acc_right[v]
            for li, e in enumerate(links[v]):
                pe = parents[e.tgt]
                tgt_data = merge(fp, merge(acl[li], acr[li + 1]))
                from_parent[e.tgt] = apply(tgt_data, pe)
                q.append(e.tgt)

        return ans


def solve(n1, edges1, n2, edges2):
    apply = lambda cv, edges: cv + 1
    reroot1 = Rerooting(n1, int, int, max, apply)
    reroot2 = Rerooting(n2, int, int, max, apply)
    for u, v in edges1:
        u -= 1
        v -= 1
        reroot1.add_edge(u, v, 0)
        reroot1.add_edge(v, u, 0)
    for u, v in edges2:
        u -= 1
        v -= 1
        reroot2.add_edge(u, v, 0)
        reroot2.add_edge(v, u, 0)
    farthest1 = reroot1.solve()
    farthest2 = reroot2.solve()
    d = max(max(farthest1), max(farthest2))
    if len(farthest1) > len(farthest2):
        n1, n2 = n2, n1
        farthest1, farthest2 = farthest2, farthest1
    farthest2.sort()
    acc = [0] + list(accumulate(farthest2))
    total = acc[-1]

    ans = 0
    for du in farthest1:
        lim = d - du
        k = bisect_left(farthest2, lim)
        ans += d * k + (du + 1) * (n2 - k) + total - acc[k]
    return ans


n1 = int(input())
edges1 = [tuple(map(int, input().split())) for _ in range(n1 - 1)]
n2 = int(input())
edges2 = [tuple(map(int, input().split())) for _ in range(n2 - 1)]
ans = solve(n1, edges1, n2, edges2)
print(ans)

from collections import deque
from typing import Tuple, List


class Dinic:
    """
    Usage:
       mf = Dinic(n)
    -> mf.add_link(from, to, capacity)
    -> mf.max_flow(source, target)
    """

    def __init__(self, n: int):
        self.n = n
        self.links: List[List[List[int]]] = [[] for _ in range(n)]
        # if exists an edge (v→u, capacity)...
        #   links[v] = [ [ capacity, u, index of rev-edge in links[u], is_original_edge ], ]

    def add_link(self, from_: int, to: int, capacity: int) -> None:
        self.links[from_].append([capacity, to, len(self.links[to]), 1])
        self.links[to].append([0, from_, len(self.links[from_]) - 1, 0])

    def bfs(self, s: int) -> List[int]:
        depth = [-1] * self.n
        depth[s] = 0
        q = deque([s])
        while q:
            v = q.popleft()
            for cap, to, rev, _ in self.links[v]:
                if cap > 0 and depth[to] < 0:
                    depth[to] = depth[v] + 1
                    q.append(to)
        return depth

    def dfs(self, s: int, t: int, depth: List[int], progress: List[int], link_counts: List[int]) -> int:
        links = self.links
        stack = [s]

        while stack:
            v = stack[-1]
            if v == t:
                break
            for i in range(progress[v], link_counts[v]):
                progress[v] = i
                cap, to, rev, _ = links[v][i]
                if cap == 0 or depth[v] >= depth[to] or progress[to] >= link_counts[to]:
                    continue
                stack.append(to)
                break
            else:
                progress[v] += 1
                stack.pop()
        else:
            return 0

        f = 1 << 60
        fwd_links = []
        bwd_links = []
        for v in stack[:-1]:
            cap, to, rev, _ = link = links[v][progress[v]]
            f = min(f, cap)
            fwd_links.append(link)
            bwd_links.append(links[to][rev])

        for link in fwd_links:
            link[0] -= f

        for link in bwd_links:
            link[0] += f

        return f

    def max_flow(self, s: int, t: int) -> int:
        link_counts = list(map(len, self.links))
        flow = 0
        while True:
            depth = self.bfs(s)
            if depth[t] < 0:
                break
            progress = [0] * self.n
            current_flow = self.dfs(s, t, depth, progress, link_counts)
            while current_flow > 0:
                flow += current_flow
                current_flow = self.dfs(s, t, depth, progress, link_counts)
        return flow

    def cut_edges(self, s: int) -> List[Tuple[int, int]]:
        """ max_flowしたあと、最小カットにおいてカットすべき辺を復元する """
        q = [s]
        reachable = [0] * self.n
        reachable[s] = 1
        while q:
            v = q.pop()
            for cap, u, li, _ in self.links[v]:
                if cap == 0 or reachable[u]:
                    continue
                reachable[u] = 1
                q.append(u)
        edges = []
        for v in range(self.n):
            if reachable[v] == 0:
                continue
            for cap, u, li, orig in self.links[v]:
                if orig == 1 and reachable[u] == 0:
                    edges.append((v, u))
        return edges


def solve(n, starts, goals):
    distances = [[0.] * n for _ in range(n)]
    lo_limit = 0.
    hi_limit = 0.
    for i in range(n):
        sx, sy = starts[i]
        for j in range(n):
            gx, gy = goals[j]
            d2 = (sx - gx) ** 2 + (sy - gy) ** 2
            distances[i][j] = d2 ** 0.5
        lo_limit = max(lo_limit, min(distances[i]))
        hi_limit = max(hi_limit, max(distances[i]))

    l = lo_limit
    r = hi_limit
    eps = 1e-7
    s = n * 2
    t = s + 1
    while True:
        if (r - l) / r < eps:
            break
        lim = (l + r) / 2

        dnc = Dinic(n * 2 + 2)
        for i in range(n):
            dnc.add_link(s, i, 1)
            dnc.add_link(i + n, t, 1)
            for j in range(n):
                d = distances[i][j]
                if d <= lim:
                    dnc.add_link(i, j + n, 1)
        f = dnc.max_flow(s, t)
        if f == n:
            r = lim
        else:
            l = lim

    return r


n = int(input())
starts = [tuple(map(int, input().split())) for _ in range(n)]
goals = [tuple(map(int, input().split())) for _ in range(n)]
ans = solve(n, starts, goals)
print(f'{ans:.7f}')