LOJ3057
updated 11.7 发现在UOJ上TLE。改进了代码实现。 生成树是可以直接做的，减少了常数，这样每一颗树最多连一条自环，加一个标记即可。
SOL
30pts
从构造路径的角度思考，难以入手。总点数能实现
O
(
n
2
)
O(n^2)
O(n2)算法，转换思路，从中间向两边接点，构造回文串。
设
f
[
i
]
[
j
]
f[i][j]
f[i][j]表示
i
,
j
i,j
i,j点对能否作为回文路径的两端。故枚举
i
,
j
i,j
i,j的边尝试转移。
不难发现这样做总复杂度是
O
(
m
2
)
O(m^2)
O(m2)（每一对"边"最多被拿出两次）
100pts
优化建图，目标是将边数减少到
O
(
n
)
O(n)
O(n)级别。
先给出做法，再尝试证明。
做法：
我们把边分成两种，一种是两端点的颜色相同，另一种是不同。
对于前一种边，会形成若干个连通块。对于每一个连通块，如果是二分图，就做一颗生成树取代原连通块的边；如果不是就再随便找一个点加一个自环。
对于后一种边形成的连通块，由于颜色已经染好了，一定是一个二分图，做一颗生成树替代。
（前一种会形成多个互相独立的连通块，后一个连接各个连通块。）
证明：
我们要让原来的合法路径依然合法，且不会产生新的合法路径。
首先对于一条合法的路径，我们可以从中心划分成若干段，为
0
/
1
0/1
0/1交替段，全是
0
/
1
0/1
0/1段两种。更改原图后，我们只需要让关于中点相对称的两端依然能匹配(设为
A
A
A,
B
B
B两段)。
原来路径依然合法。
1.具体的长度不用考虑，只需要考虑段长的奇偶性。
由于点边可以重复经过，若
A
A
A段短了，可以重复走点走回来增加长度。但重复走点不会改变奇偶性。
2.对于一个同色连通块，只要两点能连通，且路径奇偶性不变即可
故如果有环，二分图中不同路径奇偶性不变，但是非二分图奇偶性要改变，多加一个自环就可以实现。
3.对于一个不同色连通块同理。
4.同色非二分图连通块中的任意一个点都可加自环，且可加任意多个（至少一个)
由2显然。 注意若加自环的点刚好也在另一个不同色连通块
S
S
S中，不会对
S
S
S产生影响。因为走两遍该点就不属于不同色段了。
原来不合法路径依然不合法
由上述证明，该建图方式利用的合法路径奇偶性的特点。 若原不合法路径奇偶性不合法，建图后奇偶性依然不合法。
CODE
#include<bits/stdc++.h>
using namespace std
;
#define sf scanf
#define ri register int
#define in red()
#define gc getchar()
#define cs const
#define ll long long
inline int red(){
int num
=0,f
=1;char c
=gc
;
for(;!isdigit(c
);c
=gc
)if(c
=='-')f
=-1;
for(;isdigit(c
);c
=gc
)num
=(num
<<1)+(num
<<3)+(c
^48);
return num
*f
;
}
cs
int N
=5e3+10,M
=5e5+10;
int n
,m
,Q
;
bool f
[N
][N
],col
[N
];
vector
<int>g
[N
];
struct edge
{
int u
,v
;
}e
[M
];
struct BCJ
{
int fa
[N
],d
[N
],ins
[N
];
inline int find(int u
){
if(!fa
[u
])return u
;
int t
=fa
[u
];
fa
[u
]=find(fa
[u
]);
d
[u
]^=d
[t
];
return fa
[u
];
}
inline void merge(int x
,int y
,int col
){
int fx
=find(x
),fy
=find(y
);
if(fx
^fy
){
d
[fx
]=d
[x
]^d
[y
]^1;
fa
[fx
]=fy
;
g
[x
].push_back(y
);
g
[y
].push_back(x
);
ins
[fy
]|=ins
[fx
];
}
else{
if(d
[x
]^d
[y
]^1)ins
[fx
]=1;
}
}
}G
[2];
queue
<edge
> q
;
inline void solve(){
for(ri i
=1;i
<=n
;++i
)f
[i
][i
]=1,q
.push((edge
){i
,i
});
for(ri u
=1;u
<=n
;++u
){
for(ri i
=g
[u
].size()-1;i
>=0;--i
){
int v
=g
[u
][i
];
if(!f
[u
][v
]&&col
[u
]==col
[v
]){
f
[u
][v
]=f
[v
][u
]=1;
q
.push((edge
){u
,v
});
}
}
}
while(!q
.empty()){
edge t
=q
.front();q
.pop();
int x
=t
.u
,y
=t
.v
;
for(ri i
=g
[x
].size()-1;i
>=0;--i
){
for(ri j
=g
[y
].size()-1;j
>=0;--j
){
int vx
=g
[x
][i
],vy
=g
[y
][j
];
if(col
[vx
]==col
[vy
]&&!f
[vx
][vy
]){
f
[vx
][vy
]=f
[vy
][vx
]=1;
q
.push((edge
){vx
,vy
});
}
}
}
}
}
char s
[N
];
signed main(){
n
=in
;m
=in
;Q
=in
;
sf("%s",s
+1);
for(ri i
=1;i
<=n
;++i
){
col
[i
]=s
[i
]^48;
}
for(ri i
=1;i
<=m
;++i
){
e
[i
]=(edge
){in
,in
};
}
for(ri i
=1;i
<=m
;++i
){
G
[col
[e
[i
].u
]^col
[e
[i
].v
]].merge(e
[i
].u
,e
[i
].v
,col
[e
[i
].u
]^col
[e
[i
].v
]);
}
for(ri i
=1;i
<=n
;++i
)if(G
[0].find(i
)==i
&&G
[0].ins
[i
])g
[i
].push_back(i
);
solve();
while(Q
--){
int x
=in
,y
=in
;
if(f
[x
][y
])cout
<<"YES\n";
else cout
<<"NO\n";
}
return 0;
}
