首先考虑暴力M^2dp,考虑回文串是可以从回文中心每次在两边拓展的,设\(f_{i,j}\)为\(i\)到\(j\)的路径是否是回文串,bfs转移,枚举两点出边,如果两个新端点颜色相同就更新
然后这个大暴力可以优化到70',就是先枚举一端的相邻的点,然后注意到因为固定了那个相邻的点,对应的另一个用来拓展的端点个数是\(O(n)\)的,然后转移是\(O(m)\)的,所以总复杂度为\(O(nm)\)
然后考虑减少边数.对于一个同色的连通块,如果这个连通块是二分图,那么我们只要保留它的一个生成树就好了,因为对于一端在上面的子路径,在生成树上可以使用反复横跳走出同奇偶的子路径(另一边也同理),并且不会影响答案;如果不是二分图,那么就有奇环,有奇环就可以改变路径长度奇偶性,所以在生成树上加一个自环就行了.然后对于每条边两端颜色不同的连通块,显然是二分图,根据上面的道理,保留生成树就行了.然后在新图上跑dp,就是\(O(n^2)\)了
#include #include #include #include #include #include #include #include #include #include