生成树小节

, ,

生成树小结

参考 fls 7.18 的课件，收获颇多。

Boruvka 算法

不知道怎么读。

Boruvka 算法可以看作 Prim 的并行版本，它基于两个事实：

  • 已经加入最小生成树的边的两端点可以看作一个点。

  • 和每个点相连的最小的边一定在最小生成树中。

算法流程如下：

  • 初始时将每个点视为一个联通块，每一轮处理对于每个联通块找到到其它联通块最小的边。

  • 将这些边加入MST中，当联通块只有一个时结束，否则回到第一步

时间复杂度可以从两方面证明：

  • 每次结束后联通块个数至多为原来的一半，至多 $O(\log n )$。
  • 每次结束后最小联通块的大小至少为原来的两倍，只会进行 $O(\log n)$ 次。

总时间复杂度 $O(m\log m)$。

在特殊性质的完全图上具有优势。

1. CF1550F Jumping Around

Description

数轴上顺次有 $n$ 个点 $a_1 < a_2 < \cdots < a_n$。

有一只小青蛙，初始时在 $a_s$ 处。小青蛙有两个参数：步长 $d$ 和灵活程度 $k$。其中，步长 $d$ 是确定的，而灵活程度 $k$ 是可以调整的。

小青蛙可以从某个点跳到另一个点。但这是有要求的：小青蛙能从 $a_i$ 跳到 $a_j$，当且仅当 $d-k\leq |a_i-a_j|\leq d+k$。

给定 $a_1,…,a_n$ 和 $d$。你需要回答 $q$ 次询问，每次询问给定一个灵活程度 $k$ 和一个下标 $i$，你需要回答：此时的小青蛙能否跳到 $a_i$？

保证 $1\leq n,q\leq 2\times 10^5$，$1\leq s,i\leq n$，$1\leq a_i,d,k\leq 10^6$，$a_1 < a_2 < \cdots < a_n$。

5s , 250MB

Solution

观察到 $d-k\le |a_i-a_j|\le d+k\iff ||a_i-a_j|-d|\le k$

不妨把 $(i,j)$ 连边，$||a_i-a_j|-d|$ 作为边权。两点在最小生成树上的简单路径上的最大边权即为互通所需要的最小灵活程度。

这是一个具有特殊性质的完全图。

钦定 $a_i\ge a_j$，则边权为 $|a_i-a_j-d|=|(a_i-d)-a_j|$

考虑 Boruvka 算法，每次找到 $a_i-d$ 左右最近的且不在一个连通块的数，用 set 维护是这个过程，每次是 $O(n\log n)$ 的。链表则是 $O(n)$ 的。

这里使用了链表。建出最小生成树后，以 $s$ 为根遍历一遍树即可。

