考虑30分做法：暴力bfs，\(f[i][j]\)表示\(i\)到\(j\)可以形成回文串

然而为什么我场上只想到了70分做法，完全没想到30分怎么写。。

100分：

考虑缩边，对于每条边分3种情况：标号同为1，标号同为0，标号不同

1、同为1：考虑如果这是个二分图，那么可以转化为一颗生成树，对答案无影响，如果不是二分图，那么就随意加一条自环，这样就可以同时出现奇回文和偶回文

2、同为0：同上

3、不同，只有可能是二分图，直接建生成树就好了

这样下来边的数量就是\(O(n)\)级的了

然后再暴力跑bfs就好了，没错，就是那个30分做法，总复杂度\(O(n^2)\)

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         using namespace std;void read(int &x){    char ch;bool ok;    for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1;    for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}#define rg registerconst int maxn=1e6+10;queue
         
          
            >q;int n,m,qq,f[5010][5010];char ch[5010];struct oo{ int cnt,pre[maxn],nxt[maxn],h[maxn],w[maxn]; bool flag; void add(int x,int y){ pre[++cnt]=y,nxt[cnt]=h[x],h[x]=cnt; pre[++cnt]=x,nxt[cnt]=h[y],h[y]=cnt; }}a,b,c,d;void dfs1(int x,int v){ a.w[x]=v; for(rg int i=a.h[x];i;i=a.nxt[i]) if(a.w[a.pre[i]]!=-1&&a.w[a.pre[i]]==a.w[x])a.flag=1; else if(a.w[a.pre[i]]==-1)dfs1(a.pre[i],v^1),d.add(a.pre[i],x);}void dfs2(int x,int v){ b.w[x]=v; for(rg int i=b.h[x];i;i=b.nxt[i]) if(b.w[b.pre[i]]!=-1&&b.w[b.pre[i]]==b.w[x])b.flag=1; else if(b.w[b.pre[i]]==-1)dfs2(b.pre[i],v^1),d.add(b.pre[i],x);}void dfs3(int x,int v){ c.w[x]=v; for(rg int i=c.h[x];i;i=c.nxt[i]) if(c.w[c.pre[i]]!=-1&&c.w[c.pre[i]]==c.w[x])c.flag=1; else if(c.w[c.pre[i]]==-1)dfs3(c.pre[i],v^1),d.add(c.pre[i],x);}#define mk(a,b) make_pair(a,b)void solve(){ for(rg int i=1;i<=n;i++)f[i][i]=1,q.push(mk(i,i)); for(int x=1;x<=n;x++) for(int i=d.h[x];i;i=d.nxt[i]) if(ch[x]==ch[d.pre[i]])f[x][d.pre[i]]=1,q.push(mk(x,d.pre[i])); while(!q.empty()){ pair
           
             x=q.front();q.pop(); for(rg int i=d.h[x.first];i;i=d.nxt[i]) for(rg int j=d.h[x.second];j;j=d.nxt[j]) if(ch[d.pre[i]]==ch[d.pre[j]]&&!f[d.pre[i]][d.pre[j]])f[d.pre[i]][d.pre[j]]=1,q.push(mk(d.pre[i],d.pre[j])); }}int main(){ read(n),read(m),read(qq),scanf("%s",ch+1); for(rg int i=1,x,y;i<=m;i++){ read(x),read(y); if(ch[x]!=ch[y])a.add(x,y); else if(ch[x]=='0')b.add(x,y); else c.add(x,y); } memset(a.w,-1,sizeof a.w); memset(b.w,-1,sizeof b.w); memset(c.w,-1,sizeof c.w); for(rg int i=1;i<=n;i++){ if(a.w[i]==-1){ a.flag=0,dfs1(i,0); if(a.flag)d.add(i,i); } if(b.w[i]==-1){ b.flag=0,dfs2(i,0); if(b.flag)d.add(i,i); } if(c.w[i]==-1){ c.flag=0,dfs3(i,0); if(c.flag)d.add(i,i); } } solve(); for(rg int i=1,x,y;i<=qq;i++){ read(x),read(y); if(f[x][y])printf("YES\n"); else printf("NO\n"); }}