E. Journey
显然，若原无向图存在欧拉回路（即所有点的度数均为偶数），则一定可以从点 \(1\) 出发，经过每条边恰好一次并回到点 \(1\)，此时花费的代价即为所有边的边权总和，一定是最优解。
否则，存在某些点的度数为奇数，无法生成欧拉回路。但我们可以思考：若在每一对奇度数点之间添加一条边，使得最终所有点的度数均为偶数，那么就会生成新图，且是欧拉回路，多出来的代价就是添加新边的权值之和。而总度数一定是偶数，奇度数的点的数量也是偶数。于是，我们考虑找到配对每一对奇度数点的方式，使得总代价最小（类似二分图最小匹配）。
新添加边的权值即为 \(u,v\) 之间 transfer 的最小花费，即 两点之间的全部路径中，所有可能的最大编号的边对应的最小边权。
考虑如何计算对于任意两点之间的所有路径，可能经过的所有的边最大编号：按照边的编号升序，建立原图的 Kruskal 重构树。那么，对于 \(u,v\) 两点在重构树中的 LCA 对应的边，就是 \(u,v\) 之间的所有路径中，路径最大编号的最小值； 而考虑 Kruskal 重构树中的每个非叶节点对应的子树：对于该子树内的任意两点，该非叶节点对应的边一定可以成为这两个点的某条路径的边最大编号（题意说可以不是简单路径，因此只要是包含这两个点的子树就符合要求）。因此我们得到结论：任意两点 \(u,v\) 的全部路径的所有可能的最大编号，对应的是 Kruskal 重构树上从根节点到 \(lca(u,v)\) 路径上的所有点代表的边。
注意在建重构树的过程中，若加边前发现对应的两个端点已经在同一连通块中，不要舍弃这条边（因为该边权值可能更小，可能会存在取这条边的情况，不能按照传统方法直接舍弃），而是要新创建该边对应的结点，并只连接与这两个点所在 Kruskal 重构树的根结点这一条边。这样可以保证按照上述算法流程进行是正确的。
建好重构树后，预处理对于每个点，根结点到该点的路径上所有结点权值的最小值。然后考虑最优匹配方式：对于任意两点，最优连边一定是选择两点的 LCA（由于经过了前面的预处理，此时该点代表本身及所有祖先结点权值的最小值）；因此我们有了一种贪心解法：dfs 自下而上结算重构树上每个结点对应子树的答案，若发现该子树内还有 \(cnt\) 个结点未匹配，则要尽可能地先匹配可以匹配的 \(\lfloor \frac{cnt}{2}\rfloor\) 对结点，剩下的结点再留给祖先结点匹配。
具体实现见 code。
code