复杂度 $O(n\log n)$。

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int fa[maxn],n,q,d,s;
const int inf=1e9;
inline int getfa(int x) {
	assert(x>=0);
	if (x<0) return 0;
	return x==fa[x]?x:fa[x]=getfa(fa[x]);
}
vector<int>to[maxn];
#define M 1000005
int a[maxn],t[M],nex[M],pre[M],tot;
int w[maxn],v[maxn],z[maxn],pree[M],nexx[M];
inline void solve(void) {
	int las=0,i,tmp,id,now=0;
	for (i=0;i<=a[n]+1;i++) {
		pre[i]=now;
		if (t[i]) {
			if (!now||getfa(t[i])!=getfa(t[now])) las=now;
			now=i;
		} 
		pree[i]=las;
	}  
	las=now=0;
	for (i=a[n]+1;i>=0;i--) {
		nex[i]=now;
		if (t[i]) {
			if (!now||getfa(t[i])!=getfa(t[now])) las=now;
			now=i;
		}
		nexx[i]=las;
	}
	for (i=1;i<=n;i++) w[i]=0,z[i]=1e9;
	for (i=1;i<=n;i++) {
		id=getfa(i);
		tmp=pre[max(0,a[i]-d+1)];
		if (a[i]-d>=1) {
			if (tmp&&getfa(i)!=getfa(t[tmp])) {
				tmp=t[tmp];
				if (!w[id]||z[id]>abs(a[i]-d-a[tmp])) {
					w[id]=tmp,v[id]=i,z[id]=abs(abs(a[i]-a[tmp])-d);
				}
			}
			else if (tmp&&pree[tmp]&&getfa(i)!=getfa(t[pree[tmp]])) {
				tmp=t[pree[tmp]];
				if (!w[id]||z[id]>abs(a[i]-d-a[tmp])) {
					w[id]=tmp,v[id]=i,z[id]=abs(abs(a[i]-a[tmp])-d);
				}
			}
		}
		tmp=nex[max(0,a[i]-d-1)];
		if (tmp&&getfa(i)!=getfa(t[tmp])&&tmp<=a[i]) {
			tmp=t[tmp];
			if (!w[id]||z[id]>abs(-a[tmp]+a[i]-d)) {
				w[id]=tmp,v[id]=i,z[id]=abs(abs(a[i]-a[tmp])-d);
			}
		}
		else {
			if (tmp&&nexx[tmp]&&getfa(i)!=getfa(t[nexx[tmp]])&&nexx[tmp]<=a[i]) {
				tmp=t[nexx[tmp]];
				if (!w[id]||z[id]>abs(-a[tmp]+a[i]-d)) {
					w[id]=tmp,v[id]=i,z[id]=abs(abs(a[i]-a[tmp])-d);
				}
			}	
		}
		
		id=getfa(i);
		tmp=pre[min(a[n]+1,a[i]+d+1)];
		if (tmp&&getfa(i)!=getfa(t[tmp])&&tmp>=a[i]) {
			tmp=t[tmp];
			if (!w[id]||z[id]>abs(abs(a[i]-a[tmp])-d)) {
				w[id]=tmp,v[id]=i,z[id]=abs(abs(a[i]-a[tmp])-d);
			}
		}
		else if (tmp&&pree[tmp]&&getfa(i)!=getfa(t[pree[tmp]])&&pree[tmp]>=a[i]) {
			tmp=t[pree[tmp]];	
			if (!w[id]||z[id]>abs(abs(a[i]-a[tmp])-d)) {
				w[id]=tmp,v[id]=i,z[id]=abs(abs(a[i]-a[tmp])-d);
			}
		}
		tmp=nex[min(a[n]+1,a[i]+d-1)];
		if (a[i]+d<=a[n]) {
			if (tmp&&getfa(i)!=getfa(t[tmp])) {
				tmp=t[tmp];
				if (!w[id]||z[id]>abs(abs(a[i]-a[tmp])-d)) {
					w[id]=tmp,v[id]=i,z[id]=abs(abs(a[i]-a[tmp])-d);
				}
			}
			else if (tmp&&nexx[tmp]&&getfa(i)!=getfa(t[nexx[tmp]])) {
				tmp=t[nexx[tmp]];	
				if (!w[id]||z[id]>abs(abs(a[i]-a[tmp])-d)) {
					w[id]=tmp,v[id]=i,z[id]=abs(abs(a[i]-a[tmp])-d);
				}
			}	
		}
	}
	for (i=1;i<=n;i++) {
		int id=getfa(i);
		if (w[id]&&id!=getfa(w[id])) {
			assert(z[id]==abs(abs(a[v[id]]-a[w[id]])-d));
			tot--;
			fa[id]=getfa(w[id]);
			to[v[id]].push_back(w[id]);
			to[w[id]].push_back(v[id]);
		}
	}
}
int dis[maxn];
inline void dfs(int x,int pre) {
	int i;
	for (auto y:to[x]) if (y^pre) {
		dis[y]=max(dis[x],abs(abs(a[x]-a[y])-d));
		dfs(y,x);
	}
}
signed main(void){
	int i,x,y;
	read(n);read(q);read(s);read(d);
	for (i=1;i<=n;i++) read(a[i]),fa[i]=i,t[a[i]]=i;
	tot=n;
	while (tot>1) solve();
	dis[s]=0;
	dfs(s,0);
	while (q--) {
		read(x);read(y);
		puts(dis[x]<=y?"Yes":"No");
	}
	return 0;
}

2. CF1305G Kuroni and Antihype

Description

现在有 $n$ 个人，并且给出他们的年龄。两个人是朋友，当且仅当两个人年龄的按位与结果为 $0$。

现在，有一个传销组织，每个人有两种操作：

  1. 主动加入传销组织，这样的话，传销组织不会给你钱；

  2. 邀请自己的一个朋友加入传销组织，这样的话，传销组织会奖励你数值等于你的年龄的钱。（当然，执行该操作的人必须已经进入传销组织了）

