cf1610F

更加牛逼的大佬的题解！

link

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

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

先说大佬的方法

首先考虑一个点当且仅当 \(\sum w_{u,v}\) 是奇数是才有机会是。

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

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

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

把 \(1,2\) 边建成两个图。

那么如果一个点 \(x\) 的 \(1\) 的边，\(2\) 的边都是偶数，那么他没机会了，不用管了。

如果他 \(1\) 边奇数，\(2\) 边偶数，我们就建一个虚电，虚边，代表那个 \(+/-1\)。

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

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

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

---

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

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

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

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

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

是一个好题！