[HNOI2019]校园旅行

校园旅行

题解

首先有一个明显的暴力做法。将所有长度为1/2的回文串塞入队列,每次取出队首转移即可。这样每对点都会被拓展一次(由于一对点只有两种状态,存在/不存在),复杂度$(\sum d)^2=\mathcal O(m^2)$。

那么接下来要做的事情是减少边的数量。考虑把一个路径,分为许多条边,每条边必然是00或者01或者10或者11。考虑将一条路径划分为一些段,每段路径类型相同。那么对于这若干段,只要每段的奇偶性相同即可,因为可以通过来回走一条边增长数量。因此数量不成问题,只有奇偶性会有些问题。

下面将使用魔法:如果只考虑边的端点权值相同的边(其他边就当不存在),那么必然是若干个全职相同点组成的连通块。我们重构这个连通块,只要保证从任何一个节点出发,到其他节点经过点的数量奇偶性可以与原图的奇偶性相同即可。可以发现有一些图的样子满足无论如何走,节点数量奇偶性都不变。这样的图是二分图。那么对于二分图,可以考虑保留这棵树的一颗生成树。否则,说明必然存在奇环,走一次就可以改变一下奇偶性,所以保留一棵生成树并添加一条自环即可。至于边的端点权值不同的边,必然是个二分图,因为他已经给你染好色了。所以保留一棵生成树即可。

这里引用EmptySoulist的代码:

发表评论