按权值从小到大的顺序加边，第一次使得两询问点的连通块相邻时，最后一条加入的边的权值即为答案。对每个连通块维护边集和询问的集合，启发式合并即可。
时间复杂度 $O((n+m\log m+q\log q)\cdot \log n)$。
QOJ.ac
QOJ
Discussion #330 for Problem #6800. Girlfriend
Type: Editorial
Status: Open
Posted by: jiangly
Posted at: 2025-12-14 07:07:00
Last updated: 2025-12-14 07:07:03
题解
Comments
No comments yet.