题解：P13342 [EGOI 2025] 风力涡轮机

首先考虑 $l_i+1=r_i$ 的部分分，相当于查询最小生成树路径上的最大边，也就是 $l_i,r_i$ 在重构树上的 lca。

考虑全部数据，相当于找出重构树上 $r_i-l_i+1$ 个叶子节点点点权前 $r_i-l_i$ 大的两两 lca，注意到重构树上每个点代表一次合并，因此 $k$ 个叶子点恰有 $k-1$ 个 lca，从而问题变为求解编号在 $[l_i,r_i]$ 内点的两两 lca 点权和。

此时我们考察重构树某个点何时会被贡献到答案里，注意到每个点 $u$ 有且仅有两个儿子，不妨记作 $s_1,s_2$，该点会被贡献到答案当且仅当 $s1,s2$ 的子树内均存在编号在区间 $[l_i,r_i]$ 的点。

也就是说，若存在 $x\in \texttt{subtree}(s_1),y\in \texttt{subtree}(s_2)(x<y)$，所有包含 $[x,y]$ 的询问都会获得 $w_u$ 的贡献，其中 $w_u$ 是 $u$ 的点权（注意该贡献不能累加，所以对于每个节点要将贡献范围去并）。

仿照铃原露露的手法即可求出支配点对，扫描线配合树状数组完成后续工作即可。没有做过铃原露露的同学可以继续阅读。

考虑画出 $l-r$ 平面（横轴为 $l$，纵轴为 $r$），平面上一个点代表一次询问，那么一个 $(x,y)$ 的贡献区间相当于左上的 2-side 矩形。由于贡献是覆盖的，因此若当 $x$ 固定时，$y$ 只需考虑尽可能小的那个即可，因此考虑启发式合并维护子树叶子节点编号，合并时将被合并点与其对应的前驱后继凑成 $(x,y,w_u)$ 的贡献对，扫描线处理，贡献对的数量和启发式合并的复杂度是同阶的。

另外注意由于对于每个点 $u$，其贡献是不能叠加的，所以对 $l$ 从 $n$ 到 $1$ 更新时，还需额外记录每个 $u$ 的最小 $r$ 值，用树状数组实现单点修改，区间查询即可。

综合时间复杂度 $\mathcal{O}(m\log m+n\log^2 n+q\log n)$。

代码很好写，如果实在需要私信找我要。