kruskal重构树

克鲁斯卡尔重构树

应用

  1. 区间点可相互到达时考虑
  2. 连通块题目考虑
  3. 用到的边是“连通块内的最小生成树”时考虑

性质

  1. 所有原节点都为叶子节点
  2. 有2*n-1个节点，叶子是点权，非叶子是边权
  3. 任何两个叶子节点可以相互到达，一定是通过了他们的LCA所代表的那条边到达的。
  4. 重构树一定是小根堆或者大根堆（针对于点的id，针对于点的“边权”）
  5. 选出一些点可以互相到达，且最大边权不可以超过x，则答案是非叶节点中点权大于等于x的所有子树中的点

注意（性质）

  1. 重构树中的 非叶子 点权不一定都不相同，但是根的点权一定最大
  2. 重构树一定是堆
  3. 在重构树上若到达某个非叶子节点 x，则x子树的所有叶子节点，都可以相互到达。
  4. 重构树中，若一个区间的点可以相互到达，求需要经过的边权的最小值？答案为max{LCA(L,L+1),LCA(L+1,L+2),…,LCA(R-2,R-1)}，此时可以用线段树维护区间最大值解决多组询问

对于4的证明：

设4中求出的答案为t，则L和L+1可以相互到达，L+1和L+2可以相互到达…，所以任意两个点都可以相互到达。

题目

E. Qpwoeirut and Vertices

题意

给我们一个无向无权图（n个点，m条边，边有编号），若干个询问（q组），每次询问给我们一个区间[ l , r ] ，问我们只经过前k条边使得该区间内任意两点可以互相到达的k的最小值。

思路

  1. 将边的id看成边权，建立重构树
  2. 预处理lca数组
  3. 对于区间[l,r]内，若这个区间的点可以相互到达，只需要求出LCA(l,l+1,…r-1)的点权即可

代码

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
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;

ll n,m,qq;
ll f[N],a[N];
int h[N],e[N],ne[N],idx;

int ans[N];
void add(int u,int v){
	e[++idx]=v;
	ne[idx]=h[u];//clear
	h[u]=idx;
}

//find
int find(int x){
	if(x==f[x])return x;
	return f[x]=find(f[x]);
}

//LCA
ll fa[N][21],deep[N];

void init()
{
	idx=0;
	int maxn=2*n;
	for(int i=1;i<=maxn;i++){
		deep[i]=a[i]=h[i]=0;
		f[i]=i;
		for(int j=0;j<=20;j++){
			fa[i][j]=0;
		}
	}
}

void dfs(int u){
	
	for(int i=h[u];i;i=ne[i]){
		int j=e[i];
		
		deep[j]=deep[u]+1;
		fa[j][0]=u;
		for(int k=1;k<=20;k++){
			int anc=fa[j][k-1];
			fa[j][k]=fa[anc][k-1];
		}
		
		dfs(j);
	}
}


//lca返回的是点的id
int lca(int u,int v){  
	if(deep[u]<deep[v])swap(u,v);
	for(int k=20;k>=0;k--){
		int anc=fa[u][k];
		if(deep[anc]>=deep[v]){
			u=anc;
		}
	}
	
	if(u==v)return u;
	
	for(int k=20;k>=0;k--){
		int anc1=fa[u][k];
		int anc2=fa[v][k];
		if(anc1!=anc2){
			u=anc1;
			v=anc2;
		}
	}
	
	return fa[u][0];
}


ll maxn[N];

