图论部分(2025.6.25)

注意

在考试时注意时间，用基本技巧（倍增，dfs序，树上差分）解决的问题就不要使用高级数据结构（树链剖分，线段树合并和dsu on tree）

倍增维护信息时要注意lca周围

一个信息是幂等的，就是说这个信息在合并后任是自己，比如最大值算多了答案、仍然正确

这样就可以把信息合并次数减少，比如将一条链拆分成

2^k

长的部分，这样就只用

O(1)

的时间来合并

可将加链转化为两点的加，最后到根一次算出来

有

Prim

(每次扩展权值最小的边) ,

Kruskal

(边从小到大排序), $Boruvka$ （每次找一个点或连通块，在所有出边中找一个权值最小的出边）（思想非常重要）。

对于无向图，dfs 树具有不存在横叉边的性质。

推论：dfs 树附带了若干个独立集：叶子是独立集，同深度的点是独立集。

最小生成树具有可合并性。特别地，如果涉及到的点很少，甚至可以建虚树来合并。合并时只用合并少量两边的点，不用合并所有的点。

略

注意 2-sat 只能解决布尔方程组，所以要将其他的限制转化为布尔方程组，常将变量

x_{i,j}

设为

a_i \le j

为真或假，然后进行表示

注意，必须在回溯时进行边的加入，否则会错

欧拉回路有两个性质：