結果

問題 No.922 東北きりきざむたん
ユーザー 草苺奶昔草苺奶昔
提出日時 2023-03-28 17:42:59
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,528 ms / 2,000 ms
コード長 11,108 bytes
コンパイル時間 1,351 ms
コンパイル使用メモリ 81,788 KB
実行使用メモリ 347,872 KB
最終ジャッジ日時 2023-10-20 11:29:57
合計ジャッジ時間 23,856 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 66 ms
70,284 KB
testcase_01 AC 66 ms
70,284 KB
testcase_02 AC 66 ms
70,284 KB
testcase_03 AC 66 ms
70,284 KB
testcase_04 AC 90 ms
77,704 KB
testcase_05 AC 71 ms
72,340 KB
testcase_06 AC 94 ms
77,984 KB
testcase_07 AC 88 ms
77,576 KB
testcase_08 AC 94 ms
77,680 KB
testcase_09 AC 694 ms
125,256 KB
testcase_10 AC 540 ms
110,204 KB
testcase_11 AC 623 ms
120,760 KB
testcase_12 AC 377 ms
111,672 KB
testcase_13 AC 298 ms
89,648 KB
testcase_14 AC 850 ms
158,860 KB
testcase_15 AC 249 ms
114,916 KB
testcase_16 AC 1,320 ms
198,736 KB
testcase_17 AC 1,266 ms
198,300 KB
testcase_18 AC 1,165 ms
196,656 KB
testcase_19 AC 1,313 ms
202,444 KB
testcase_20 AC 1,264 ms
198,012 KB
testcase_21 AC 1,131 ms
206,208 KB
testcase_22 AC 1,073 ms
199,528 KB
testcase_23 AC 1,286 ms
243,584 KB
testcase_24 AC 1,245 ms
243,060 KB
testcase_25 AC 854 ms
239,888 KB
testcase_26 AC 843 ms
239,884 KB
testcase_27 AC 845 ms
240,948 KB
testcase_28 AC 322 ms
144,320 KB
testcase_29 AC 1,528 ms
347,872 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from typing import List, Tuple