void pushup(int u){
	maxn[u]=max(maxn[u<<1],maxn[u<<1|1]);
}
void build(int u,int l,int r){
	if(l==r){
		maxn[u]=ans[l];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}

int ask(int u,int l,int r,int L,int R){
	if(L<=l&&R>=r){
		return maxn[u];
	}
	int ans=0;
	int mid=l+r>>1;
	if(L<=mid){
		ans=max(ans,ask(u<<1,l,mid,L,R));
	}
	if(R>mid){
		ans=max(ans,ask(u<<1|1,mid+1,r,L,R));
	}
	return ans;
}
void solve()
{
	cin>>n>>m>>qq;
	init();
	for(int i=1;i<=m;i++){
		int u,v;
		cin>>u>>v;
		u=find(u),v=find(v);
        
        //注意这句
		if(u==v)continue;
		a[++n]=i;//val
		f[u]=n,f[v]=n;
		add(n,u),add(n,v);
	}
	
	deep[n]=1;
	dfs(n);
	
    
    //注意此时叶子节点的编号为[1,n/2+1]，但是最后一个点不参与答案
	for(int i=1;i<=n/2;i++){
		int zu=lca(i,i+1);
		ans[i]=a[zu];
	}

    //注意区间右端点
	build(1,1,n/2);
	
	for(int i=1;i<=qq;i++){
		int l,r;
		cin>>l>>r;
		if(l==r){
			cout<<0<<" ";
			continue;
		}
        
        //注意区间右端点
		cout<<ask(1,1,n/2,l,r-1)<<" ";
	}
	cout<<endl;
}

int main()
{
	int t;
	cin>>t;
	while(t--){
		solve();
	}
}

注意区间右端点

2021ICPC上海站Life is a Game

题意

​ 给我们一个无向有权图。
​ 点有点权，边有边权。。我们可以在图上来回走，走到一个点后会获得该点的价值，能够重复到达一个点但是不能重复获得该点的价值。但是，从一个点走到另一个点需要满足当前带有的价值要大于边权。
​ 若干次询问，每次询问给一个起点和一个价值，问最多可以获得多少价值。

思路

  1. 考虑到可以在一个连通块内随意走，而且走的边一定是这个连通块的“最小生成树边”，所以正好符合重构树
  2. 建立重构树之后，如果可以到达某个非叶子节点x，那么x的子树的叶子节点的权值都可以被收集到
  3. 考虑假设到达了某非叶子节点x，是否可以向上走，只需要此时的价值>父亲节点的点权即可

代码

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
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll n,m,q;
ll a[N];
//kruskal
struct A{
	int u,v;
	ll w;
	bool operator<(const A&b)const{
		return w<b.w;
	}
}edge[N];
ll f[N];
ll find(int x){
	if(x==f[x])return x;
	return f[x]=find(f[x]);
}

//graph
int h[N],e[N],ne[N],idx;
void add(int a,int b){
	e[++idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
}


//lca
ll fa[N][21],deep[N];
ll dd[N][21];//在i节点跳到i+2^j，至少还需要多少
ll sum[N];//子树中所有叶子的权值和

void dfs1(int u){
	if(u<=n/2+1){
		sum[u]=a[u];
	}
	else{
		for(int i=h[u];i;i=ne[i]){
			int j=e[i];
			dfs1(j);
			sum[u]+=sum[j];
		}
	}
}

void dfs2(int u){
	for(int i=h[u];i;i=ne[i]){
		int j=e[i];//son
		
		dd[j][0]=a[u]-sum[j];
		deep[j]=deep[u]+1;
		fa[j][0]=u;
		
		for(int k=1;k<=20;k++){
			ll anc=fa[j][k-1];
			fa[j][k]=fa[anc][k-1];
			dd[j][k]=max(dd[j][k-1],dd[anc][k-1]);
		}
		
		dfs2(j);
	}
}

void solve()
{
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	
	for(int i=0;i<=n*2+1;i++)f[i]=i;
	
	for(int i=1;i<=m;i++){
		int u,v,w;
		cin>>u>>v>>w;
		edge[i]={u,v,w};
	}
	sort(edge+1,edge+m+1);
	for(int i=1;i<=m;i++){
		int u=edge[i].u,v=edge[i].v;
		ll w=edge[i].w;
		u=find(u),v=find(v);
		if(u==v)continue;
		a[++n]=w;
		f[u]=f[v]=n;
		add(n,u),add(n,v);
	}
	
	dfs1(n);//cal sum
	
	deep[n]=1;
	dfs2(n);//cal fa&dd&deep
	
	while(q--){
		ll x,k;
		cin>>x>>k;
		//pos:x,val:k
		for(int jmp=20;jmp>=0;jmp--){
            if(fa[x][jmp]==0)continue;//不可以跳出去
			if(dd[x][jmp]<=k){
				x=fa[x][jmp];
			}
		}
        cout<<sum[x]+k<<endl;
	}
	
}
int main()
{
	int t=1;
	while(t--){
		solve();
	}
}

注意：dd数组表示至少需要k才可以跳，那么如果最开始在x位置额外拥有k，无论跳到哪里，都额外拥有k，k不会变化

算法 > 重构树
#算法
kruskal重构树
http://example.com/2023/11/27/算法/克鲁斯卡尔重构树/
作者
Mrxiad
发布于
2023年11月27日
许可协议