JZTXT

Kruskal 重构树学习笔记

发布时间 2023-10-08 21:49:05作者: Svemit

模拟赛突然出了这个，，，被创死了

定义

我们先回顾最基本的 Kruskal 算法。

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

那什么事 Kruskal 重构树呢？

就是用类似Kruskal的方法来把一个图重构成一颗树。

实现方法

按照最小生成树的方法先把边权从小到大排序，然后一次考虑每条边。

如果这条边连接的两个端点已经连通就跳过，还没连通就建一个新点，把这个新点的权值设为这条边的权值，让这个新点向两个端点的根节点连边。

具体实现方法如下：

tot = n;
dsu.init();
for(int i = 1; i <= m; i ++)
	cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
sort(edge + 1, edge + 1 + m);
for(int i = 1; i <= m; i ++) {
	int u = dsu.find(edge[i][1]), v = dsu.find(edge[i][2]);
	if(u == v) continue;
	tot ++;
	dsu.fa[u] = dsu.fa[v] = tot;
	e[tot].push_back(u);
	e[tot].push_back(v);
	val[tot] = edge[i][0];
}

优秀性质：

  • 是一棵二叉树。

  • 如果是按最小生成树建立的话是一个大根堆。

  • 原图中两个点间所有路径上的边最大权值的最小值 \(=\) 最小生成树上两点简单路径的边最大权值 \(= \text{Kruskal}\) 重构树上两点 \(\text{LCA}\) 的点权。

例题

1. P2245 星际导航

