Unification

很丁真的一个题，权当复习下树上倍增的写法了 考虑先给图求出一个MST，那么很容易发现对于每条非树边\((u,v)\)，它的权值必须严格大于MST上\(u,v\)之间所有边的权值，否则就可以用这条非树边来替换某一条树边 因此直接倍增维护树上两点间最大边权即可，复杂度\(O(n\log n)\) #in ......

给定一个有n个点，m条边的无向连通图，每条边有边权。 定义一次操作为：选择一条图中的边，并将其权值+1。 试求最小的操作次数，使得操作后的图的最小生成树是唯一的。 1<=N<=2e5 n-1<=m<=2e5 如上图所示，设加入一条不在最小生成树上的边，例如(4,5)这条边 则这条边的值必然要大于4到 ......