每个人只可以进入传销组织一次。

求如果 $n$ 个人通力合作，传销组织支付给这 $n$ 个人的钱数之和最大是多少。

$1\le n\le 2\times 10^5,0\le a_i\le 2\times 10^5$

3s , 250MB

Solution

建立虚点 $n+1$ ，$a_{n+1}=0$。

两个点 $i,j$ 连边当且仅当按位与为 $0$，权值为 $a_i+a_j$。

找出最大生成树。最后答案减去 $\sum a_i$。容易发现这么做是对的，而且很妙。

考虑 Boruvka 算法，每次找到与自己不在一个连通块，且按位与为 $0$ 的最大的数。可以用 SOSdp 维护不在同一个连通块的最大值和不严格次大值。

复杂度 $O((2^{B}B+n)\log n)$，本题中 $B=\log w=18$。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
const int base=18,N=1<<base;
int n,a[maxn];
#define fi first
#define se second
const int inf=1e12;
struct yyy{
	int id,w;
	yyy(int a=0,int b=-inf) {id=a;w=b;}
}rt[5];
inline bool cmp(yyy x,yyy y) {return x.w>y.w;}
struct node{
	yyy x,y;
	node operator +(const node &tmp) const {
		rt[0]=x,rt[1]=y,rt[2]=tmp.x,rt[3]=tmp.y;
		sort(rt,rt+4,cmp);
		node ans;
		ans.x=rt[0];
		for (int i=1;i<=3;i++) if (rt[i].id!=rt[0].id) {ans.y=rt[i];break;}
		return ans;
	}
}f[N+5];
int fa[maxn],tot,w[maxn],ans,v[maxn];
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void solve(void) {
	int i,j;
	for (i=1;i<=n;i++) w[i]=0;
	for (i=0;i<N;i++) f[i].x=f[i].y=yyy(0,-inf);
	for (i=1;i<=n;i++) {
		node tmp;
		tmp.x=yyy(getfa(i),a[i]);
		f[a[i]]=f[a[i]]+tmp;
	}
	for (i=0;i<base;i++) 	
		for (j=0;j<N;j++) if ((j>>i)&1){
			f[j]=f[j]+f[j^(1<<i)];
		}
	for (i=1;i<=n;i++) {
		int T=(N-1)^a[i];
		int id=getfa(i);
		if (f[T].x.id!=id) {
			if (w[id]<a[i]+f[T].x.w) {
				w[id]=a[i]+f[T].x.w;
				v[id]=getfa(f[T].x.id);
			}
		}
		else {
			if (w[id]<a[i]+f[T].y.w) {
				w[id]=a[i]+f[T].y.w;
				v[id]=getfa(f[T].y.id);
			}
		}
	}
	for (i=1;i<=n;i++) if (i==getfa(i)) {
		if (getfa(i)^getfa(v[i])) {
			fa[getfa(i)]=getfa(v[i]);
			ans+=w[i];
			tot--;
		}
	}
}
signed main(void){
	int i;
	read(n);
	for (i=1;i<=n;i++) read(a[i]),ans-=a[i];
	n++;tot=n;
	for (i=1;i<=n;i++) fa[i]=i;
	while (tot>1) solve();
	printf("%lld",ans);
	return 0;
}

3. IOI2021 Keys

待补

生成树的特殊求法/性质

有一个奇怪定理：

如果一张图的边集分为若干个子集，保证子集的交为原边集，则所有边子集的 MST 构成的边集的 MST 为原图的 MST。

有点绕，但是很好用。

1. THUPC2022初赛 A 最小公倍树

Description

点 $(i,j)$ 的边权为 $lcm(i,j)$ ，求点在 $[L,R]$ 中的最小生成树。

$1\le L\le R\le 10^6,R-L\le 10^5$

1s , 512MB

Solution

枚举公约数 $d$。$\forall i\in [L,R],d|i$ 的数组成的集合中，令其中最小的数为 $x$，最小生成树为其他点 $y$ 连向点 $x$，边权为 $\dfrac{xy}{d}$。因为求的是最小生成树，即使 $d$ 不是 $x,y$ 的最大公约数也不会对答案造成影响。

