我没有脑子。

题目链接

题意：给你一张$n$个点$m$条边的无向图，每个点有$0$或$1$的点权，$q$组询问，每组询问$x$和$y$，求是否存在一条从$x$到$y$的路径，满足这条路径上的点的点权按顺序拼接形成的字符串是回文串。（$n \leqslant 5000, m \leqslant 500000, q \leqslant 100000$）

我们用$f(i, j)$代表询问$i, j$的答案。我们要预处理出所有$f(i, j)$。

显然有一个$O(m^2)$的算法，我们一开始能确定$f(i, i) = 1$和$f(l, r) = 1$（$l$的点权和$r$的点权相同且$l$和$r$之间直接有边相邻），一旦我们确定$f(x, y) = 1$，如果$p$和$x$之间有边，$q$和$y$之间有边，并且$p$和$q$的点权相等，那么我们就能确定$f(p, q) = 1$。我们可以直接$\text{bfs}$或$\text{dfs}$出结果。

然后我们尝试删掉一些没有用的边。我们把所有连接两个点权为$1​$的点的边拿出来，它们构成的一个连通块如果是二分图，那么只要保留一棵生成树即可，否则保留一棵生成树，再增加加一个自环。（因为如果一条合法的路径中走过了删掉的边，我们可以走保留的生成树，然后让另一个点沿着当前边反复横跳，如果走的步数的奇偶性不对就沿着自环绕一圈）

然后对我们再对连接两个点权为$0$的点的边和连接两个点权不同的点的边都重复以上过程即可。这样边数就变成$O(n)$的了，复杂度就变成$O(n^2)$了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
#define mkp make_pair
const int maxn = 5000, maxm = 500000;
int n, m, q, l[maxm + 10], r[maxm + 10], d[maxn + 10];
char s[maxn + 10];
vector<int> g[maxn + 10], z[maxn + 10];
bool vis[maxn + 10][maxn + 10];

bool dfs(int p) {
	bool is = 0;
	for (int i = 0; i < (int)g[p].size(); ++i) {
		int e = g[p][i];
		if (d[e] == -1) {
			z[p].push_back(e); z[e].push_back(p);
			d[e] = d[p] ^ 1; is |= dfs(e);
		} else if (d[e] == d[p]) is = 1;
	}
	return is;
}

void solve() {
	for (int i = 1; i <= n; ++i) d[i] = -1;
	for (int i = 1; i <= n; ++i)
		if (d[i] == -1) {
			d[i] = 0;
			if (dfs(i)) z[i].push_back(i);
		}
}

void calc(int x, int y) {
	if (x > y) swap(x, y);
	if (vis[x][y]) return;
	static queue<pii> q;
	vis[x][y] = 1;
	q.push(mkp(x, y));
	while (!q.empty()) {
		x = q.front().first; y = q.front().second;
		q.pop();
		for (int i = 0; i < (int)z[x].size(); ++i)
			for (int j = 0; j < (int)z[y].size(); ++j) {
				int xx = z[x][i], yy = z[y][j];
				if (xx > yy) swap(xx, yy);
				if (!vis[xx][yy] && s[xx] == s[yy]) {
					vis[xx][yy] = 1; q.push(mkp(xx, yy));
				}
			}
	}
}

int main() {
	scanf("%d%d%d", &n, &m, &q);
	scanf("%s", s + 1);
	for (int i = 1; i <= m; ++i) scanf("%d%d", &l[i], &r[i]);
	for (int i = 1; i <= m; ++i)
		if (s[l[i]] == '0' && s[r[i]] == '0') {
			g[l[i]].push_back(r[i]);
			g[r[i]].push_back(l[i]);
		}
	solve();
	for (int i = 1; i <= n; ++i) g[i].clear();
	for (int i = 1; i <= m; ++i)
		if (s[l[i]] == '1' && s[r[i]] == '1')  {
			g[l[i]].push_back(r[i]);
			g[r[i]].push_back(l[i]);
		}
	solve();
	for (int i = 1; i <= n; ++i) g[i].clear();
	for (int i = 1; i <= m; ++i)
		if (s[l[i]] != s[r[i]])  {
			g[l[i]].push_back(r[i]);
			g[r[i]].push_back(l[i]);
		}
	solve();
	for (int i = 1; i <= n; ++i)
		calc(i, i);
	for (int i = 1; i <= m; ++i)
		if (s[l[i]] == s[r[i]]) calc(l[i], r[i]);
	while (q--) {
		int x, y; scanf("%d%d", &x, &y);
		if (x > y) swap(x, y);
		printf("%s\n", vis[x][y] ? "YES" : "NO");
	}
}