GYM 100685 G【并查集】

迷南。 2022-08-04 14:40 120阅读 0赞

一开始看题就水了一发bitset，本地是没有什么问题，但是交上去果断地MLE了。

那么就想到乱搞，假设将其变成一颗有根树，如果dfs的时候走的是正的边，就在正的并查集里面merge，如果走的是负的边，就在反的并查集里面merge。

对于一个查询，查询一下他们的LCA，如果他们的LCA，在u（或者v）正的并查集中，在另一个反的并查集内，那么就是可以访问，否则不行。

大家可以脑补一下图像，必然是这样的。

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #define MAXN 100005
    
    using namespace std;
    
    int fa1[MAXN],fa2[MAXN];
    
    int n,m;
    int depth[MAXN];
    
    int Index;
    int head[MAXN],nxt[2*MAXN],node[2*MAXN];
    
    int from[MAXN],to[MAXN];
    
    int p[MAXN][20];
    int deep[MAXN];
    
    void init()
    {
        Index = 0;
        memset(head,0,sizeof(head));
        memset(nxt,0,sizeof(nxt));
    
        deep[1] = 0;
        p[1][0] = 1;
    
        for(int i=1;i<=n;i++)
        {
            fa1[i] = i;
            fa2[i] = i;
        }
    }
    
    void addedge(int u,int v)
    {
        Index++;
        nxt[Index] = head[u];
        node[Index] = v;
        head[u] = Index;
    }
    
    void dfs(int ret,int fa=-1)
    {
        for(int j=1;j<20;j++)
            p[ret][j] = p[p[ret][j-1]][j-1];
    
        for(int o=head[ret];o;o=nxt[o])
            if(node[o] != fa)
            {
                p[node[o]][0] = ret;
                deep[node[o]] = deep[ret] + 1;
                dfs(node[o],ret);
            }
    }
    
    int getLca(int u,int v)
    {
        if(deep[u] > deep[v])
            swap(u,v);
    
        for(int delta = deep[v]-deep[u],i=0;delta!=0;delta>>=1,++i)
            if(delta & 1) v = p[v][i];
    
        if(u == v) return u;
    
        for(int i=19;i>=0;i--)
        {
            if(p[u][i] == p[v][i]) continue;
            u = p[u][i],v = p[v][i];
        }
        return p[u][0];
    }
    
    int getfather1(int x)
    {
        if(fa1[x] == x) return x;
        else return fa1[x] = getfather1(fa1[x]);
    }
    
    int getfather2(int x)
    {
        if(fa2[x] == x) return x;
        else return fa2[x] = getfather2(fa2[x]);
    }
    
    int main()
    {
        scanf("%d",&n);
        init();
    
        for(int i=1;i<n;i++)
        {
            scanf("%d%d",&from[i],&to[i]);
            addedge(from[i],to[i]);
            addedge(to[i],from[i]);
        }
    
        dfs(1);
    
        for(int i=1;i<n;i++)
        {
            if(deep[from[i]] > deep[to[i]]) fa1[getfather1(from[i])] = getfather1(to[i]);
            else fa2[getfather2(from[i])] = getfather2(to[i]);
        }
    
        scanf("%d",&m);
    
        for(int i=1;i<=m;i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            int shit = getLca(x,y);
            //cout<<shit<<endl;
            if(getfather1(x) == getfather1(shit) && getfather2(y) == getfather2(shit)) printf("Yes\n");
            else printf("No\n");
        }
        return 0;
    }