2024.9.16 上午 总结（考 DS）

T1

我的做法：

• 合并 -> 并查集。类似建 Kruskal 重构树。询问跑 LCA。

• 注意并查集合并要把两个根都变成一个新点的儿子，而不是把一个作为另一个的儿子。（可能类似建 [边]（？） Kruskal 重构树）

• 要特判询问时 \(x = y\) 的情况（好像是输出 \(0\)）。

lzh 的做法：

• 连出一棵树，边的边权是 它是第几条边。每次询问问的是一条链上的 \(\max\)。用树剖做。

• 其实也可以建这棵树的 Kruskal 重构树（[边]（？））来做。这个重构树好像就是我的做法里建出来的树。

xwb 的做法：

对操作（加边）分块（块长是根号）。

记一下[每个块结尾处]（？？？）的 fa 数组（前面的边都加上时）。通过这个找每个询问的答案是在哪个块里的。

对每个块里的询问一起处理。在每个块里暴力走，每走一步暴力对这个块里的所有询问判是否可行即可。

题解的

咕咕咕。