結果
| 問題 |
No.922 東北きりきざむたん
|
| ユーザー |
 草苺奶昔
|
| 提出日時 | 2023-03-28 16:24:34 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 11,981 bytes |
| コンパイル時間 | 325 ms |
| コンパイル使用メモリ | 82,816 KB |
| 実行使用メモリ | 203,968 KB |
| 最終ジャッジ日時 | 2024-09-20 06:07:32 |
| 合計ジャッジ時間 | 21,880 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 7 WA * 16 RE * 3 |
ソースコード
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, Dict, Generic, List, TypeVar
T = TypeVar("T")
class RerootingDict(Generic[T]):
__slots__ = "adjMap", "_allVertex"
def __init__(self):
self.adjMap = defaultdict(list)
self._allVertex = set()
def addEdge(self, u: int, v: int) -> None:
self.adjMap[u].append(v)
self.adjMap[v].append(u)
self._allVertex |= {u, v}
def rerooting(
self,
e: Callable[[int], T],
op: Callable[[T, T], T],
composition: Callable[[T, int, int, int], T],
root: int,
) -> Dict[int, "T"]:
parents = {v: -1 for v in self._allVertex}
order = [root]
stack = [root]
while stack:
cur = stack.pop()
for next in self.adjMap[cur]:
if next == parents[cur]:
continue
parents[next] = cur
order.append(next)
stack.append(next)
dp1 = {v: e(v) for v in self._allVertex}
dp2 = {v: e(v) for v in self._allVertex}
for cur in order[::-1]:
res = e(cur)
for next in self.adjMap[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.adjMap[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
from typing import Dict, Set, Tuple, List
INF = int(4e18)
if __name__ == "__main__":
from collections import defaultdict
from typing import DefaultDict, List
class UnionFindArray:
__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
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
return (dist + size + 1, size + 1)
n, m, q = map(int, input().split())
adjList = [[] for _ in range(n)]
edges = []
uf = UnionFindArray(n)
LCA = LCA_HLD(n)
for _ in range(m):
u, v = map(int, input().split()) # 树中保留的边
u, v = u - 1, v - 1
adjList[u].append((v, 1))
adjList[v].append((u, 1))
edges.append((u, v))
uf.union(u, v)
LCA.addEdge(u, v, 1)
LCA.build(root=-1)
res = 0
toCenter = defaultdict(set) # 每个连通分量内需要到飞机场的点(特殊点)
for _ in range(q):
a, b = map(int, input().split()) # 移动的起点和终点
a, b = a - 1, b - 1
if uf.isConnected(a, b):
res += LCA.dist(a, b, weighted=False)
else:
toCenter[uf.find(a)].add(a)
toCenter[uf.find(b)].add(b)
def getDistSumToSpecials(
edges: List[Tuple[int, int]], specials: Set[int], root: int
) -> Dict[int, int]:
"""求`树`中每个点到特殊点的距离之和."""
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 = 1 if from_ in specials else 0
return (dist + size + count, size + count)
R = RerootingDict()
for u, v in edges:
R.addEdge(u, v)
dp = R.rerooting(e, op, composition, root=root)
return {k: v[0] for k, v in dp.items()}
groupEdges = defaultdict(list) # 每个连通分量内的边
for u, v in edges:
groupEdges[uf.find(u)].append((u, v))
groups = uf.getGroups()
for root, nodes in groups.items():
dp = getDistSumToSpecials(groupEdges[root], toCenter[root], root)
res += min(dp.values(), default=0)
print(res)