复杂度 $O(n\ln \log n)$，其中边的数量是 $O(n\ln n)$ 的。

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
#include<bits/stdc++.h>
#define ll long long
#define int long long
#define ull unsigned long long
#define maxn 1000005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int L,R;
struct node{
	int x,y,z;
}e[10000005];
int ans,fa[maxn],tot;
inline bool cmp(node x,node y) {return x.z<y.z;}
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
signed main(void){
	int i,j;
	read(L);read(R);
	for (j=1;j<=R;j++) {
		int minn=(L-1)/j*j+j;
		if (minn>R) continue;
		for (i=minn+j;i<=R;i+=j) ++tot,e[tot]=(node){minn,i,minn/j*i};
	}
	for (i=1;i<=R;i++) fa[i]=i;
	sort(e+1,e+1+tot,cmp);
	for (i=1;i<=tot;i++) {
		if (getfa(e[i].x)!=getfa(e[i].y)) {
			fa[getfa(e[i].x)]=getfa(e[i].y);
			ans+=e[i].z;
		}
	}
	printf("%lld",ans);
	return 0;
}

2. AT3611 Tree MST

Description

给定一棵 $n$ 个节点的树，现有有一张完全图，两点 $x,y$ 之间的边长为 $w_x+w_y+dis_{x,y}$，其中 $dis$ 表示树上两点的距离。

求完全图的最小生成树。

$n \leq 2 \times 10^5$。

5s , 256MB

Solution

由于对路径的形态没有要求，很自然的联想到点分治。

考虑点分治的过程，现在要求经过点 $r$ 的路径的 MST。枚举存在于不同子树中的两个点 $x,y$，$w_x+w_y+dis_{x,y}=(w_x+d_x)+(w_y+d_y)$ ，其中 $d_x$ 是 $x$ 到根 $r$ 的距离.

令树上 $w_x+d_x$ 最小的点为 $i$ 。对于跟 $i$ 不同的子树中，与 $i$ 相连显然是不劣的。对于跟 $i$ 在相同的子树中的节点，之后递归以后会出现更优的边，由于最后要求的是最小生成树，所以跟 $i$ 相连并不会对结果产生影响。

复杂度 $O(n\log^2n)$ ，其中边的数量是 $O(n\log n)$ 的。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,w[maxn];
int h[maxn],head=1;
struct yyy{
	int to,z,w;
	inline void add(int x,int y,int val) {
		to=y;z=h[x];h[x]=head;w=val;
	}
}a[maxn*2];
struct node{
	int x,y,z;
}e[maxn*20];
inline bool cmp(node x,node y) {return x.z<y.z;}
int root,tot,siz[maxn],Max[maxn],vis[maxn];
inline void clear(int x,int pre) {
	siz[x]=1;Max[x]=0;int i,y;
	for (i=h[x];i;i=a[i].z) if (a[i].to!=pre&&!vis[y=a[i].to]) {
		clear(y,x);
		siz[x]+=siz[y];
		Max[x]=max(Max[x],siz[y]);
	}
}
inline void dfs1(int x,int pre,int SUM) {
	int i;
	for (i=h[x];i;i=a[i].z) if (a[i].to!=pre&&!vis[a[i].to]) {
		dfs1(a[i].to,x,SUM);
	}
	Max[x]=max(Max[x],SUM-siz[x]);
	if (!root||Max[root]>Max[x]) root=x;
}
inline void getroot(int x) {
	root=0;
	clear(x,0);
	dfs1(x,0,siz[x]);
}
int dis[maxn],fa[maxn];
int minn,ans;
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
inline void dfs(int x,int pre) {
	int i;
	if (!minn||dis[x]+w[x]<dis[minn]+w[minn]) minn=x;
	for (i=h[x];i;i=a[i].z) if (a[i].to!=pre&&!vis[a[i].to]) {
		dis[a[i].to]=dis[x]+a[i].w;
		dfs(a[i].to,x);
	}
}
inline void dfs3(int x,int pre) {
	int i;
	if (x^minn) e[++tot]=(node){minn,x,dis[x]+dis[minn]+w[x]+w[minn]};
	for (i=h[x];i;i=a[i].z) if (a[i].to!=pre&&!vis[a[i].to]) {
		dfs3(a[i].to,x);
	}
}
inline void solve(int x) {
	int i;
	vis[x]=1;dis[x]=0;minn=0;
	dfs(x,0);
	dfs3(x,0);
	for (i=h[x];i;i=a[i].z) if (!vis[a[i].to]) {
		getroot(a[i].to);
		solve(root);
	}
} 
signed main(void){
	int i,x,y,z;
	read(n);
	for (i=1;i<=n;i++) read(w[i]);
	for (i=1;i<n;i++) {
		read(x);read(y);read(z);
		a[++head].add(x,y,z);
		a[++head].add(y,x,z);
	}
	getroot(1);
	solve(root);
	sort(e+1,e+1+tot,cmp);
	for (i=1;i<=n;i++) fa[i]=i;
	for (i=1;i<=tot;i++) {
		if (getfa(e[i].x)!=getfa(e[i].y)) {
			fa[getfa(e[i].x)]=getfa(e[i].y);
			ans+=e[i].z;
		}
	}
	printf("%lld",ans);
	return 0;
}

