神仙好题啊~膜拜出题者
洛谷题目传送门
给定一张无向图，每个点有权值v=0或1,q次询问，每次给出两个点，判断两点间是不是有一条路径，使得路径上经过的点的权值构成一个回文串，每个点，每条边可以重复走
我们形式化地定义一下回文串
· 单个字符是回文串
· 两个相同字符是回文串
· 在回文串两端加上相同字符，依旧是回文串
这启示我们有一个30pts的dp
设
f
i
,
j
f_{i,j}
fi,j表示
i
i
i与
j
j
j能否构成回文串，如果能，那么在这条路径两端加上相同字符依旧构成字符串，也就可以转移，可以用队列把所有可行的二元组存起来，依次向外扩展，初始条件，若
i
,
j
i,j
i,j颜色相同且
i
,
j
i,j
i,j有边，则
f
i
,
j
=
1
f_{i,j}=1
fi,j=1，特别的
f
i
,
i
=
1
f_{i,i}=1
fi,i=1,复杂度
O
(
m
2
)
O(m^2)
O(m2)，瓶颈主要在于边数
上述DP的复杂度在于边数，而我们发现点数非常小，考虑能不能将边数缩小，也就是只保留有用的边
看下面一张图，这两个点间有一条符合条件的路径
因为题目中说某一个点可以重复经过，所以这两点间如果存在下面这样的路径也是合法的
这是因为我可以重复走一边这个白点
换句话说，如果这两点路径中有这样的两个点
S
→
…
…
→
u
→
v
→
…
…
→
T
S\to……\to u \to v \to …… \to T
S→……→u→v→……→T
其中
u
,
v
u,v
u,v颜色相同，那么这样的也是合法的
S
→
…
…
→
u
→
v
→
u
→
v
→
…
…
→
T
S\to……\to u \to v \to u \to v \to…… \to T
S→……→u→v→u→v→……→T
但是这个长度的奇偶性是不变的
我们也能发现只需要保证对应的两段的奇偶性相同，就能构成回文
所以我们考虑简化同色连通块内的边，显然如果这个连通块内任意两个点的路径长度奇偶性是固定的，不过怎么走都不会变，那么我们只需要保留这个连通块的最简形态即可，为了保证联通，这个最简形态一定是一颗生成树。
考虑什么样的连通子图满足上述性质，很显然只要不存在奇环就行，不存在奇环？看到这个很容易想到二分图
所以如果某个同色连通块是二分图，只保留它的一颗生成树
那么如果不是二分图呢，也就是说两个点间既可以通过奇数条边相连，也可以通过偶数条边相连，那么我们在保留生成树的基础上，留下一个奇环就行了，这样能保证如果想要转换奇偶性，来到这个奇环上走一圈就行了，那么最简单的奇环是什么，就是自环，所以如果不是二分图，保留一颗生成树和一个自环就行了
对于连接不同同色连通块的边，这些边也可能构成连通块，而且，这个连通块一定是一颗二分图，因为同色点内肯定没有边，根据上面的理论，保留一颗生成树就行了
所以我们的步骤就是，对于同色连通块，如果是二分图，保留一颗生成树，不是的话保留一颗生成树和一个自环，不同色连通块，保留一颗生成树就行了，容易证明这样的边数是
O
(
n
)
O(n)
O(n)级别的
再做上面的算法，复杂度
O
(
n
2
+
m
)
O(n^2+m)
O(n2+m)
再次膜拜出题人，真的是神仙题
代码很好写
#include<bits/stdc++.h>
using namespace std;
const int N = 5020;
const int M = 5e5+7;
struct node
{
int y,next;
}e[2*M];
int link[N],t=0;
void add(int x,int y)
{
e[++t].y=y;
e[t].next=link[x];
link[x]=t;
}
char s[N];
int a[N];
int n,m,q;
inline int read()
{
int X=0; bool flag=1; char ch=getchar();
while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
if(flag) return X;
return ~(X-1);
}
int f[N];
struct Edge
{
int x,y;
};
queue<Edge> que;
bool ans[N][N];
void Insert(Edge x)
{
que.push(x);
ans[x.x][x.y]=1;
ans[x.y][x.x]=1;
}
int col[N];
vector<int> G[N];
void Link(int x,int y)
{
G[x].push_back(y);
G[y].push_back(x);
}
bool Dye(int x,int c)
{
col[x]=c;
bool ok=1;
for(int i=link[x];i;i=e[i].next)
{
int y=e[i].y;
if(a[x]!=a[y]) continue;
if(!col[y])
{
Link(x,y);
ok&=Dye(y,3-c);
Insert((Edge){x,y});
}
else if(col[x]==col[y]) ok=0;
}
return ok;
}
void Extand(int x,int y)
{
for(int i=0;i<G[x].size();i++)
{
for(int j=0;j<G[y].size();j++)
{
int u=G[x][i],v=G[y][j];
if(!ans[u][v]&&a[u]==a[v])
Insert((Edge){u,v});
}
}
}
void dp()
{
while(!que.empty())
{
int x=que.front().x,y=que.front().y;
que.pop();
Extand(x,y);
}
}
int u[M],v[M];
int Find(int x)
{
if(x==f[x]) return x;
return f[x]=Find(f[x]);
}
int main()
{
n=read();
m=read();
q=read();
scanf("%s",s+1);
for(int i=1;i<=n;i++)
a[i]=s[i]-'0';
for(int i=1;i<=m;i++)
{
int x=read(),y=read();
add(x,y);
add(y,x);
u[i]=x;
v[i]=y;
}
for(int i=1;i<=n;i++)
{
if(!col[i])
{
if(!Dye(i,1))
G[i].push_back(i);
}
}
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
{
int x=u[i],y=v[i];
if(a[x]!=a[y]&&Find(x)!=Find(y))
{
f[Find(y)]=Find(x);
Link(x,y);
}
}
for(int i=1;i<=n;i++)
Insert((Edge){i,i});
dp();
while(q--)
{
int x=read(),y=read();
if(ans[x][y]) printf("YES\n");
else printf("NO\n");
}
return 0;
}