1.P5344 【XR-1】逛森林
先用并查集维护连通性。
考虑如何建立传送门：
如果使用树剖，强行线段树优化建图，那么空间开销过大，已经有 2 只 \(\log\)。
考虑使用倍增优化建图，对于一个点向上 \(2^k\) 的祖先的形成链都建一个点，模仿 LCA 的过程建边，空间是 1 只 \(\log\).
如果我们模仿 ST 表，那么就没有 \(\log\) 了。
即可通过此题。
2023.8.4 杂题
发布时间 2023-08-04 21:52:01作者: GloriousCc
先用并查集维护连通性。
考虑如何建立传送门：
如果使用树剖，强行线段树优化建图，那么空间开销过大，已经有 2 只 \(\log\)。
考虑使用倍增优化建图，对于一个点向上 \(2^k\) 的祖先的形成链都建一个点，模仿 LCA 的过程建边，空间是 1 只 \(\log\).
如果我们模仿 ST 表，那么就没有 \(\log\) 了。
即可通过此题。