3. CF888G Xor-MST

Description

给定 $n$ 个结点的无向完全图。每个点有一个点权为 $a_i$。连接 $i$ 号结点和 $j$ 号结点的边的边权为 $a_i\oplus a_j$。求这个图的 MST 的权值。

$1\le n\le 2\times 10^5$，$0\le a_i< 2^{30}$。

2s , 250MB

Solution

建立 01Trie。

回忆一下 Kruskal 的过程，是按照边权从小到大合并的。我们可以考虑模拟这个从小到大的过程。

在一个点处将左右儿子合并成一个联通块一定是正确的。因为到更上面合并权值还要更大。

现在我们要查询两个点集之间的最小 xor。由于 01Trie 只有 $O(\log v)$ 层，暴力将一侧的点拿出来到另一边查询最小的 xor 值复杂度就是 $O(n\log ^2v)$ 的，不需要启发式合并。

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
#include<bits/stdc++.h>
#define rg register
#define int long long 
#define maxn 200005
#define put() putchar('\n')
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
int cnt,root,n,a[maxn],g[maxn],tot,ans;
struct yyy{
    int ls,rs,size,val;
}f[maxn*30];
const int base=31;
inline void insert(int &rt,int x,int deep){
	if (!rt) rt=++cnt;f[rt].size++;
	if (deep<0) {f[rt].val=x;return;}
	if ((x>>deep)&1) insert(f[rt].rs,x,deep-1);
	else insert(f[rt].ls,x,deep-1);
}
inline void dfs2(int rt,int deep){
	if (deep<0) {g[++tot]=f[rt].val;return;}
	if (f[rt].ls) dfs2(f[rt].ls,deep-1);
	if (f[rt].rs) dfs2(f[rt].rs,deep-1);
}
inline int query(int rt,int x,int deep){
	if (deep<0) return 0;
	if (x&(1ll<<deep)) {
		if (f[rt].rs) return query(f[rt].rs,x,deep-1);
		else return query(f[rt].ls,x,deep-1)+(1ll<<deep);  
	}
	else{
		if (f[rt].ls) return query(f[rt].ls,x,deep-1);
		else return query(f[rt].rs,x,deep-1)+(1ll<<deep);
	}
}
inline void dfs(int rt,int deep){
	if (f[rt].size<=1||deep<0) return;
	if (f[rt].ls) dfs(f[rt].ls,deep-1);
	if (f[rt].rs) dfs(f[rt].rs,deep-1);
	if (f[rt].ls&&f[rt].rs) {
		rg int i,tmp,Min=1e18;tot=0;
		dfs2(f[rt].ls,deep-1);
		for (i=1;i<=tot;i++) tmp=query(f[rt].rs,g[i],deep-1),Min=min(tmp,Min);
		ans+=Min+(1ll<<deep);
	}
}
signed main(){
    rg int i;
    read(n);cnt=root=1;
    for (i=1;i<=n;i++) read(a[i]),insert(root,a[i],base);
    dfs(root,base);
    printf("%lld",ans);
    return 0;
}

4. CF1687B Railway System

Description

交互题，交互库有一张图，每次询问若干条边，交互库返回这些边的最大生成树的权值。

不超过 $2m $ 次询问报告最小生成树。

$n\le 200,m\le 500$

1s , 250MB

Solution

先用 $m$ 次问出每条边的权值。

把这 $m$ 条边从小到大排序，如果这条边 $i$ 有贡献，则这条边连接的两个点在排序后 $[1,i)$ 组成的图中并不连通。

