有可能不经过那条最小边。
by sevenki @ 2024-02-04 08:56:59
@[sevenki](/user/1014573) 能详细说说吗，蒟蒻有点不懂。
by gghack_Nythix @ 2024-02-04 09:26:56
@[sevenki](/user/1014573) 但是假设我们走了最大生成树，明显要经过这上面的所有边啊，根据题意来说，我们确实应该记录最大路径中的最小，如果不经过那么去别的边上只会更劣（雾
by gghack_Nythix @ 2024-02-04 09:45:06
比如最大生成树上的两个相邻节点中间边权为114，而最大生成树上更远的还有一条边是113，而事实上这两条相邻节点的路径权最小值就是树上点对之间权最小值，只需要经过114，不需要经过113，因此113无法对答案造成贡献 @[gghack_Nythix](/user/895690)
by sevenki @ 2024-02-04 10:18:45
@[sevenki](/user/1014573) 哦懂了懂了，就是说我统计的时候这两点一定是联通的，那么就只需要走最大生成树上那个大一点的就可以保证一定走到，是这样吗？
by gghack_Nythix @ 2024-02-04 10:21:58
@[gghack_Nythix](/user/895690) 并不是这样理解的。统计的时候只要考虑两点在最大生成树上的路径边权就行了。因为最大生成树首先保证了走最大生成树的方案最优，然后走最大生成树实际上不用每个点都经过一次，两点在树上有且只有一条简单路径，只需要考虑这条经过的路径上的边权最小值就可以了。
by sevenki @ 2024-02-04 10:24:57
@[sevenki](/user/1014573) 啊，但是如果要考虑这条路径上的最小值又是怎么计算呢（
by gghack_Nythix @ 2024-02-04 10:28:57
@[sevenki](/user/1014573) 我刚刚下载了一下测试点，每一次的最大生成树影响到的总是两个相邻的点(一条边)，于是就可以考虑记录一下$max$，这样子走的时候就往$max$上面走
by gghack_Nythix @ 2024-02-04 10:30:39
@[sevenki](/user/1014573) 刚刚画了个图，懂了，就是说因为我们已经在跑最大生成树了，所以说后面的节点一定更加劣，所以记录第一次能到达的点就可以了。
by gghack_Nythix @ 2024-02-04 10:40:46
@[sevenki](/user/1014573) 感谢神犇,orz%%%，同时关注了。
by gghack_Nythix @ 2024-02-04 10:42:13