显然是板子题，直接利用性质 3，会写 LCA 就行。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e5 + 5, M = 3e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, q;
array<int, 3> edge[M];
int p[N];
int fa[N][20], val[N], dep[N];
vector<int> e[N];
int tot;
int find(int x) {
	return p[x] == x ? x : p[x] = find(p[x]);
}
void dfs(int u, int fath) {
	dep[u] = dep[fath] + 1;
	fa[u][0] =  fath;
	for(int i = 1; i <= __lg(dep[u]); i ++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(auto v : e[u]) dfs(v, u); 
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) swap(u, v);
	while(dep[u] != dep[v]) u = fa[u][__lg(dep[u] - dep[v])];
	if(u == v) return u;
	for(int k = __lg(dep[u]); ~k; k --)
		if(fa[u][k] != fa[v][k]) 
			u = fa[u][k], v = fa[v][k];
	return fa[u][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
	cin >> n >> m;
	for(int i = 1; i <= n * 2; i ++) p[i] = i;
	for(int i = 1; i <= m; i ++)
		cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
	tot = n;
	sort(edge + 1, edge + 1 + m);
	for(int i = 1; i <= m; i ++) {
		int u = find(edge[i][1]), v = find(edge[i][2]);
		if(u == v) continue;
		tot ++;
		p[u] = p[v] = tot;
		e[tot].push_back(u);
		e[tot].push_back(v);
		val[tot] = edge[i][0];
	}
	for(int i = 1; i <= tot; i ++)
		if(find(i) == i) dfs(i, 0);
	cin >> q;
	while(q --) {
		int u, v;
		cin >> u >> v;
		if(find(u) != find(v)) cout << "impossible\n";
		else cout << val[lca(u, v)] << '\n';
	}
    return 0;
}

2.囹圄

同学出的题，就不放链接了。

题意：

在一个神奇的国家有 \(n\) 个地点，以及 \(m\) 条道路连接这些地点，每个地点有一个局限值 \(a_i\)。

同时，定义一个地点的广阔度为其能到达的地方的局限值中没有出现过的最小正整数。

最近这个国家打算修路，有 \(q\) 次操作，分为修路和询问

1 x y 表示修一条连接 \(x\) 和 \(y\) 的路。

2 x 表示查询 \(x\) 的广阔度。

对于 \(100%\) 的数据 \(1\le n,m\le 3\times 10^5\) ，\(1\le q\le 1\times 10^6\) ，\(1\le a_i \le n\)。

分析：

有一个显然的 \(O(n \log ^ 2 n)\) 的并查集启发式合并，暴力维护 mex 的做法，可以通过，但是不是最优解这里只提一嘴。

最优解显然可以线段树合并，但是我没学。

考虑按询问顺序建重构树，对于每次询问，倍增寻找能到的节点，把叶子节点建立权值线段树。

然后就可以 P4137了。

3. 黄队

模拟赛题，链接放了也没人进得去（

有一棵 \(n\) 个节点的树，其中所有的树边 \(1\) 到 \(n−1\) 标号。定义 \(δ(v,r)\) 为 \(v\) 经过由标号不超过 \(r\) 的边构成的路径到达的点集。

现在有 \(q\) 个询问，每个询问给你一组点 \(v_1,v_2,…,v_k\)，求 \((r_1,r_2,…,r_k)\) 这样的 k 元组个数，满足 $ 0 \le r_i \le n - 1 $ 且\(δ(v_i,r_i)\) 这些点集两两不交。

由于答案很大，请输出对 \(10^9+7\) 取模的值。

对于 \(100%\) 的数据，满足 \(n, q,\sum k \le 10^5\) 。

分析：

杜老师几年前出的题，性质还是很好找的，找到性质就 80 pts 了（

考虑 \(u, v\) 两点，如果他们之间的路径上最大边权是 \(w\)，那么有 \(r_u,r_v < w\)，否则 \(u\) 或者 \(v\) 的球就会包含另
1 个点。

所以 \(r_u\) 要小于到其他所有点的路径最大边权的最小值。

到这里之后暴力就有 80 了，就是我场上拿的分。（

考虑建出重构树，每次询问按 \(dfn_u\) 排序，每个点的最小值一定是跟他相邻的点的 LCA 取到，所以排完序后每个点就只要算两边的了。

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 4e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, q, tot;
int p[N], val[N], fa[N][20], dep[N], dfn[N], tim;
int find(int x) {
	return p[x] == x ? x : p[x] = find(p[x]);
}
vector<int> e[N];
void dfs(int u, int fath) {
	fa[u][0] = fath;
	dfn[u] = ++ tim;
	dep[u] = dep[fath] + 1;
	for(int i = 1; i <= __lg(dep[u]); i ++) 
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(auto v : e[u]) dfs(v, u);
}
int lca(int u, int v) {
	if(dep[u] < dep[v]) swap(u, v);
	while(dep[u] != dep[v]) u = fa[u][__lg(dep[u] - dep[v])];
	if(u == v) return u;
	for(int k = __lg(dep[u]); ~k; k --) 
		if(fa[u][k] != fa[v][k]) 
			u = fa[u][k], v = fa[v][k];
	return fa[u][0];
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	tot = n;
	for(int i = 1; i <= n * 2; i ++) p[i] = i;
	for(int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		u = find(u), v = find(v);
		tot ++;
		p[u] = p[v] = tot;
		e[tot].push_back(u);
		e[tot].push_back(v);
		val[tot] = i;
	}
	cin >> q;
	dfs(tot, 0);
	while(q --) {
		int k;
		int ans = 1;
		cin >> k;
		vector<int> a(k);
		for(int i = 0; i < k; i ++)
			cin >> a[i];
		sort(a.begin(), a.end(), [](int x, int y) {
			return dfn[x] < dfn[y];
		});
		for(int i = 0; i < k; i ++) {
			int tmp = n - 1;
			if(i) tmp = val[lca(a[i], a[i - 1])] - 1;
			if(i < k - 1) tmp = min(tmp, val[lca(a[i], a[i + 1])] - 1);
			ans = (LL)(tmp + 1ll) * ans % mod;
		}
		cout << ans << '\n';
	}
    return 0;
}

4.P7834 [ONTAK2010] Peaks 加强版

求从 \(u\) 开始只经过权值 \(\leq x\) 的边所能到达的点，这个可以重构树上倍增求解，求出左右端点，就变成区间第 \(k\) 大了，直接主席树即可。

#include <bits/stdc++.h>
#define int long long 
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 2e5 + 5, M = 5e5 + 5, INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
int n, m, q;
int h[N];
vector<int> hs;
array<int, 3> edge[M];
vector<int> e[N];
int val[N], fa[N][25], p[N], L[N], R[N], dep[N];
struct DSU {
	int fa[N];
	void init() {
		for(int i = 1; i <= n * 2; i ++) fa[i] = i;
	}
	int find(int x) {
		return fa[x] == x ? x : fa[x] = find(fa[x]);	
	}
} dsu;
int tot, idx;
void dfs(int u, int fath) {
	L[u] = idx;
	if(u <= n) p[++ idx] = u;
	dep[u] = dep[fath] + 1;
	fa[u][0] = fath;
	for(int i = 1; i <= __lg(dep[u]); i ++)
		fa[u][i] = fa[fa[u][i - 1]][i - 1];
	for(auto v : e[u]) dfs(v, u);
	R[u] = idx;
}
struct SegT {
	int l, r, val;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define val(x) tr[x].val
} tr[N << 5];
int rt[N], cnt;
void pushup(int x) {
	val(x) = val(l(x)) + val(r(x));
}
void build(int &x, int l, int r) {
	x = ++ cnt;
	if(l == r) return;
	int mid = l + r >> 1;
	build(l(x), l, mid), build(r(x), mid + 1, r);
}
void insert(int &x, int lst, int pos, int l, int r) {
	x = ++ cnt;
	tr[x] = tr[lst];
	if(l == r) {
		val(x) ++;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) insert(l(x), l(lst), pos, l, mid);
	else insert(r(x), r(lst), pos, mid + 1, r);
	pushup(x);
}
int query(int x, int y, int l, int r, int k) {
	if(l == r) return l;
	int cnt = val(r(y)) - val(r(x)), mid = l + r >> 1;
	if(k <= cnt) return query(r(x), r(y), mid + 1, r, k);
	else return query(l(x), l(y), l, mid, k - cnt);
}
int get(int u, int x) {
	for(int i = 19; ~i; i --)
		if(val[fa[u][i]] <= x) u = fa[u][i];
	return u;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
	cin >> n >> m >> q;
	for(int i = 1; i <= n; i ++) {
		cin >> h[i];
		hs.push_back(h[i]);
	}
	sort(hs.begin(), hs.end());
	hs.erase(unique(hs.begin(), hs.end()), hs.end());
	for(int i = 1; i <= n; i ++) {
		h[i] = lower_bound(hs.begin(), hs.end(), h[i]) - hs.begin() + 1;
	}
	tot = n;
	dsu.init();
	for(int i = 1; i <= m; i ++)
		cin >> edge[i][1] >> edge[i][2] >> edge[i][0];
	sort(edge + 1, edge + 1 + m);
	for(int i = 1; i <= m; i ++) {
		int u = dsu.find(edge[i][1]), v = dsu.find(edge[i][2]);
		if(u == v) continue;
		tot ++;
		dsu.fa[u] = dsu.fa[v] = tot;
		e[tot].push_back(u);
		e[tot].push_back(v);
		val[tot] = edge[i][0];
	}
	val[0] = LLONG_MAX;
	for(int i = tot; i >= 1; i --)
		if(dsu.fa[i] == i) dfs(i, 0);
	build(rt[0], 1, hs.size());
	for(int i = 1; i <= n; i ++) {
		insert(rt[i], rt[i - 1], h[p[i]], 1, hs.size());
	}
	int lst = 0;
	while(q --) {
		int v, x, k;
		cin >> v >> x >> k;
		v = (v ^ lst) % n + 1;
		k = (k ^ lst) % n + 1;
		x ^= lst;
		v = get(v, x);
		if(R[v] - L[v] < k) cout << -1 << '\n', lst = 0;
		else {
			lst = hs[query(rt[L[v]], rt[R[v]], 1, hs.size(), k) - 1];
			cout << lst << '\n';
		}
	}
    return 0;
}