Kruskal 重构树和 LCA
CF1706 小总结
其实都会做,但是各种各样的原因导致了没在场上 AK
ABC
A 题没考虑清楚就在写,WA 了一发样例,然后慢悠悠调好交上去过。
B 题愣了一会儿,弄了个伪 DP 上去,稍微有点磨蹭,但还好。
C 题做得无可挑剔。
D
D 题先想到可以枚举一个端点,二分另一个,
后面想到其实对 min 分类限制更多。暴力算
换一种思路考虑,还是枚举
对于一个
E
E
题在考场上想到了可以类似整体二分的做,先给所有的二分,然后再合并一次,查询每一个询问是否可行。查询的维护可以
dsu on tree 带一个维护线段的 set,复杂度
后面发现可以将询问直接塞进 dsu 的过程中,但是处理询问只能处理较小的那一边,如果是小的合到大的上面去,此时询问挂在大的上面,会非常的恼火。于是就把询问拆到两个上面去,又发现可能两个询问会在合并时变成一个但是还没解决,所以合并的时候如果变成一个就又找了一个还没合并的把询问扔上去。
然后又 TLE 了,赛后仔细分析复杂度,发现不对劲,比如有个
然后想到可以把线段合并的过程记下来,这个就是严格
其实 E 题和最近做的题都暴露出几个问题,思维模式僵化,没有办法 Think out of box,同时代码中常常犯一些不容易注意到的小错误,依赖数据调试。
Sum up
关于代码小错的问题,我觉得一边写一边静态查是一个比较理想的解决方案,先认真核实思路的正确性,再检查代码和思路是否一致,同时可以在关键点插入数据输出。
思维上的问题,估计还只有多做题。
收获 1:Dsu on tree 的复杂度理解
Dsu on tree,复杂度证明的过程是这样的:考虑一个点的权值
因此,权值的构成不影响其时间复杂度
如果在合并的时候进行了额外的对
Kruscal 重构树的应用和连通性
E 题可以用 Kruscal
重构树做,具体的,先做最小生成树,顺便合并点,现在一个连通块就是一个点,合并两个连通块时,新建一个点,点权为这条边的权值,作为被合并的两个点的父亲,任意两个点联通的时最小权值就是它们的
lca,然后区间 lca 应该都会。事实上甚至没有必要做区间 lca,我们考虑
已经知道这个性质了,那么,将询问放到 dsu 合并过程中的方法也不难写了,合并时处理其中一个询问即可。
LCA 的一些性质
从 2 中的性质,我们总结出了一些 LCA 的共有性质。
设树上一个点集为
若
否则,
对于
对
由 Lemma 1.1,有
- 若满足
,对于 ,即 ,结论成立。 - 若不满足
,记 ,则有 ,因此对于 ,结论仍然成立。
证毕。
记
对三个元素
由 Theorem 1.2,
假设
记
因此
证毕。
对于序列
归纳证明,设对
由 Theorem 1.2,
由 Lemma 2.1,Theorem 1.2,
因此定理对
证毕。
对于序列
有
由 Theorem 2.1 ,
由 Theorem 1.1,