bzoj 3569 DZY Loves Chinese II 随机算法树上倍增

朴灿烈づ我的快乐病毒、 2023-08-17 17:22 88阅读 0赞

题意：给你一个n个点m条边的图，有若干组询问，每次询问会选择图中的一些边删除，删除之后问此图是否联通？询问之间相互独立。此题强制在线。

思路：首先对于这张图随便求一颗生成树，对于每一条非树边，随机一个权值。树边的权值为所有覆盖这条树边的非树边的权值异或和。覆盖是指这条边是个返祖边，并且一端在父节点方向，一端在子节点方向。这样，我们选出若干条边，看一下他们异或起来是不是0，如果是0，那么相当于把一条树边和它的所有子节点方向的返祖边全部断开，那么图就不连通了。

代码：

#include <bits/stdc++.h>
    #define LL long long
    #define pii pair<int, int>
    using namespace std;
    const int maxn = 100010;
    const int maxm = 500010;
    const LL mod = 1e18;
    mt19937 Random(time(0));
    LL get(void) {
    	return 1ll * Random() * rand();
    }
    vector<pii> G[maxn], G1[maxn];
    LL val[maxn];
    int d[maxn], f[maxn][18], t;
    bool v[maxn], v1[maxm];
    struct edge {
    	int u, v;
    	LL w;
    };
    edge a[maxm];
    void add(int x, int y, int id) {
    	G[x].push_back(make_pair(y, id));
    	G[y].push_back(make_pair(x, id));
    }
    void add1(int x, int y, int id) {
    	G1[x].push_back(make_pair(y, id));
    	G1[y].push_back(make_pair(x, id));
    }
    void dfs(int x) {
    	v[x] = 1;
    	for (auto y : G[x]) {
    		if(v[y.first]) continue;
    		dfs(y.first);
    		add1(x, y.first, y.second);
    		v1[y.second] = 1;
    	}
    }
    
    queue<int> q;
    void bfs() {
    	q.push(1);
    	d[1] = 1;
    	while(q.size()) {
    		int x = q.front();
    		q.pop();
    		for (auto y : G1[x]) {
    			if(d[y.first]) continue;
    			d[y.first] = d[x] + 1;
    			f[y.first][0] = x;
    			for (int i = 1; i <= t; i++) {
    				f[y.first][i] = f[f[y.first][i - 1]][i - 1];
    			}
    			q.push(y.first);
    		}
    	}
    }
    
    int lca(int x, int y) {
    	if(d[x] > d[y]) swap(d[x], d[y]);
    	for (int i = t; i >= 0; i--) {
    		if(d[f[y][i]] >= d[x]) y = f[y][i];
    	}
    	if(x == y) return x;
    	for (int i = t; i >= 0; i--) {
    		if(f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];
    	}
    	return f[x][0];
    	
    }
    LL dfs1(int x, int fa) {
    	for (auto y : G1[x]) {
    		if(y.first == fa) continue;
    		dfs1(y.first, x);
    		a[y.second].w = val[y.first];
    		val[x] ^= val[y.first];
    	}
    }
    struct L_B{
        long long d[61],p[61];
        int cnt;
        void init(){
            memset(d,0,sizeof(d));
            memset(p,0,sizeof(p));
            cnt=0;
        }
        bool insert(long long val){
            for (int i=60;i>=0;i--)
                if (val&(1LL<<i))
                {
                    if (!d[i])
                    {
                        d[i]=val;
                        break;
                    }
                    val^=d[i];
                }
            return val>0;
        }
        long long query_max() {
            long long ret=0;
            for (int i=60;i>=0;i--)
                if ((ret^d[i])>ret)
                    ret^=d[i];
            return ret;
        }
        long long query_min() {
            for (int i=0;i<=60;i++)
                if (d[i])
                    return d[i];
            return 0;
        }
        void rebuild() {
            for (int i=60;i>=0;i--)
                for (int j=i-1;j>=0;j--)
                    if (d[i]&(1LL<<j))
                        d[i]^=d[j];
            for (int i=0;i<=60;i++)
                if (d[i])
                    p[cnt++]=d[i];
        }
        long long kthquery(long long k) {
            int ret=0;
            if (k>=(1LL<<cnt))
                return -1;
            for (int i=60;i>=0;i--)
                if (k&(1LL<<i))
                    ret^=p[i];
            return ret;
        }
    };
    int main() {
    	int n, m, cnt = 0, x, y, num, T;
    	srand(time(0));
    	scanf("%d%d", &n, &m);
    	t = (int)(log(n) / log(2)) + 1;
    	for (int i = 1; i <= m; i++) {
    		scanf("%d%d", &a[i].u, &a[i].v);
    		add(a[i].u, a[i].v, i);
    	}
    	dfs(1);
    	bfs();
    	for (int i = 1; i <= m; i++) {
    		if(v1[i]) continue;
    		a[i].w = get();
    		int tmp = lca(a[i].u, a[i].v);
    		val[a[i].u] ^= a[i].w;
    		val[tmp] ^= a[i].w;
    		val[a[i].v] ^= a[i].w;
    		val[tmp] ^= a[i].w;
    	}
    	dfs1(1, -1);
    	scanf("%d", &T);
    	while(T--) {
    		scanf("%d", &num);
    		bool flag = 1;
    		L_B solve;
    		solve.init();
    		for (int i = 1; i <= num; i++) {
    			scanf("%d", &x);
    			x ^= cnt;
    			flag = (flag & solve.insert(a[x].w));
    		}
    		if(flag == 0) {
    			printf("Disconnected\n");
    		} else {
    			printf("Connected\n");
    			cnt++;
    		}
    	}
    }

转载于:https://www.cnblogs.com/pkgunboat/p/11447347.html