2023.8.4 杂题
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的点+纯粹的环\)
考虑每删一个点都会先删两条边再加一条，边的数量也迎刃而解。
考虑如何维护纯粹的环数量，我们用加权并查集维护集合内点的数量和二度点的数量，
若二者相同，那么就是“纯粹的环”。
3.P3573 [POI2014] RAJ-Rally
考虑删除一个点会使得什么路径会改变。
如果这个点拓扑序为 \(x\)，若存在一条边 \((u,v),u<x<v\) 那么就不会受影响。
因为拓扑序是递增的。
考虑一条边的贡献，我们算出强制经过这条边最长路，可以正反两次拓扑求出。
那么这条边 \((u,v)\),\(x\in[u+1,v-1]\) 的点都可以被贡献，那么区间取 \(\max\)，
最后求最小值即可。