# class Tree
class LCA_HLD:
    __slots__ = (
        "depth",
        "parent",
        "tree",
        "depthWeighted",
        "lid",
        "rid",
        "_idToNode",
        "_top",
        "_heavySon",
        "_dfn",
    )

    def __init__(self, n: int) -> None:
        self.depth = [0] * n
        self.parent = [-1] * n
        self.tree = [[] for _ in range(n)]
        self.depthWeighted = [0] * n
        self.lid = [0] * n
        self.rid = [0] * n
        self._idToNode = [0] * n
        self._top = [0] * n
        self._heavySon = [0] * n
        self._dfn = 0

    def build(self, root=-1) -> None:
        if root != -1:
            self._build(root, -1, 0, 0)
            self._markTop(root, root)
            return
        n = len(self.tree)
        for i in range(n):
            if self.parent[i] == -1:
                self._build(i, -1, 0, 0)
                self._markTop(i, i)

    def addEdge(self, from_: int, to: int, weight: int) -> None:
        self.tree[from_].append((to, weight))
        self.tree[to].append((from_, weight))

    def addDirectedEdge(self, from_: int, to: int, weight: int) -> None:
        self.tree[from_].append((to, weight))

    def lca(self, u: int, v: int) -> int:
        while True:
            if self.lid[u] > self.lid[v]:
                u, v = v, u
            if self._top[u] == self._top[v]:
                return u
            v = self.parent[self._top[v]]

    def dist(self, u: int, v: int, weighted=True) -> int:
        if weighted:
            return (
                self.depthWeighted[u]
                + self.depthWeighted[v]
                - 2 * self.depthWeighted[self.lca(u, v)]
            )
        return self.depth[u] + self.depth[v] - 2 * self.depth[self.lca(u, v)]

    def kthAncestor(self, root: int, k: int) -> int:
        """k:0-indexed;如果不存在,返回-1.
        kthAncestor(root,0) = root
        """
        if k > self.depth[root]:
            return -1
        while True:
            u = self._top[root]
            if self.lid[root] - k >= self.lid[u]:
                return self._idToNode[self.lid[root] - k]
            k -= self.lid[root] - self.lid[u] + 1
            root = self.parent[u]

    def jump(self, from_: int, to: int, step: int) -> int:
        """
        从 from 节点跳向 to 节点,跳过 step 个节点(0-indexed).
        返回跳到的节点,如果不存在这样的节点,返回-1.
        """
        if step == 1:
            if from_ == to:
                return -1
            if self.isInSubtree(to, from_):
                return self.kthAncestor(to, self.depth[to] - self.depth[from_] - 1)
            return self.parent[from_]
        c = self.lca(from_, to)
        dac = self.depth[from_] - self.depth[c]
        dbc = self.depth[to] - self.depth[c]
        if step > dac + dbc:
            return -1
        if step <= dac:
            return self.kthAncestor(from_, step)
        return self.kthAncestor(to, dac + dbc - step)

    def getPath(self, from_: int, to: int) -> List[int]:
        res = []
        composition = self.getPathDecomposition(from_, to, True)
        for a, b in composition:
            if a <= b:
                res += self._idToNode[a : b + 1]
            else:
                res += self._idToNode[a : b - 1 : -1]
        return res

    def getPathDecomposition(self, from_: int, to: int, vertex: bool) -> List[Tuple[int, int]]:
        """返回沿着`路径顺序`的 [起点,终点] 的 欧拉序 `左闭右闭` 数组.
        注意不一定沿着欧拉序, 但是沿着路径顺序.
        """
        up, down = [], []
        while True:
            if self._top[from_] == self._top[to]:
                break
            if self.lid[from_] < self.lid[to]:
                down.append((self.lid[self._top[to]], self.lid[to]))
                to = self.parent[self._top[to]]
            else:
                up.append((self.lid[from_], self.lid[self._top[from_]]))
                from_ = self.parent[self._top[from_]]
        offset = 1 ^ vertex
        if self.lid[from_] < self.lid[to]:
            down.append((self.lid[from_] + offset, self.lid[to]))
        elif self.lid[to] + offset <= self.lid[from_]:
            up.append((self.lid[from_], self.lid[to] + offset))
        return up + down[::-1]

    def isInSubtree(self, child: int, root: int) -> bool:
        """child是否在root的子树中(child和root不能相等)"""
        return self.lid[root] <= self.lid[child] < self.rid[root]

    def subtreeSize(self, root: int) -> int:
        return self.rid[root] - self.lid[root]

    def id(self, root) -> Tuple[int, int]:
        """返回 root 的欧拉序区间, 左闭右开, 0-indexed."""
        return self.lid[root], self.rid[root]

    def eid(self, u: int, v: int) -> int:
        """返回边 u-v 对应的 欧拉序起点编号, 0-indexed."""
        id1, id2 = self.lid[u], self.lid[v]
        return id1 if id1 > id2 else id2

    def _build(self, cur: int, pre: int, dep: int, dist: int) -> int:
        subSize, heavySize, heavySon = 1, 0, -1
        for next, weight in self.tree[cur]:
            if next != pre:
                nextSize = self._build(next, cur, dep + 1, dist + weight)
                subSize += nextSize
                if nextSize > heavySize:
                    heavySize, heavySon = nextSize, next
        self.depth[cur] = dep
        self.depthWeighted[cur] = dist
        self.parent[cur] = pre
        self._heavySon[cur] = heavySon
        return subSize

    def _markTop(self, cur: int, top: int) -> None:
        self._top[cur] = top
        self.lid[cur] = self._dfn
        self._idToNode[self._dfn] = cur
        self._dfn += 1
        if self._heavySon[cur] != -1:
            self._markTop(self._heavySon[cur], top)
            for next, _ in self.tree[cur]:
                if next != self._heavySon[cur] and next != self.parent[cur]:
                    self._markTop(next, next)
        self.rid[cur] = self._dfn


from collections import defaultdict
from typing import Callable, Generic, List, TypeVar, Dict

T = TypeVar("T")


