【题解】DZY Loves Chinese

【题解】DZY Loves Chinese II

不吐槽这题面了...

考虑如何维护图的连通性，如果把图的变成一颗的\(dfs\)生成树，那么如果把一个节点的父边和他接下来所有的返祖边删除，那么我们就可以确定图的连通性改变了。

考虑如何快速维护这个东西。

可以考虑这样

对于每条非树边，给他一个随机数的权值。
对于每条树边，他的权值是横跨他的所有非树边的\(xor\)和。

那么也就是说，将非树边的状态通过\(xor\)压缩2到其他树边上了。树边的权值是由与他有关的非树边决定的。

查询的时候建基底，如果有数到最后被基底表示出来了，连通性就发生了变化。

正确性(忽略随机数的影响)我不知道怎么说，分情况讨论吧。

假设多条权值一样的在集合内
- 可能都是树边->权值一样代表这些点在一条链上，一条链断开了\(\ge 2\)条边，就算有一条非树边的帮助，肯定发生了连通性的改变。
- 可能有一条返祖边->树边的后路被切断了，切掉这两条边后，肯定有节点脱节了。
假设不存在多条权值一样的在几何内，但是有的权值被线性基表示出来了
- 说明有至少一个点，横跨他的所有返祖边都被切断了，自己的树边也被切断了。
假设这些点是线性无关的，不存在被表示出来的情况
- 说明不存在有点的返祖边和树边被同时切断，说明图的连通性没有改变。

这道题其实也启示了我们一个做题的技巧，可以利用线性基将许多状态都压缩起来。

最终时间复杂度\(O(32qk)\)很快了

#include<bits/stdc++.h>

using namespace std;

#define RP(t,a,b) for(register int t=(a),edd_=(b);t<=edd_;(t)++)

#define DRP(t,a,b) for(int t=(a),edd_=(b);t>=edd_;(t)--)

#define ERP(t,a) for(register int t=head[a];t!=-1;t=e[t].nx)

#define TMP template < class ccf>

typedef long long ll;

#define Max(a,b) ((a)>(b)?(a):(b))

TMP inline ccf qr(ccf b) {

	char c=getchar();

	int q=1;

	ccf x=0;

	while(c<48||c>57)

		q=c==45?-1:q,c=getchar();

	while(c>=48&&c<=57)

		x=x*10ll+c-48,c=getchar();

	return q==-1?-x:x;

}

const int maxm=500005;

const int maxn=100005;

struct E {

	int to,nx;

} e[maxm<<1];

int cnt(1);

int head[maxn];

inline void add(int fr,int to,bool f) {

	cnt++;

	e[cnt].to=to;

	e[cnt].nx=head[fr];

	head[fr]=cnt;

	if(f)

		add(to,fr,0);

}

int ew[maxm];

int dfn[maxn];

int had[maxn];

int timer;

void dfs(int now,int last) {

	dfn[now]=++timer;

	ERP(t,now) {

		if(e[t].to!=last) {

			if(!dfn[e[t].to]) {

				dfs(e[t].to,now);

				had[now]^=had[e[t].to];

				ew[t>>1]=had[e[t].to];

			} else if(dfn[now]>dfn[e[t].to]) {

				register int x=rand();

				ew[t>>1]=x;

				had[e[t].to]^=x;

				had[now]^=x;

			}

		}

	}

}

int base[35];

int num[35];

inline int upd(int x) {

	DRP(t,31,1) {

		if(x&num[t]) {

			if(base[t])

				x^=base[t];

			else {

				base[t]=x;

				break;

			}

		}

	}

	return x==0;

}

int q,n,k,m;

int t1,t2,t3;

int sigma,temp;

int main() {

	memset(head,-1,sizeof head);

	srand(19491001);

	num[1]=1;

	RP(t,2,32)

	num[t]=num[t-1]<<1;

//	cout<<(int)'0'<<' '<<(int)'9'<<' '<<(int)'-'<<endl;

	n=qr(1);

	m=qr(1);

	RP(t,1,m) {

		t1=qr(1);

		t2=qr(1);

		add(t1,t2,1);

	}

	dfs(1,0);

	q=qr(1);

	RP(t0,1,q) {

		k=qr(1);

		temp=1;

		memset(base,0,sizeof base);

		RP(qaqqqq,1,k) {

			register int x=ew[qr(1)^sigma];

			if(upd(x))

				temp=0;

		}

		sigma+=temp;

		if(temp)

			puts("Connected");

		else

			puts("Disconnected");

	}

	return  0;

}

巴特西

【题解】DZY Loves Chinese

【题解】DZY Loves Chinese II

最新文章

热门文章