会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
使用并查集重构树与奇度点配对。
首先，每条链路实地巡检一次的费用固定为 S=∑i=1qci。重复实地经过一条非自环链路，可以改为沿该链路调度专线，费用不增加；重复经过自环则可以直接省略。因此只需考虑每条链路实地巡检恰好一次。原图连通，要形成从节点 1 出发并回到节点 1 的欧拉回路，只需用专线将所有奇度点两两配对。
关键在于专线票价。按编号依次加入链路，设 Ci 为加入第 i 条链路后、包含该链路的连通块。对于 Ci 内任意两个不同节点，都能选择一条经过第 i 条链路、且不经过更大编号链路的路径，所以可以支付 ci 进行传送。
据此按编号建立并查集重构树：原节点为叶子；链路连接两个不同连通块时，新建父节点并记录费用 ci；若两端已经连通，则用 ci 更新当前连通块对应树节点的最小费用。由于祖先连通块内的专线也能用于子连通块，按树节点编号从大到小传播最小费用，得到 best[v]。任意两点间的最低专线费用，就是它们在重构树中的最近公共祖先对应的 best 值。
