题解 P5292 【[HNOI2019]校园旅行】
洛水·锦依卫
2019-04-09 20:55:03
[欢迎来博客玩呀](https://www.cnblogs.com/luoshuitianyi/p/10679665.html)
# Algorithm
$DP$
# Mentality
考场上无人切的神题 $orz$ ，$myy\ nb$ 。
由于 $n$ 异常的小，所以我们发现完全可以用 $n^2$ 的二维空间来储存信息，而 $m$ 和 $q$ 相对来说又异常大，这启发我们用一种看起来很暴力的方法做这道题 -- 预处理出所有点对的情况。
$30$ 分的做法还是很好想的，我们发现可以将回文路径分为两类：长度为奇数的，长度为偶数的。
设 $f[i][j]$ 为 $i,j$ 之间是否有回文路径，那么我们先处理出长度最短的奇偶回文路径。首先，长度最短的奇数回文路径就是每个点自己，即 $f[i][i]=1$ 。然后观察到对于每条边，如果连的两个点 $u,v$ 编号相同，则 $f[u][v]=f[v][u]=1$ ，这些就是长度最短的偶数回文路径。
然后考虑利用这些信息进行 $DP$ 转移，我们用 $bfs$ 的顺序来转移即可。
将这些两点之间有路径的二元组 $(u,v)$ 扔进队列，转移的时候枚举 $u,v$ 的出边 $to_u,to_v$，如果 $to_u$ 的编号与 $to_v$ 相同，那么 $to_u,to_v$ 之间肯定也存在回文路径，我们将 $f$ 数组更新，然后将二元组 $to_u,to_v$ 丢入队列末尾等待下一次转移即可。
由于每次转移都要枚举两点的出边一一判断，所以复杂度为 $m^2$ 。
代码大概长这个样子？
```cpp
while(h<t)
{
h++;
for(int i=hd[u[h]];i;i=Nx[i])
for(int j=hd[v[h]];j;j=Nx[j])
if(S[To[i]]==S[To[j]]&&!f[To[i]][To[j]])
f[To[i]][To[j]]=f[To[j]][To[i]]=1,Add(To[i],To[j]);
}
```
由于 $STL$ 常数太大，所以手写队列 (也就总共 $5e7$ 的空间~~而已~~)
询问一次就直接看它的 $f$ 数组即可。
接下来考虑 $100$ 分做法。
观察到 $m$ 巨大，我们考虑减少边的枚举。
我们将所有转移分成两类：向相同编号的点转移，向不同编号的点转移。
那么我们也就可以依此将边分为两类：连接相同编号点的边，连接不同编号点的边。
我们先考虑一类边，譬如连接相同编号点的边。
这些边把图分成了许多个联通块，我们发现，对于一个联通块内的转移，只取决于一件事：这个联通块是不是个二分图。
为什么呢？我们来考虑一下，如果联通块是一个二分图，那么它满足两个性质。
- 能将联通块内的点划分成两个集合，同一集合内的点互不直接相连。
- 同时由于这是个联通块，两点之间皆可达。
那么不难发现，如果我在一个集合内，想要转移到集合内另一点，必定会经过偶数条边。
因为我到达这个点的过程中，注定只能是重复 `当前集合` -> `另一集合` -> `当前集合` 这样的步骤，所以最后的步数一定是偶数条。
换而言之，若联通块为二分图，那么联通块内任意两点之间的路径长度奇偶性唯一。
而注意到，当我们 $DP$ 转移的时候，若回文串两端新增的数字全都相同，譬如在左右端都添上 $0$ ，那么我们只需要保证左右两边新增的数量相同即可。
而根据题目的性质可知，我们为保证数量相等，完全可以在一条连向一个相同编号点的边上来回横走保证数量的增值。但是**这样不改变奇偶性**。
那么奇偶性就成了判断 $DP$ 转移的重要性质了。
接着上面的推论，由于若联通块为二分图，那么联通块内两点件路径长度奇偶性唯一。那么我们在这个联通块内，只需要**保留一颗生成树**即可，因为 **奇偶唯一** ，所以 **不影响 $DP$ 过程** 。
然后我们再来看，如果不是二分图怎么办。还是划分成两个集合，那么同一集合内至少有一对点 $(u,v)$ 之间直接有连边。由于只考虑连接两个不同集合的边时，从 $u$ 至 $v$ 必定有一条长度为 **偶数** 的路径，所以再加上一条边，这个联通块内就有了一个 **奇环** 。则联通块内任意一点都可以走到奇环上通过绕环改变路径长度奇偶性。
那么不难发现，我们只需要先像二分图一样，保留一颗生成树。至于那个奇环，我们只需**要在生成树内任意一个点上随便连个自环**就行了 $QwQ$，反正只是要个奇环而已，自环当然也是啦。
以上是连接相同编号点的边的处理方式。
至于连接不同编号的边的话，我们发现这联通块肯定就是个二分图，那么直接保留生成树即可。
那么边数减少为 $n$ 的级别，此时再去 $DP$ ，复杂度就降为 $n^2$ 了。
如若未懂详见代码
# Code
```cpp
#include<iostream>
#include<cstdio>
using namespace std;
int n,m,Q;
int cntr,head[5001],nx[1000001],to[1000001],col[5001];
int cr,hd[5001],Nx[1000001],To[1000001];
int h,t,u[25000001],v[25000001];
bool flag,f[5001][5001];
char S[5001];
struct node{int u,v;};
void read(int &x)
{
x=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
}
void addr(int u,int v)
{
cntr++;
nx[cntr]=head[u],to[cntr]=v;
head[u]=cntr;
}
void Addr(int u,int v)
{
cr++;
Nx[cr]=hd[u],To[cr]=v;
hd[u]=cr;
}
void Add(int U,int V)
{
t++;
u[t]=U,v[t]=V;
}
void dye(int x,bool type)
{
for(int i=head[x];i;i=nx[i])
{
int p=to[i];
if((S[p]==S[x])==type)//构图参数的使用
{
if(col[p]!=-1)if(!(col[p]^col[x]))flag=1;//染色冲突则不是二分图
if(col[p]==-1)
{
col[p]=col[x]^1,dye(p,type);
Addr(x,p),Addr(p,x);//加边
}
}
}
}
void Read_Init()
{
read(n),read(m),read(Q);
scanf("%s",S+1);
int u,v;
while(m--)
{
read(u),read(v);
if(S[u]==S[v])f[u][v]=f[v][u]=1,Add(u,v);//先加入偶数最短边，并更新 DP 数组
addr(u,v),addr(v,u);
}
}
void Build_Init()
{
for(int i=1;i<=n;i++)f[i][i]=1,Add(i,i);//加入奇数最短边，并更新 DP 数组
for(int k=0;k<2;k++)//k 是构图参数
{
for(int i=1;i<=n;i++)col[i]=-1;//二分图染色初始化
for(int i=1;i<=n;i++)
if(col[i]==-1)
{
flag=0;
col[i]=0,dye(i,k);
if(flag)Addr(i,i);//如果不是二分图那就加个自环
}
}
}
void DP()
{
while(h<t)
{
h++;
for(int i=hd[u[h]];i;i=Nx[i])
for(int j=hd[v[h]];j;j=Nx[j])
if(S[To[i]]==S[To[j]]&&!f[To[i]][To[j]])
f[To[i]][To[j]]=f[To[j]][To[i]]=1,Add(To[i],To[j]);//DP 转移
}
}
void Answer()
{
int u,v;
while(Q--)
{
read(u),read(v);
if(f[u][v])printf("YES\n");
else printf("NO\n");
}
}
int main()
{
Read_Init();
Build_Init();
DP();
Answer();
}
```