洛谷P5292 [HNOI2019]校园旅行题解

题目链接：P5292 [HNOI2019]校园旅行

题意：

~~HNOI2019 day2t1就这么难了，好珂怕~~

某学校的每个建筑都有一个独特的编号。一天你在校园里无聊，决定在校园内随意地漫步。

你已经在校园里呆过一段时间，对校园内每个建筑的编号非常熟悉，于是你情不自禁的把周围每个建筑的编号都记了下来——但其实你没有真的记下来，而是把每个建筑的编号除以 \(2\) 取余数得到 \(\mathtt{0}\) 或 \(\mathtt{1}\)，作为该建筑的标记，多个建筑物的标记连在一起形成一个 \(\mathtt{01}\) 串。

你对这个串很感兴趣，尤其是对于这个串是回文串的情况，于是你决定研究这个问题。

学校可以看成一张图，建筑是图中的顶点，而某些顶点之间存在无向边。对于每个顶点我们有一个标记（\(\mathtt{0}\) 或者 \(\mathtt{1}\) ）。每次你会选择图中两个顶点，你想知道这两个顶点之间是否存在一条路径使得路上经过的点的标记形成一个回文串。

一个回文串是一个字符串使得它逆序之后形成的字符串和它自己相同，比如 \(\mathtt{010}\) ，\(\mathtt{1001}\) 都是回文串，而 \(\mathtt{01}\) ，\(\mathtt{110}\) 不是。注意长度为 \(1\) 的串总是回文串，因此如果询问的两个顶点相同，这样的路径总是存在。此外注意，经过的路径不一定为简单路径，也就是说每条边每个顶点都可以经过任意多次。

输入格式：

第一行三个整数 \(n,m,q\) ，表示图中的顶点数和边数，以及询问数。

第二行为一个长度为 \(n\) 的 \(\mathtt{01}\) 串，其中第 \(i\) 个字符表示第 \(i\) 个顶点（即顶点 \(i\)）的标记，点从 \(1\) 开始编号。

接下来 \(m\) 行，每一行是两个整数 \(u_i,v_i\)，表示顶点 \(u_i\) 和顶点 \(v_i\) 之间有一条无向边，不存在自环或者重边。

接下来 \(q\) 行，每一行存在两个整数 \(x_i,y_i\)，表示询问顶点 \(x_i\) 和顶点 \(y_i\) 的点之间是否有一条满足条件的路径。

输出格式：

输出 \(q\) 行，每行一个字符串 YES ，或者 NO 。

输出 YES 表示满足条件的路径存在，输出 NO 表示不存在。

数据范围：

\(1 \le n \le 5000,~1 \le m \le 5\times 10^5,~1 \le q \le 10^5\)。

考虑 \(30\) 分的 dp 。设 \(f_{i,j}\) 表示 \(i\) 到 \(j\) 是否存在一条合法的路径。

转移就是枚举 \(i,j\) 的出边，然后转移，每个点至多被访问 \(\mathcal{O}(1)\) 次，时间复杂度 \(\mathcal{O}(m^2)\) 。

考虑减少边数。首先对于 \(\mathtt{col}(u) \ne \mathtt{col}(v)\) 的边，可以发现它构成一个二分图。

因此我们只需要保留其一棵生成树即可，因为其他的均可以通过 \(u\to v \to u\) 达到。

对于 \(\mathtt{col}(u) = \mathtt{col}(v)\) 的边，如果它构成了一个二分图，那么也可以仅保留其生成树。

如果不是二分图，我们可以在生成树上加一个自环。

为什么可以加一个自环呢？因为 \(u,v\) 颜色相同，所以两侧只需要匹配数量相等即可。

如果两侧匹配的都是奇环，那加不加都能匹配。

如果其中一侧是二分图，那我们可以通过在奇环上绕圈绕到偶数的情况。（根据乘法的性质可知）

加一个自环就相当于加速了~~这个没啥意义的跑圈过程~~。因此是正确的。

