最小生成树 MST

P5994 [PA2014] Kuglarz

考虑连边 \(i,j\) 表示花费代价知道区间 \([i,j)\) 的奇偶性．

容易发现 \(i,j\) 联通就可以发现表示出 \([i,j)\)．

考虑最终局面，一定要推出每个 \([i,i+1)\) 的奇偶性．要求每对 \([i,i+1)\) 联通．即整张图联通．

最小生成树

k条白边最小生成树

二分附加权．

注意最后的方案，MST 上可能存在代价为 \(w\) 的若干条边可能是白边可能是黑边．不好判断．

考虑优先选白边．在白边数量 \(\ge k\) 的时候记录二分答案．

• 合法答案存在于白边 \(\ge k\) 的时候．
• 保证白边 \(\ge k\) 的时候，附加权越大是一定能构造出合法答案．

树的重心

定义

• 到所有点的带权距离之和最小的点（定义一）
• 使得最大子树大小最小的点（定义二）

如何从定义一推出定义二呢？一个点若存在一个大小大于 \(\displaystyle \frac{n}{2}\) 的子树，朝那个子树走一定会使距离和变得更小．

性质

• 两个树相连，新重心在原来的两棵树重心的路径上．

无向图 DFS 树

从 \(u\) 开始搜索，遇到没有访问过的点就当自己的儿子 \((1)\)，并继续搜索．否则不管 \((2)\)．

\((1)\) 叫做树边．
\((2)\) 叫做非树边（返祖边）．

无向图 DFS 树有一个很好的性质：一个点子树中的点互相没有边．

可以解决一些奇怪的题目．

[BZOJ4878]挑战NP-Hard

建出任一棵 DFS 树，若树深度 \(> k\)，解决 subtask 2；否则每层染不同的颜色，解决 subtask 1．

拓扑排序

最短路

严格次短路

结论：严格次短路上一定存在一条边，使得它不属于原来的 任何一条最短路．枚举次短的边是哪一条即可．
考虑最短路 DAG，若严格次短路经过的全部都是属于某一条最短路的边，它是最短路 DAG 的一条路径，它就是最短路！

换一种严谨的证明方式，记 \(D_i\) 表示 \(1 \rightarrow i\) 的最短路长度．假设一条严格次短路 \(Path\) 的所有边都存在于某一条最短路，则有 \(\forall e(u \rightarrow v,w) \in Path,D_v=D_u+w\)．那么顺序考虑 \(Path\) 中的每一个点，最后可以发现 \(\displaystyle \sum_{e\in Path} w=D_n\)．

01 BFS

和我 基础图论 中的内容不谋而和．

当然学到了一点奇技淫巧．比如若存在 \(k\) 种边权，然后 \(k\) 很小，存在一种很轻便的空间复杂度和最短路 最长长度相关 解题方式：维护堆可以桶排开 最长最短路长度 个 vector．然后每次遍历最短路长度最短的点即可．