有趣的小清新数据结构题。
首先考虑这个合并每次找到最小的边的过程很类似于 Kruskal 最小生成树的合并过程，只不过每次是钦定了合并一个大联通块和一个点。由于需要从不同的起点开始考虑，也就是需要多次处理这个类似 Kruskal 的过程，自然想到 Kruskal 重构树。我们考虑建出 Kruskal 重构树，下面考虑如何在这个过程中维护出从每个点开始出发，合并到目前的答案。
考虑一次合并两个联通块的过程，我们合并两个联通块，相当于从这两个联通块中伸出来边权最小的边就是当前这条边了，也就是说，以这两个联通块内部的任何一个点为起点，合并完子树之后下一条合并的边自然就是这条边，再接下来合并的边就是另一个子树内以这条边的另一个端点为起点需要合并的边。发现这种操作对于整一个子树内需要进行的处理是相同的，所以可以想到线段树来维护区间操作。我们每次取出从这条边两个节点出发这个子树内部的答案，然后把这些操作和当前这条边的贡献挂到另一棵子树上。下面来考虑如何用一个支持快速合并的 tag 来维护这种操作。
考虑维护一个 pair $(mul,add)$ 表示如果初始值为 $x$，经过这个 tag 之后的值是 $mul*x+add$。那么两个 tag 的合并是容易的，具体来说设两个 tag 分别为 $(mul1,add1)(mul2,add2)$，那么新的 tag 就是 $(mul1*mul2,add1*mul2+add2)$，所以就解决了上述信息的快速维护，然后直接用线段树维护这个 tag 就做完了。
写代码的时候注意区分原图中的点和建出 kruskal 重构树上的点编号和编号的 dfs 序，不要写混了。
标签：联通,Pt,T2,Kruskal,合并,USACO,tag,维护,考虑 From： https://www.cnblogs.com/Harry27182/p/17924771.html