schtonn

前置知识

存图方式（邻接表，邻接矩阵），并查集。

引入

生成树，就是从一个包含 \(n\) 个节点的无向图中选中 \(n-1\) 条边，使得这些边构成一棵树，并包含图中的所有节点。

最小生成树，就是找到一种生成树，使得这个生成树的边权和最小。

前置知识

哈哈，简单到爆，没有。

引入

并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。

前置知识

必备：存图方式（邻接表，邻接矩阵），dfs序。 维护：线段树、树状数组、BST。

引入

树链剖分，简单来说就是把树分割成链，然后维护每一条链。一般的维护算法有线段树，树状数组和BST。复杂度为\(O(\log n)\)。

\(\texttt{Is KaTeX working?-IT WORKED!NICE!}\) \[a^b\] \[\left(\dfrac{a}{b}\right)\]

\(\alpha_\beta = \gamma_\delta\)