Luogu

LOJ

分析

orz myy

可以发现，一条回文路径左右扩展一个相同字符仍然是一条回文路径。

设 $f_{u, v}$ 表示 $(u, v)$ 间是否存在一条回文路径，转移枚举出边即可。这样子是 $\mathcal{O}(m^2)$ 的。

因为我们可以在一条边上反复横跳，所以直觉上这个东西只会和奇偶性有关。

对于连接同色点的边，我们对每个连通块单独考虑：如果构成二分图，则可以只保留一棵生成树，原来的转移仍然满足（可以反复横跳）；否则我们可以在生成树的基础上加一个自环，因为原来可以通过奇环改变长度的奇偶性，这里我们通过一个自环来达到同样的效果。

对于连接异色点的边，我们同样对每个连通块单独考虑。注意到这里一定是二分图，所以我们可以类似地只保留一棵生成树。

这样子边数变为 $\mathcal{O}(n)$ 级别，再跑上面那个 $\mathcal{O}(m^2)$ 做法就可以了。

代码

为啥我跑的这么慢 /ll

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X = 0, w = 1; char c = getchar();
    while (c < '0' || c > '9') { if (c == '-') w = -1; c = getchar(); }
    while (c >= '0' && c <= '9') X = X * 10 + c - '0', c = getchar();
    return X * w;
}

const int N = 5000 + 10;

int n, m, q, f[N][N];
char s[N];
vector<int> G[3][N], E[N];
pair<int, int> Q[N * N];
int h = 1, t = 0;

int fa[N], col[N], flag;
int sta[N], top;
void dfs(int k, int u, int c) {
    sta[++top] = u, col[u] = c;
    for (int v : G[k][u]) {
        if (!~col[v]) fa[v] = u, dfs(k, v, c ^ 1);
        else if (col[v] == c) flag = 0; 
    }
}

int main() {
    n = read(), m = read(), q = read();
    scanf("%s", s + 1);
    for (int i = 1; i <= m; ++i) {
        int u = read(), v = read(), f = (s[u] == s[v] ? s[u] - '0' : 2);
        G[f][u].emplace_back(v), G[f][v].emplace_back(u);
    }
    for (int k = 0; k < 3; ++k) {
        memset(col, -1, sizeof(col));
        for (int i = 1; i <= n; ++i) {
            if (~col[i]) continue;
            flag = 1, top = 0; dfs(k, i, 0);
            for (int j = 2; j <= top; ++j) {
                int u = sta[j];
                E[u].emplace_back(fa[u]), E[fa[u]].emplace_back(u);
            }
            if (!flag) E[i].emplace_back(i);
        }
    }
    for (int i = 1; i <= n; ++i) {
        f[i][i] = 1, Q[++t] = make_pair(i, i);
        for (int j : E[i])
            if (s[i] == s[j]) f[i][j] = f[j][i] = 1, Q[++t] = make_pair(i, j);
    }
    while (h <= t) {
        int x = Q[h].first, y = Q[h].second; ++h;
        for (int u : E[x])
            for (int v : E[y])
                if (s[u] == s[v] && !f[u][v]) 
                    f[u][v] = f[v][u] = 1, Q[++t] = make_pair(u, v);
    }
    while (q--) {
        int u = read(), v = read();
        puts(f[u][v] ? "YES" : "NO");
    }
    return 0;
}