题目：https://loj.ac/problem/3057
想令 b[ i ][ j ] 表示两点是否可行，从可行的点对扩展。但不知道顺序，所以写了卡时间做数次 m2 迭代的算法，就是每次遍历所有不合法点对，枚举其出边看是否有合法的，把自己更新成合法。
可得10分。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=,M=5e5+,Tm=6e7;
int n,m,hd[N],xnt,to[M<<],nxt[M<<];
int cnt,col[N];bool a[N],b[N][N];
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
void dfs(int cr)
{
col[cr]=cnt;
for(int i=hd[cr],v;i;i=nxt[i])
if(!col[v=to[i]])dfs(v);
}
void solve()
{
for(int i=;i<=n;i++)
if(!col[i]) cnt++,dfs(i);
for(int i=;i<=n;i++)b[i][i]=;
for(int i=;i<=n;i++)
for(int j=hd[i],v;j;j=nxt[j])
if(a[i]==a[v=to[j]])b[i][v]=b[v][i]=;
int pl=n*n;
//for(int lj=0,cd=0;lj<=Tm&&cd<=n;lj+=pl,cd++)
for(int lj=;lj<=Tm*;lj+=pl)
{
bool flag=;
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
{
if(b[i][j]||a[i]!=a[j]||col[i]!=col[j])continue;
bool fg=;
for(int l0=hd[i];l0&&!fg;l0=nxt[l0])
for(int l1=hd[j];l1;l1=nxt[l1])
if(b[to[l0]][to[l1]]){fg=;break;}
if(fg)b[i][j]=b[j][i]=;
else flag=;
}
if(!flag)break;
}
}
int main()
{
n=rdn();m=rdn();int Q=rdn();
char ch[N]; scanf("%s",ch+);
for(int i=;i<=n;i++)a[i]=ch[i]-'';
for(int i=,u,v;i<=m;i++)
{
u=rdn();v=rdn();add(u,v);add(v,u);
}
solve();int u,v;
while(Q--)
{
u=rdn();v=rdn();puts(b[u][v]?"YES":"NO");
}
return ;
}
30分暴力是这样：不是遍历不合法点对，而是遍历合法点对。
因为一个点对合法之后就没用变化，可以不用管了，所以在合法的时候把它的影响也算过，再不用管它，正确性和时间都是对的。遍历不合法点对，可能有很多失败尝试，时间没有保证。
即把合法点对压入队列，每次从队列里取出，遍历两个点出边看能否产生新的合法点对。因为点对合法之后不会有变化，所以遍历的先后之类的没有影响。
这样是 m2 的。
然后考虑把图的规模缩小。
因为发现有 “在一条边上来回走” 之类的情况，所以很多边去掉也不会影响答案。
然后从连接同色点和连接异色点的边来考虑。因为同色点之间可以来回走得到特定长度，异色点之间可以得到特定次数的颜色切换。把一个合法回文串拆成这两个部分考虑。
考虑所有连 0 类点的边构成的某个连通块。如果是二分图，则一个点到另一个点的长度任意，但一定是奇数长度或偶数长度中的一种。
如果把该连通块删边至剩下一棵树，性质不会改变。两个点之间还是任意长度、奇数或偶数中的一种。
可能本来可以较短地走过去，变成树之后不得不走很长才能走过去。不过在答案中只要在回文的另一侧多走一些就行了。
如果不是二分图，一个点到另一个点之间的长度和奇偶性都是任意的。只要在删成一棵树之后给某个点连一个自环就能让树等价于原图了。
连 1 类点的边也是一样。连异色点的边也是一样。不过连异色点的边构成的不会不是二分图。
然后图被删得剩下 O(n) 条边。刚才的做法就变成 n2 而可过了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
const int N=,M=5e5+;
int n,m,top,hd[N],xnt,to[M<<],nxt[M<<],fa[N];
bool a[N],vis[N],col[N],b[N][N],flag;
struct Ed{
int x,y;
Ed(int x=,int y=):x(x),y(y) {}
}ed[M],sta[M];
namespace G{
int hd[N],xnt,to[N<<],nxt[N<<],q[N*N][];
void add(int x,int y)
{
to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;
to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;
}
void solve()
{
int he=, tl=;
for(int i=;i<=n;i++)
{
q[++tl][]=i;q[tl][]=i;b[i][i]=;
}
for(int i=;i<=n;i++)
for(int j=hd[i],v;j;j=nxt[j])
if(a[v=to[j]]==a[i]&&i<v)
{
q[++tl][]=i;q[tl][]=v;b[i][v]=b[v][i]=;
}
while(he<tl)
{
int x=q[++he][], y=q[he][];
for(int i=hd[x],v1;i;i=nxt[i])
for(int j=hd[y],v2;j;j=nxt[j])
if(a[v1=to[i]]==a[v2=to[j]]&&!b[v1][v2])//!b[][]
{
q[++tl][]=v1;q[tl][]=v2;b[v1][v2]=b[v2][v1]=;
}
}
}
}
void add(int x,int y){to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;}
int fnd(int a){if(fa[a]==a)return a;return fa[a]=fnd(fa[a]);}
void dfs(int cr)
{
vis[cr]=;
for(int i=hd[cr],v;i;i=nxt[i])
if(a[v=to[i]]==a[cr])
{
sta[++top]=Ed(cr,v);
if(!vis[v])col[v]=!col[cr],dfs(v);
else if(col[v]==col[cr])flag=;
}
}
void init()
{
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=n;i++)
if(!a[i]&&!vis[i])
{
flag=;top=;dfs(i);if(flag)G::add(i,i);
for(int j=,u,v;j<=top;j++)
if((u=fnd(sta[j].x))!=(v=fnd(sta[j].y)))
G::add(sta[j].x,sta[j].y), fa[u]=v;
}
for(int i=;i<=n;i++)
if(a[i]&&!vis[i])
{
flag=;top=;dfs(i);if(flag)G::add(i,i);
for(int j=,u,v;j<=top;j++)
if((u=fnd(sta[j].x))!=(v=fnd(sta[j].y)))
G::add(sta[j].x,sta[j].y), fa[u]=v;
}
for(int i=;i<=n;i++)fa[i]=i;//
for(int i=,u,v;i<=m;i++)
if((u=fnd(ed[i].x))!=(v=fnd(ed[i].y)))
G::add(ed[i].x,ed[i].y), fa[u]=v;
}
int main()
{
n=rdn();int tp=rdn();int Q=rdn();
char ch[N]; scanf("%s",ch+);
for(int i=;i<=n;i++)a[i]=ch[i]-'';
for(int i=,u,v;i<=tp;i++)
{
u=rdn();v=rdn();add(u,v);add(v,u);
if(a[u]!=a[v])ed[++m]=Ed(u,v);
}
init(); G::solve(); int u,v;
while(Q--)
{
u=rdn();v=rdn();puts(b[u][v]?"YES":"NO");
}
return ;
}