时间复杂度 \(\mathcal{O}(n^2)\) ，因为边数至多 \(2n-2\) 条。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define DDD cout << "line here is " << __LINE__ << '\n';
typedef pair<int,int> pii;
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define Fi first
#define Se second
#define N ((int)(5e3+25))
#define M ((int)(5e5+15))

pii same[M], diff[M];
int n,m,Q,cd,cs; int fa[N],sz[N];
char col[N]; bitset<N> dp[N],vis[N];
namespace Graph
{
    int pos=1,head[N];
    struct Edge { int u,v,next; } e[M * 2];
    void addEdge(int u,int v)
    { e[++pos] = {u,v,head[u]}; head[u] = pos; }
    void clear(int n) { for(int i=1; i<=n; i++) head[i] = 0; pos = 1;}
}
void init(int n)
{ for(int i=1; i <= n; i++) fa[i] = i, sz[i] = 1; Graph::clear(n); }
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool merge(int u,int v)
{
    int x = find(u), y = find(v);
    if(x == y) return 0;
    if(sz[x] > sz[y]) swap(x,y);
    fa[x] = y; sz[y] += sz[x]; return 1;
}
namespace MST
{
    int pos=1,head[N]; bitset<N> tag,vis;
    struct Edge { int u,v,next; } e[M * 2];
    void addEdge(int u,int v)
    { e[++pos] = {u,v,head[u]}; head[u] = pos; }
    bool test(int u,int t)
    {
        if(vis[u]) return (tag[u] == t);
        tag[u] = t; vis[u] = 1;
        for(int i=Graph::head[u]; i; i=Graph::e[i].next)
        {
            int v = Graph::e[i].v;
            if(!test(v, t^1)) return 0;
        }return 1;
    }
    void kruskal(int type)
    {
        init(n); int cnt = 0, len = (type==1) ? cs : cd;
        pii *arr = (type==1) ? same : diff;
        for(int i=1; i<=n; i++) tag[i] = 0, vis[i] = 0;
        for(int i=1; i<=len; i++)
        {
            Graph::addEdge(arr[i].Fi, arr[i].Se);
            Graph::addEdge(arr[i].Se, arr[i].Fi);
        }
        for(int i=1; i<=len && cnt < n-1; i++)
            if(merge(arr[i].Fi, arr[i].Se) && ++cnt)
            {
                MST::addEdge(arr[i].Fi, arr[i].Se);
                MST::addEdge(arr[i].Se, arr[i].Fi);
            }
        for(int i=1; i<=n; i++)
            if(!vis[i] && !test(i,0)) MST::addEdge(i,i);
    }
}
queue<pii> q;
void solve()
{
    using MST::head, MST::e;
    for(int u=1; u<=n; u++)
    {
        vis[u][u] = 1; dp[u][u] = 1; q.push(pii(u,u));
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            vis[u][v] = vis[v][u] = 1;
            if(col[u] != col[v]) continue;
            dp[u][v] = dp[v][u] = 1; q.push(pii(u,v));
        }
    }
    for(int x,y; !q.empty(); )
    {
        tie(x,y) = q.front(); q.pop();
        for(int i=head[x]; i; i=e[i].next)
            for(int j=head[y]; j; j=e[j].next)
            {
                int a = e[i].v, b = e[j].v;
                if(!vis[a][b] && col[a] == col[b])
                { dp[a][b] = dp[b][a] = 1; q.push(pii(a,b)); }
                vis[a][b] = vis[b][a] = 1;
            }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    scanf("%lld%lld%lld\n%s\n",&n, &m, &Q, col+1);
    for(int i=1,u,v; i<=m; i++)
    {
        read(u); read(v); // scanf("%lld%lld",&u,&v);
        Graph::addEdge(u,v); Graph::addEdge(v,u);
        if(col[u] != col[v]) diff[++cd] = pii(u,v);
        else same[++cs] = pii(u,v);
    }
    MST::kruskal(1); MST::kruskal(2); solve();
    for(int u,v; Q--; )
    {
        read(u); read(v); // scanf("%lld%lld",&u,&v);
        puts((dp[u][v] | dp[v][u]) ? "YES" : "NO");
    }
    return 0;
}