思路

自环对距离的影响为:增大路径的权值,所以自环没有作用,可以删去
图上的环对距离的影响为:因为我们最后总是会选择较短的路,因此所有环上的最大边可以删去
重边相当于一种特殊的环,选择最小的那一个留下就行

那么经过处理以后,这个无向图貌似变成了一颗最小生成树?

不用怀疑,这就是最小生成树森林!

那么怎么证明呢?

我发现一个类似的算法:反向删除构建最小生成树
构建过程具体如下:按边权从大到小依次删去边,要是不影响连通性则删去,最后得到最小生成树

应用在这一题,我们破环相当于删去了不影响连接性的一条边权较大的边,所以最后得到的就是最小生成树

而我们需要判断距离是否一样,那么只要其最小生成森林一样就行

因为此处已经得出结论,只要算出最小生成树,问题就解决了一半,所以接下来正向考虑每一条边加入图中对距离的影响

在两张图中同时进行最小生成树算法,要是这两条边的边权一样,连起的区块相同,那么所有点在两张图的距离仍对应相等

证明(DeepSeek):

这是因为在按权值从小到大逐步添加边的过程中，每一步合并相同的连通分量（区块），使得任意两点首次连通时的边权值相同。而两点间的最小瓶颈距离正是它们首次连通时的边权值（若始终不连通则为无穷）。因此，对于任意两点，它们在两张图中的距离相等。

但是在算法实现中,这是比较困难的,因为可能构建顺序不完全一致.

方法是把距离相同的边同时操作,每一次操作观察图的连通情况,由此来判断得到的生成树是否一样

按照之前的结论,重边和自环对答案没有影响,因为最后算的反正是连通性,所以不需要特殊处理,这样就简化了操作

比赛中和赛后补题中出现的思路问题

在比赛时,我们想到了构建生成树来简化计算,但是停留在每一步相等才行,并没有想到只需要判断连通性就行

最后是计算区块信息的问题,我赛时的想法是通过计算异或和区分每个区块,每个点给予随机值作为初始哈希值,这是对的,但是在赛后计算总连通性时出问题.方法是结合加法,每个区块的和为总哈希

所以最后代码上除了还要学习一下dsu标准写法外没有大问题

总之是一道好题,已严肃补完