1.P5344 【XR-1】逛森林
先用并查集维护连通性。
考虑如何建立传送门:
如果使用树剖,强行线段树优化建图,那么空间开销过大,已经有 2 只 \(\log\)。
考虑使用倍增优化建图,对于一个点向上 \(2^k\) 的祖先的形成链都建一个点,模仿 LCA 的过程建边,空间是 1 只 \(\log\).
如果我们模仿 ST 表,那么就没有 \(\log\) 了。
即可通过此题。(码量过大)
2.P4350 [CERC2015] Export Estimate
离线。首先先将边权排序,然后从大到小加边,即可避免删除操作。
我们考虑什么点会被删掉。
1.度数为 0
2.度数为 2 且最后不删成自环。
这是因为如果有一个纯粹的环(所有点度数为 2),这样的话最后只能删成自环。
但是如果有一个点连向外面,整个环都会被删掉,因为总有点度数为 2。
那么最后点的数量是 \(n-度数为0的点-度数为2的点+纯粹的环\)