题解：P11095 [ROI 2021] 旅行 (Day 2)

模拟赛两次出了这题，可惜本人实力太低了，拼尽全力无法战胜。

题解看了一个多小时才看懂，这里讲下我的思路。

首先我们看到最小值，是不是很容易想到最小生成树？其实这很对，只是一些特殊情况会出错，比如下图。

有了这张图是不是就很显然了。

总结下特殊情况，一个是环，另一个是一个点有两种方式到根，他们的最小值不同。

考虑怎么去特判这种情况。

首先我们建出最小生成树，按照最小生成树的思路，从小到大枚举边。

现在我们从小到大加边，那么当前每条路径的最大值就先钦定为枚举的边。

然后如果这条边是最小生成树上的边，就更新深度深的子树的答案（因为这有这颗子树内的点才能经过这条边，这个东西可以直接用线段树做）。

如果不是，那么现在有两种情况。一个是两个点是一个边双内的，那么这条边没用，不管他。

如果只是普通联通块，那么是不是这个环可以概括成他们两个点到他们公共祖先上的所有点？所以我们拿个并查集存小联通快，然后暴力跳，缩点即可。缩完的点，答案就是他们当中到根最小的边加上枚举到的边的权值。

然后每篇题解都告诉你，就是在每个点首次和根相连时清空答案，实际上是强制赋值为这个点到根的最小值加枚举的边。

然后我们有两颗线段树，第一颗是用来存每个点到根的边的最小值，另一颗树才是答案。

并查集也要开两个，第一个是联通块，第二个是边双。

省选加油。