BZOJ 3569 DZY Loves Chinese II

发表于 | 更新于

Link

神校XJ之学霸兮，Dzy皇考曰JC。 摄提贞于孟陬兮，惟庚寅Dzy以降。 纷Dzy既有此内美兮，又重之以修能。 遂降临于OI界，欲以神力而凌辱众生。 今Dzy有一魞歄图，其上有N座祭坛，又有M条膴蠁边。 时而Dzy狂WA而怒发冲冠，神力外溢，遂有K条膴蠁边灰飞烟灭。 而后俟其日A50题则又令其复原。（可视为立即复原） 然若有祭坛无法相互到达，Dzy之神力便会大减，于是欲知其是否连通。

Solution

什么鬼！ 求出图的一个生成树。如果割掉一条树边之后想让图不连通，必须割掉所有可以连接树边两端的联通块的回边，称为覆盖着这条树边的边。 然后很神奇地给每个回边随机一个值，那么只要求出所有覆盖某条被删掉的树边的回边的异或和，然后看一下集合中能否异或出来这个值就行了。那就等价于，给每个树边的一个权值，权值为所有覆盖这条树边的回边的异或和，这样只要看删掉的边集的权值是否线性无关。 求树边的权值的过程也很高能 在每个点维护一个值vv，给每条回边随机上一个值之后，用这个值在异或一下回边的两端的点的vv。这样的话，自底向上DFS，一条树边的权值就是树边指向的子树vv的异或和。因为只有一端在这个点下方的回边才会被计算进去，如果起点和终点都在下方，异或两下就没了。

Tips

“异或两下就没了” “随机+异或”做hash

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include "lucida"
typedef unsigned long long qword;
using std::fill;
const int MAXN=100000+11,MAXM=500000+11;
struct Edge {
	int to,id;Edge *pre;
	Edge(int to,int id,Edge *pre):to(to),id(id),pre(pre) {}
	void *operator new(size_t) {
		static Edge *Me=alloc(Edge,MAXM<<1);
		return Me++;
	}
}*G[MAXN];
void Adde(int f,int t,int id) {
	G[f]=new Edge(t,id,G[f]);
	G[t]=new Edge(f,id,G[t]);
}
qword ehava[MAXM],phava[MAXN];bool ud[MAXN];
void DFS(int pos,int from) {
	ud[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre) {
		if(e->to!=from) {
			int u=e->to;
			if(ud[u]) {
				if(!ehava[e->id]) {
					ehava[e->id]=(qword)rand()<<31|rand();//回边
					phava[pos]^=ehava[e->id];
					phava[u]^=ehava[e->id];
				}
			} else {
				DFS(u,pos);
			}
		}
	}
}
void Calc(int pos) {
	ud[pos]=1;
	for(Edge *e=G[pos];e;e=e->pre) {
		int u=e->to;
		if(!ud[u]) {
			Calc(u);
			ehava[e->id]=phava[u];
			phava[pos]^=phava[u];
		}
	}
}
bool Query(int lis[],int n) {
	static qword a[62];
	fill(a,a+62,0);
	for(int i=1;i<=n;++i) {
		qword x=ehava[lis[i]];
		for(int lg=61;~lg;--lg) {
			if(x>>lg&1) {
				if(!a[lg]) {
					a[lg]=x;
					break;
				} else {
					x^=a[lg];			
				}
			}
		}
		if(!x) {
			return 0;
		}
	}
	return 1;
}
int main() {
	//我一定要在八点之前把这道题彻底搞懂并A掉！
	freopen("input","r",stdin);
	srand(0x1f1f1f1f);
	int n,m;is>>n>>m;
	static struct {int x,y;}edges[MAXM];
	for(int i=1;i<=m;++i) {
		is>>edges[i].x>>edges[i].y;
		Adde(edges[i].x,edges[i].y,i);
	}
	fill(ud+1,ud+1+n,0);DFS(1,0);
	fill(ud+1,ud+1+n,0);Calc(1);
	int counter=0;
	#define decode(x) (x^=counter)
	static int cut[20],ec;
	int Q;is>>Q;
	for(int i=1;i<=Q;++i) {
		is>>ec;
		for(int j=1;j<=ec;++j) {
			is>>cut[j];
			decode(cut[j]);
		}
		bool Ans=Query(cut,ec);
		counter+=Ans;
		os<<(Ans?"Connected":"Disconnected")<<'\n';
	}
	return 0;
}