bzoj 3569 DZY Loves Chinese II

Posted on | Edited on | Views:

神仙题.

先做出原图的一棵 $dfs$ 树.对于每条非树边,随机分配一个权值 $x$ ,将它在树上覆盖到的树边的权值全部异或上 $x$ .

每次询问给定了一个边的集合 $S$ ,若存在 $S$ 的一个非空子集,该子集内所有的边权异或和为 $0$ ,则不连通,否则连通.

边权覆盖可以用树上差分,查询可以利用线性基,看给出的边权在 $\mbox{xor}$ 意义下是否线性无关.

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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int read()
{
	int out=0,sgn=1;
	char jp=getchar();
	while(jp!='-' && (jp<'0' || jp>'9'))
		jp=getchar();
	if(jp=='-')
		sgn=-1,jp=getchar();
	while(jp>='0' && jp<='9')
		out=out*10+jp-'0',jp=getchar();
	return out*sgn;
}
const int MAXN=1e5+10,MAXM=1e6+10;
int ecnt=0,head[MAXN],nx[MAXM],to[MAXM],id[MAXM];
int st[MAXM],ed[MAXM],ontree[MAXM];
void addedge(int u,int v,int k)
{
	++ecnt;
	id[ecnt]=k;
	to[ecnt]=v;
	nx[ecnt]=head[u];
	head[u]=ecnt;
}
int n,m,tot=0;
int dfn[MAXN],idx=0;
ull dif[MAXN],val[MAXM];
void dfs(int u)
{
	dfn[u]=++idx;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(dfn[v])
			continue;
		ontree[id[i]]=1;
		dfs(v);
	}
}
void calc(int u,int t)
{
	dfn[u]+=n;
	for(int i=head[u];i;i=nx[i])
	{
		int v=to[i];
		if(dfn[v]>n)
			continue;
		calc(v,i);
		dif[u]^=dif[v];
	}
	val[id[t]]=dif[u];
}
void init()
{
	for(int i=1;i<=m;++i)
		if(!ontree[i])
		{
			ull x=rand()*rand()*rand()*rand();
			val[i]=x;
			int u=st[i],v=ed[i];
			dif[u]^=x,dif[v]^=x;
		}
	calc(1,0);
}
struct Base
{
	ull a[64];
	int siz;
	void init()
	{
		siz=0;
		memset(a,0,sizeof a);
	}
	void ins(ull x)
	{
		for(int i=63;i>=0;--i)
			if(x&(1ULL<<i))
			{
				if(a[i])
					x^=a[i];
				else
				{
					a[i]=x;
					++siz;
					break;
				}
			}
	}
}LB;
int main()
{
	n=read(),m=read();
	for(int i=1;i<=m;++i)
	{
		int u=read(),v=read();
		addedge(u,v,i);
		addedge(v,u,i);
		st[i]=u,ed[i]=v;
	}
	dfs(1);
	int Q=read();
	if(idx!=n)
	{
		while(Q--)
			puts("Disconnected");
		return 0;
	}
	srand(time(NULL));
	init();
	while(Q--)
	{
		int k=read();
		LB.init();
		for(int i=1;i<=k;++i)
		{
			int c=read()^tot;
			LB.ins(val[c]);
		}
		if(k==LB.siz)
			++tot,puts("Connected");
		else
			puts("Disconnected");
	}
	return 0;
}