按权值从小到大的顺序加边，第一次使得两询问点的连通块相邻时，最后一条加入的边的权值即为答案。对每个连通块维护边集和询问的集合，启发式合并即可。
时间复杂度 $O((n+m\log m+q\log q)\cdot \log n)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
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.