只要不失去你的崇高,整个世界都将为你敞开。

喜报：本人在写完本文后，由于网站自动注销，且文章没有保存，成功丢失了全稿。现在这篇是本人又码了一遍得到了。令人忍俊不禁。

注意到 $f$ 只与原图的奇/偶最短路有关，那么每个点在两个图上的奇/偶最短路应该都是相同的。

若原图是二分图，那么答案为任意一棵生成树。

否则，所有点的奇/偶最短路均存在，记作 $(x,y)$。又发现两者的顺序无影响，于是不妨令 $x \lt y$。

考虑一个点 $(x,y)$ 的连边方式：

1. $(x-1,y-1) \to (x,y)$.

2. $(x-1,y+1) \to (x,y) \gets (x+1,y-1)$.

3. $(x-1,x+2) \to (x,x+1) \gets (x,x+1)$.

实际上③是②在 $y=x+1$ 时的特殊情况，但是很有用。

注意到②③中 $x+y$ 是不变的，这启示我们将点按照 $x+y$ 分层。而①中又有 $y-x$ 不变，这启示我们在每层中按照 $y-x$ 升序。

此时我们的连边方式就变得直观了。考虑在以 $x+y$ 为横轴，$y-x$ 为纵轴的坐标系中，我们的连边方式体现为：

1. 向正下方的点连边（如果存在）。

2. 向左右的点分别连边 （如果存在）。

3. 每层最右侧的点，若是 $(x,x+1)$，那么它可以和自己连边。

可以画个图理解一下。

显然①是最划算的，但问题是 $(x-1,y-1)$ 可能不存在，此时我们必须使用②③。

分析一下②③，可以发现本质是将一条链不断往右延伸，并最终在 $(x,x+1)$ 内部消化。显然我们应该将链两两配对，来省去一般代价。

现在我们来分讨一下策略。

考虑点 $(x,y)$，记它包含 $cnt$ 个节点，令 $(x-1,y-1)=fa,(x-1,y+1)=lst$，那么：

1. 若 $fa$ 存在， $lst$ 不存在。那么就直接全连①即可，不向后面留任何链头。

2. 若 $fa$ 不存在， $lst$ 存在。那么就只能全连②，并向后留 $cnt$ 个链头。

3. 若 $fa$ 与 $lst$ 均存在。分析一下可以发现，我们应该让前面的链头尽量分散地连到当前点，再向右传递下去。如果还有剩的，就用①连。

4. 若 $fa$ 与 $lst$ 均不存在。显然这是不可能出现的，因为原图的存在实际上已经为有解做了保障。

可以发现，只有②会产生链头。

最后我们会到达本层的最右端。

若它为 $(x,x+1)$。记它后面还有 $c$ 个链头，通过两两配对，只需要 $\left \lceil \frac{c}{2} \right \rceil $ 的代价。

否则，因为有解，本层一定不存在任何链头。

其实还没完，由于节点 1 并不需要连边，需要特殊处理。要留意一下节点 1 有自环的情况。

可以用 map 之类的实现，时间复杂度 $O(n\log n)$。