询问 $[1,i]$ 组成的最大生成树的权值，通过权值增加来判断这条边原来的两个点是不是联通。

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
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define maxn 1005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
int n,m,ans;
string s,t;
struct yyy{
	int id,w;
}a[maxn];
inline bool cmp(yyy x,yyy y) {return x.w<y.w;}
signed main(void){
//	freopen("1.in","r",stdin);
	int i,x,y;
	read(n);read(m);
	for (i=1;i<=m;i++) s+="0";
	for (i=0;i<m;i++) {
		t=s;t[i]='1';
		cout<<"? "<<t<<endl;
		fflush(stdout);
		read(a[i].w);a[i].id=i;
	}
	sort(a,a+m,cmp);
	t=s;
	int las=0,now;
	for (i=0;i<m;i++) {
		t[a[i].id]='1';
		cout<<"? "<<t<<endl;
		fflush(stdout);
		read(now);
		if (now-las==a[i].w) ans+=a[i].w;
		las=now;
	}
	cout<<"! "<<ans;
	return 0;
}

5. CF1120D Power Tree

Description

给定一棵 $n$ 个点的有根树，$1$ 为根。定义 $u$ 为叶子当且仅当它不是根且度数为 $1$。

你可以选择花费 $w_u$ 的代价控制 $u$ 点。当一个点被控制时你可以选择给它的子树内的叶子的点权都加上一个值 $v$ 。你需要控制若干个点，使得花费的代价尽量少，无论怎样规定叶子的初始点权，都可以通过操作你选择的点来让所有叶子的点权清空。

你需要输出代价和的最小值以及所有点，满足它存在于某一种最优选择中。

$n\le 2\times 10^5$

2s , 512MB

Solution

求出叶子节点的 dfs 序。子树加变成在差分数组上的两个点加减，满足之和不变。连接这两个点。

如果满足无论神秘初始点权都可以让叶子节点清空，则需要满足叶子节点在新的图上都联通。

求最小生成树即可。

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
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 200005
#define put() putchar('\n')
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
using namespace std;
inline void read(int &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,Ty t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,Ty x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	Tp ostream& operator<<(ostream& os,vector<Ty>& V){os<<"[";for(auto& vv:V) os<<vv<<",";os<<"]";return os;}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
inline int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,w[maxn];
struct yyy{
	int x,y,z,id;
}e[maxn];
inline bool cmp(yyy x,yyy y) {return x.z<y.z;}
int fa[maxn];
inline int getfa(int x) {return x==fa[x]?x:fa[x]=getfa(fa[x]);}
int l[maxn],r[maxn],times,ans,Ans[maxn],tot;
vector<int>to[maxn];
inline void dfs(int x,int pre) {
	int i;
	if (x!=1&&to[x].size()==1) l[x]=++times;
	else l[x]=times+1;
	for (auto y:to[x]) if (y^pre) {
		dfs(y,x);
	}
	r[x]=times;
}
signed main(void){
	freopen("1.in","r",stdin);
	int i,x,y,j,k;
	read(n);
	for (i=1;i<=n;i++) read(w[i]);
	for (i=1;i<=n+1;i++) fa[i]=i;
	for (i=1;i<n;i++) read(x),read(y),to[x].push_back(y),to[y].push_back(x);
	dfs(1,0);
	for (i=1;i<=n;i++) e[i].x=l[i],e[i].y=r[i]+1,e[i].z=w[i],e[i].id=i;//,gdb(e[i].x,e[i].y,e[i].z,e[i].id);
	sort(e+1,e+1+n,cmp);
	for (i=1;i<=n;i++) {
		for (k=i;e[k+1].z==e[i].z&&k<n;k++);
		for (j=i;j<=k;j++) if (getfa(e[j].x)!=getfa(e[j].y)) Ans[++tot]=e[j].id;//,gdb(tot,e[j].id,i,k);
		for (j=i;j<=k;j++) {
			if (getfa(e[j].x)!=getfa(e[j].y)) {
				fa[getfa(e[j].x)]=getfa(e[j].y);
				ans+=e[j].z;
			}
		}
		i=k;
	}
	printf("%lld %lld\n",ans,tot);
	sort(Ans+1,Ans+1+tot);
	for (i=1;i<=tot;i++) printf("%lld ",Ans[i]);
	return 0;
}

Kruskal 重构树

这玩意我之前就会，就不细讲了。

  1. NOI2018 归程

  2. CF1628E Groceries in Meteor Town

  3. CF1416D Graph and Queries

​ 以时间为顺序的重构树。