class RerootingForest(Generic[T]):

    __slots__ = ("adjList", "_n", "_decrement")

    def __init__(self, n: int, decrement: int = 0):
        self.adjList = [[] for _ in range(n)]
        self._n = n
        self._decrement = decrement

    def addEdge(self, u: int, v: int) -> None:
        u -= self._decrement
        v -= self._decrement
        self.adjList[u].append(v)
        self.adjList[v].append(u)

    def rerooting(
        self,
        e: Callable[[int], T],
        op: Callable[[T, T], T],
        composition: Callable[[T, int, int, int], T],
        groupRoot=0,
    ) -> Dict[int, "T"]:
        """groupRoot 是联通分量的根节点."""
        groupRoot -= self._decrement
        assert 0 <= groupRoot < self._n
        parents = defaultdict(lambda: -1)
        order = [groupRoot]

        stack = [groupRoot]
        while stack:
            cur = stack.pop()
            for next in self.adjList[cur]:
                if next == parents[cur]:
                    continue
                parents[next] = cur
                order.append(next)
                stack.append(next)

        dp1 = dict({v: e(v) for v in order})
        dp2 = dict({v: e(v) for v in order})
        for cur in order[::-1]:
            res = e(cur)
            for next in self.adjList[cur]:
                if parents[cur] == next:
                    continue
                dp2[next] = res
                res = op(res, composition(dp1[next], cur, next, 0))
            res = e(cur)
            for next in self.adjList[cur][::-1]:
                if parents[cur] == next:
                    continue
                dp2[next] = op(res, dp2[next])
                res = op(res, composition(dp1[next], cur, next, 0))
            dp1[cur] = res

        for newRoot in order[1:]:
            parent = parents[newRoot]
            dp2[newRoot] = composition(op(dp2[newRoot], dp2[parent]), parent, newRoot, 1)
            dp1[newRoot] = op(dp1[newRoot], dp2[newRoot])
        return dp1

import sys
from typing import Tuple, List, DefaultDict
from collections import defaultdict

sys.setrecursionlimit(int(1e7))
input = lambda: sys.stdin.readline().rstrip("\r\n")
INF = int(4e18)


class _UF:

    __slots__ = ("n", "part", "_parent", "_rank")

    def __init__(self, n: int):
        self.n = n
        self.part = n
        self._parent = list(range(n))
        self._rank = [1] * n

    def find(self, x: int) -> int:
        while x != self._parent[x]:
            self._parent[x] = self._parent[self._parent[x]]
            x = self._parent[x]
        return x

    def union(self, x: int, y: int) -> bool:
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        if self._rank[rootX] > self._rank[rootY]:
            rootX, rootY = rootY, rootX
        self._parent[rootX] = rootY
        self._rank[rootY] += self._rank[rootX]
        self.part -= 1
        return True

    def isConnected(self, x: int, y: int) -> bool:
        return self.find(x) == self.find(y)

    def getGroups(self) -> DefaultDict[int, List[int]]:
        groups = defaultdict(list)
        for key in range(self.n):
            root = self.find(key)
            groups[root].append(key)
        return groups


if __name__ == "__main__":

    n, m, q = map(int, input().split())
    # 树中保留的边
    edges = list((a - 1, b - 1) for a, b in tuple(map(int, input().split()) for _ in range(m)))
    queries = list((a - 1, b - 1) for a, b in tuple(map(int, input().split()) for _ in range(q)))

    tree = [[] for _ in range(n)]
    uf = _UF(n)
    LCA = LCA_HLD(n)
    for u, v in edges:
        tree[u].append((v, 1))
        tree[v].append((u, 1))
        uf.union(u, v)
        LCA.addEdge(u, v, 1)
    LCA.build(root=-1)

    res = 0
    weights = [0] * n  # 特殊点的权重
    for u, v in queries:
        if uf.isConnected(u, v):
            res += LCA.dist(u, v)
        else:
            weights[u] += 1
            weights[v] += 1

    """求`原树`中每个点到可达的(连通)所有特殊点的距离之和."""

    E = Tuple[int, int]  # (distSum,size) 树中距离之和, 子树中特殊点的大小

    def e(root: int) -> E:
        return (0, 0)

    def op(childRes1: E, childRes2: E) -> E:
        dist1, size1 = childRes1
        dist2, size2 = childRes2
        return (dist1 + dist2, size1 + size2)

    def composition(fromRes: E, parent: int, cur: int, direction: int) -> E:
        """direction: 0: cur -> parent, 1: parent -> cur"""
        dist, size = fromRes
        from_ = cur if direction == 0 else parent
        count = weights[from_]
        return (dist + size + count, size + count)

    R = RerootingForest(n)
    for u, v in edges:
        R.addEdge(u, v)
    groups = uf.getGroups()
    for root, nodes in groups.items():
        dp = R.rerooting(e, op, composition, groupRoot=root)
        values = dp.values()
        res += min(d for d, _ in values)
    print(res)
0