随机值的一些应用

发表于

闲扯

最近做的一些题里面用到了使用随机值来维护图的连通性和判断点对是否包含某条边，写篇博客总结一下。

TEST_20200112(Day 2) T3

题目描述

给出一个连通图，每次删掉不超过 $4$ 条边，然后询问整幅图是否连通。

Solution

正常做法：

线段树分治。

非正常解法乱搞：

先搞一颗生成树出来，然后给非树边赋一个随机权值。

然后给树边赋值，将除根结点外每个点的出边的异或值调整为 $0$ 。

每次询问时，枚举删掉的边的子集，如果存在一个子集，使得边权异或为 $0$ ，那么这个子集使得一个子图恰好与外部分开。

Code

吐槽一下这个从 std 学来的随机值是真的强，直接弄会被卡

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<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 1e5+5;
int n,m,q,u,v,k,p[5],fa[N];
char vis[N];
pair<int,int> edge[N];
vector<pair<int,int> > G[N];
il add_edge(int id,int u,int v){
	G[u].push_back(make_pair(v,id));
	G[v].push_back(make_pair(u,id));
}
it find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
ll val[N],s[N];
ll Rand(){
	return ((ll)rand()<<48ll)+((ll)rand()<<32ll)+((ll)rand()<<16ll)+(ll)rand();
}
il DFS(int u,int fa){
	for(auto _:G[u]){
		int v=_.first,id=_.second;
		if(v==fa) continue;
		DFS(v,u),val[id]=s[v];
		s[v]^=val[id],s[u]^=val[id];
	}
}
int main(){
	freopen("disconnected.in","r",stdin);
	freopen("disconnected.out","w",stdout);
	srand(time(0));
	read(n),read(m);
	for(ri i=1;i<=n;++i) fa[i]=i;
	for(ri i=1;i<=m;++i){
		read(u),read(v);
		edge[i]=make_pair(u,v);
		if(find(u)==find(v)) continue;
		vis[i]=1,fa[find(u)]=find(v),add_edge(i,u,v);
	}
	for(ri i=1;i<=m;++i){
		if(vis[i]) continue;
		val[i]=Rand();
		u=edge[i].first,v=edge[i].second;
		s[u]^=val[i],s[v]^=val[i];
	}
	DFS(1,0),read(q);
	for(ri i=1;i<=q;++i){
		read(k);
		for(ri j=1;j<=k;++j)
			read(p[j]);
		char flag=0;
		for(ri T=1;T<(1<<k);++T){
			ll sum=0;
			for(ri j=1;j<=k;++j)
				if(T&(1<<(j-1)))
					sum^=val[p[j]];	
			flag|=sum==0;
		}
		puts(flag?"Disconnected":"Connected");
	}
	return 0;
}

共价大爷游长沙

题面

题面

Solution

每次询问一条边是否被所有路径覆盖，我们有一个很巧妙的做法。

给每一个操作赋值，把两端的值异或上这个值，。

那么每次相当于求以 $x$ 为根节点时， $y$ 子树中的所有点权异或起来是否等于所有操作的值的异或和。

由于有动态加边、删边，所以用 $LCT$ 来维护子树信息即可。

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
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
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define ull unsigned ll
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define mid ((l+r)>>1)
#define lowbit(x) (x&(-x))
#define INF 0x3f3f3f3f
using namespace std;
template<class T>il read(T &x){
	int f=1;char k=getchar();x=0;
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=(x<<3)+(x<<1)+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x/10) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
ll mul(ll a,ll b,ll mod){long double c=1.;return (a*b-(ll)(c*a*b/mod)*mod)%mod;}
it qpow(int x,int m,int mod){
	int res=1,bas=x;
	while(m){
		if(m&1) res=(1ll*res*bas)%mod;
		bas=(1ll*bas*bas)%mod,m>>=1;
	}
	return res;
}
const int N = 1e5+5;
int id,n,m,u,v,num,opt,x,y;
int ch[N][2],f[N],stk[N];
ull sum,s[N],is[N],val[N];
char rev[N];
#define lc ch[x][0]
#define rc ch[x][1]
inl bool Not_root(int x){return ch[f[x]][0]==x||ch[f[x]][1]==x;}
il pushup(int x){s[x]=s[lc]^s[rc]^is[x]^val[x];}
il pushrev(int x){swap(lc,rc),rev[x]^=1;}
il pushdown(int x){
	if(rev[x]){
		if(lc) pushrev(lc);
		if(rc) pushrev(rc);
		rev[x]^=1;
	}
}
il Rotate(int x){
	int y=f[x],z=f[y],k=ch[y][1]==x,w=ch[x][!k];
	if(Not_root(y)) ch[z][ch[z][1]==y]=x;
	ch[x][!k]=y,ch[y][k]=w;
	if(w) f[w]=y;
	f[x]=z,f[y]=x,pushup(y);
}
il Splay(int x){
	int y=x,top=0;
	stk[++top]=y;
	while(Not_root(y)) stk[++top]=y=f[y];
	while(top) pushdown(stk[top--]);
	while(Not_root(x)){
		int y=f[x],z=f[y];
		if(Not_root(y)) Rotate((ch[y][0]==x)^(ch[z][0]==y)?x:y);
		Rotate(x);
	}
	pushup(x);
}
il Access(int x){
	for(ri y=0;x;x=f[y=x]){
		Splay(x);
		is[x]^=s[rc]^s[y];
		rc=y,pushup(x);
	}
}
il Make_root(int x){Access(x),Splay(x),pushrev(x);}
il Split(int x,int y){Make_root(x),Access(y),Splay(y);}
il Link(int x,int y){
	Make_root(x),Make_root(y);
	f[x]=y,is[y]^=s[x],pushup(y);
}
il Cut(int x,int y){Split(x,y),f[x]=ch[y][0]=0,pushup(y);}
struct Node{int u,v;ull w;}node[N<<2];
inl ull Rand(){ull res=1;for(ri i=1;i<=5;++i) res*=rand();return res;}
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	srand(time(0));
	read(id),read(n),read(m);
	for(ri i=1;i<n;++i)
		read(u),read(v),Link(u,v);
	for(ri i=1;i<=m;++i){
		read(opt);
		if(opt==1){
			read(x),read(y),Cut(x,y);
			read(x),read(y),Link(x,y);
		}
		if(opt==2){
			read(x),read(y);
			node[++num]=(Node){x,y,Rand()},sum^=node[num].w;
			Split(x,y),val[y]^=node[num].w;
			Split(y,x),val[x]^=node[num].w;
		}
		if(opt==3){
			read(id),x=node[id].u,y=node[id].v,sum^=node[id].w;
			Split(x,y),val[y]^=node[id].w;
			Split(y,x),val[x]^=node[id].w;
		}
		if(opt==4){
			read(x),read(y),Split(x,y);
			puts(s[x]==sum?"YES":"NO");
		}
	}
	return 0;
}