cf1610F

更加牛逼的大佬的题解！

link

我朝，这个题解太牛逼了。

当然官方题解也有很多值得学的地方，但是这个第二个大佬的题解更接近我现在的思维模式。

先说大佬的方法

首先考虑一个点当且仅当 $$ 是奇数是才有机会是。

当然这样的点有偶数个（考虑一条边俩贡献）。

所以欧拉回路的想法油然而生，我们希望所有。

但是我们是带权的，所以直接跑不行，那么最牛逼的地方来了，直接分开考虑 $$,$$。

把 $$ 边建成两个图。

那么如果一个点 $$ 的 $$ 的边，$$ 的边都是偶数，那么他没机会了，不用管了。

如果他 $$ 边奇数，$$ 边偶数，我们就建一个虚电，虚边，代表那个 $$。

如果他 $$ 边奇数，$$ 边奇数，那么就必须有一个 $$ 边和 $$ 边匹配，那么我们建出一条 $$ 到 $$ 的边，代表走进来的 $$ 边匹配走出去的 $$ 边。

如果他 $$ 边偶数，$$ 边奇数，我们不想管他，但是他得匹配，所以也给他的 $$ 边建虚边。

这个组合构造思维牛逼炸了。

---

接下来是欧拉回路的另一种视角，消“环”。

在这里体现的就是类似增量法的思维。

找到 $$ 使得 $$ 那么我们认为对于 $$ 这两条边抵消了，但是对于 $$,$$ 并不是，所以我们加入 $$ 这条边，继续增量构造。

正确性就是最后一定是一堆二度点组成的图形，如果有一度点，就是链，否则是环，这样好考虑了，所以原问题有解。

值得注意的是 我们并不是在匹配，而更加类似在“消除贡献”，所以正确性比较显然了 。。。。

是一个好题！