考虑这样一个问题：有两棵边带权的树，以及若干条两个端点分别在两棵树上、有边权的边。求最小生成树。多次询问，每次给出两棵树之间的边，要求回答询问的复杂度与给出的边数相关。
一个暴力做法是动态最小生成树，每次尝试用新加的边替换掉原来的树上的边。
我们称连接两棵树的那些边的端点为关键点。观察到，对于树上的某条路径，如果任意的一对关键点之间的路径都包含它或者与它无交，那么这条路径上至多有一条边被新加入的边替换掉。因为一旦这条路径的某条边被替换掉（也就意味着这条路径被断开了），那么它将不再与任何的关键点之间的路径有交。
这意味着我们可以对关键点建虚树，虚树上两点之间的边权为它们路径上边权的最大值，然后进行之前的动态最小生成树做法。也可以直接 Kruskal，因为虚树上的点数不超过关键点数量的二倍。
回到本题，可以用上面说的方法求出每个前缀、后缀的最小生成树，对于每个询问，把 $[1,l_i)$ 与 $(r_i,n]$ 合并起来即可。时间复杂度 $O((m+q)n\log n)$。
实现细节可以参考代码。