HNOI 2019 D2T1
神仙dp题，考场爆0只有我了
解法
myy出的，搬一下他的原话如下
30分的DP就是dp[i][j]表示i到j是否存在一条合法的路径，转移就是枚举i的边和j的边。总复杂度是
考虑减少边数。我们把一种标号单独拿出来，只考虑连接同一种标号的两个点的边。 对于一个连通块，如果它是二分图，那么我们仅保留一棵生成树答案也不会变。这是因为我们容易发现这个连通块之内的转移仍然可以实现（只要另一边在两个点内来回走即可）。如果它不是二分图，我们可以加一个自环。
我们考虑连接不同标号的边，只把这些边拿出来我们也可以形成若干个连通块。对于每个连通块， 根据同样的道理我们保留一棵生成树即可（注意这个时候连通块一定都是二分图）。
这样总边数不超过
所以为什么不是二分图的时候可以加自环呢？仔细想想，如果图不是二分图，就说明图中一定有长度为奇数的环。那么在这边可以一直来回转圈，另一边如果也有奇数环，那么显然可以匹配，如果另一边是二分图，那么显然我们可以在这一边转上几圈，让长度变成偶数，依然可以转移QAQ
如果不懂的话可以自己手造数据的QAQ，个人认为比较好理解
于是就变成了
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define rg register
#define il inline
#define MX (5000 + 65)
#define M_MX (500000 + 5)
int cs ,cd;
struct ip{
int u ,v;
}same[M_MX] ,diff[M_MX];
int color[MX];
namespace FS{ //forward_star 前向星
int head[MX] ,tot;
struct edge{
int node ,next;
}h[M_MX << 1];
il void addedge(int u ,int v){
h[++tot].next = head[u];
head[u] = tot;
h[tot].node = v;
}
}
int n ,m ,q;
int fa[MX];
void init(int upper){
for(rg int i = 1 ; i <= upper ; ++i) fa[i] = i;
using namespace FS;
memset(FS::head ,0 ,sizeof(head));
memset(h ,0 ,sizeof(h));
tot = 0;
}
int find(int x){return fa[x] == x ? x : fa[x] = find(fa[x]);}
void link(int x ,int y){fa[find(x)] = find(y);}
int vis[MX][MX] ,DP[MX][MX];
namespace MST{ //Minimum Spanning Tree 最小生成树
int head[MX] ,tot;
FS::edge h[M_MX << 1];
void addedge(int u ,int v){
h[++tot].next = head[u];
head[u] = tot;
h[tot].node = v;
}int Tag[MX];
bool check2fen(int x ,int tag){
if(Tag[x]) return Tag[x] == tag;
Tag[x] = tag;
for(rg int i = FS::head[x] ; i ; i = FS::h[i].next){
int d = FS::h[i].node;
if(!check2fen(d ,tag == 1 ? 2 : 1)) return false;
}return true;
}
void kruskal(int type){
if(type == 1){ //单独拿出连接同种编号的
for(rg int i = 1 ; i <= n ; ++i) Tag[i] = false;
init(n);
int cnt = 0;
for(rg int i = 1 ; i <= cs ; ++i){
FS::addedge(same[i].u ,same[i].v);
FS::addedge(same[i].v ,same[i].u);
}
for(rg int i = 1 ; i <= cs ; ++i){
if(find(same[i].u) != find(same[i].v)){
LST::addedge(same[i].u ,same[i].v);
LST::addedge(same[i].v ,same[i].u);
link(same[i].u ,same[i].v);
++cnt;
}
}
for(rg int i = 1 ; i <= n ; ++i){
if(!Tag[i]){
if(!check2fen(i ,1)) LST::addedge(i ,i);
}
}
}
else{//单独拿出连接不同种编号的
init(n);
for(rg int i = 1 ; i <= n ; ++i) Tag[i] = false;
int cnt = 0;
for(rg int i = 1 ; i <= cd ; ++i){
FS::addedge(diff[i].u ,diff[i].v);
FS::addedge(diff[i].v ,diff[i].u);
}
for(rg int i = 1 ; i <= cd ; ++i){
if(find(diff[i].u) != find(diff[i].v)){
LST::addedge(diff[i].u ,diff[i].v);
LST::addedge(diff[i].v ,diff[i].u);
link(diff[i].u ,diff[i].v);
++cnt;
}
}
for(rg int i = 1 ; i <= n ; ++i){
if(!Tag[i]){
if(!check2fen(i ,1)) LST::addedge(i ,i);
}
}
}
}
}using namespace MST;
void dp(){ //大力转移，因为本题有O2，可以放心用STL
std::queue<int> q1 ,q2;
for(rg int i = 1 ; i <= n ; ++i){
vis[i][i] = true;
DP[i][i] = true;
q1.push(i) ,q2.push(i);
for(rg int j = head[i] ,d ; j ; j = h[j].next){
d = h[j].node;
vis[i][d] = vis[d][i] = true;
if(color[i] != color[d]) continue;
DP[i][d] = DP[d][i] = true;
q1.push(i) ,q2.push(d);
}
}
while(!q1.empty()){
int x = q1.front() ,y = q2.front();
q1.pop() ,q2.pop();
for(rg int i = head[x] ; i ; i = h[i].next){
for(rg int j = head[y] ; j ; j = h[j].next){
if(!vis[h[i].node][h[j].node] && color[h[i].node] == color[h[j].node]){
DP[h[i].node][h[j].node] = DP[h[j].node][h[i].node] = true;
q1.push(h[i].node) ,q2.push(h[j].node);
}vis[h[i].node][h[j].node] = vis[h[j].node][h[i].node] = true;
}
}
}
}
int main(){
scanf("%d%d%d" ,&n ,&m ,&q);
for(rg int i = 1 ; i <= n ; ++i){
scanf("%1d" ,color + i);
}
for(rg int i = 1 ,u ,v ; i <= m ; ++i){
scanf("%d%d" ,&u ,&v);
FS::addedge(u ,v);
FS::addedge(v ,u);
if(color[u] ^ color[v]) diff[++cd] = (ip){u ,v};
else same[++cs] = (ip){u ,v};
}
using namespace MST;
kruskal(1);
kruskal(2);
//outedge();
dp();
for(rg int i = 1 ,u ,v ; i <= q ; ++i){
scanf("%d%d" ,&u ,&v);
if(DP[u][v] || DP[v][u]) puts("YES");
else puts("NO");
}
return 0;
}