kruskal重构树和Prufer序列

kruskal 重构树

 首先前置知识就是 \(kruskal\) 求最小生成树，就不再多说了。

  \(kruskal\) 重构树其实就是把最小生成树这个建成一个二叉树，然后这个图中所有的叶子节点都是原图中的节点。

 其余的点每一个点都有一个权值 \(w[i]\) ，代表从左边的集合到右边的集合的路径，优于重构树是在 \(kruskal\) 的基础上完成的，所以我们必然可以得到一个自下而上点权不降的二叉树。例如这个图：

 和 \(kruskal\) 最小生成树一样，我们先按照边的边权排一个序，然后开始慢慢找，只是建树的时候不一样。

 首先我们看到 \(6 -> 7\) 这条边，我们将 \(6,7\) 放到一个并查集中去，然后建图的时候将他们两个同时连到一个新的虚点上面去，然后这个虚点的权值就是 \(1\)

 然后后面建边的时候就和这个一样建就可以了，然后两个集合连边的话连两个虚点就可以了。

 \(kruskal\) 重构树有很多独特的性质，最常用的一个应该就是求路径上最小的权值最大为多少或者路径上最大的权值最小为多少，可能还有别的用法，但是我不太清楚。

 然后求这种的时候，就先用 \(kruskal\) 跑一个最大或者最小生成树，然后求的两个点的最近公共祖先的权值就是要求的值。

 我还没有用 \(kruskal\) 重构树写过题，我都是直接硬算的（）。如果以后写了再贴吧。

Prufer序列

定义：对于一棵 \(n(n \ge 2)\) 个节点的标定树（节点带编号），其 \(Prufer\) 序列是一个长度为 \(n - 2\) ，值域为 \([1,n]\) 的整数序列。

 每棵树必存在 \(Prufer\) 序列且唯一，每个 \(Prufer\) 序列对应的树也必定存在且唯一，即两者为双射关系。

将树转化为Prufer序列

1. 从树上选择编号最小的叶子节点，序列的下一位为其父节点的编号。

2. 删去该叶子节点。

3. 重复 ① 和 ② 操作，直到树只剩下两个节点，此时序列的长度刚好为 \(n - 2\) 。

一个显而易见的做法是：

 维护一个小根堆，将叶子节点依次丢入，每次从堆顶取出一个叶子节点，将其父节点的编号加入序列，然后删去该叶子节点并减小父节点的度数，如果他的父节点的度数为 \(1\) ，那么就把父节点加入小根堆，重复这个操作，执行 \(n - 2\) 次就可以求出序列了。

复杂度是：\(O(n \log n)\)

还有一种线性的做法

1. 先找到编号最小的叶子节点，设其为 \(p\)

2. 将 \(p\) 的父节 \(f\) 点加入序列

3. 若删去 \(p\) 节点后，\(f\) 节点变成叶子节点，且 \(f < p\) ，那么就可以立即将 &f& 作为新选择的叶子节点进行操作。

4. 一直执行 ③ 直到不满足条件，此时将 \(p ++\) ，直到找到下一个还没有删除的叶子节点。

总的时间复杂度为：\(O(n)\)

由Prufer序列重构树

 既然这两者是双射关系，则必然也可以由 \(Prufer\) 序列来重构一棵唯一的标定树。

 这个过程和树的序列化是十分类似的。

1. 选择编号最小的叶子节点，即未出现在序列中的节点，其父节点就是序列的第 \(i\) （ \(i\) 初始为 \(1\) ）个元素。

2. 由性质可得，其父节点的度数为其出现次数 \(+ 1\) 。将该叶子节点删去，其父节点度数 \(- 1\)。若度数变成 \(1\) ，那么父节点也变成叶子节点。

3. \(i ++\) ，然后重复这操作 ① 和 ② ，直到序列的每一个元素都是用完毕。

同样，还有一种线性的方法

1. 先找到编号最小的未出现在序列中的节点，其为叶子节点，设其为 \(p\)

2. 将 \(p\) 的父节点 \(f\) 设为序列中尚未使用的第一个元素。

3. 若删去节点 \(p\) 之后， \(f\) 节点变为叶子节点且 \(f < p\)，那么此时可以立即将 \(f\) 作为新选择的叶子结点进行操作。

4. 一直执行 ③ 直到不满足条件，此时将 \(p ++\) ，直到找到下一个还没有删除的叶子节点。

最后剩下两个节点，一个必然是节点 \(n\)，将这两个节点连接即可。

应用

一般是利用于图论的组合奇数问题

1.无向完全图的不同生成树数：

 若该图有 \(n\) 个节点，则仍以一个长度为 \(n - 2\) 的 \(Prufer\) 序列都可以构造出一棵生成树，且各不相同，所以总数为 \(n ^ {n - 2}\) 。

2.\(n\) 个点，每个点度数为别为 \(d_i\) 的无根树计数：

 总排列为 \((n - 2) !\) ，即 \(A _{n - 2} ^ {n - 2}\)

 其中数字 \(i\) 出现了 \(d_i - 1\) 次，故其重复的有 \((d_i - 1) !\) 种排列，即 \(A _ {d_i - 1}^{d_i - 1}\)。

 应当 去除重复的，故总个数为 \(\frac{(n - 2)!}{\Pi _{i = 1} ^{n} (d_i - 1)!}\)

例题 P6086

int n;
int w[N],fa[N];
int d[N];

int main(){
	int type;
	n = fr(),type = fr();
	if (type == 1) {
		for (int i = 1; i < n; i ++) {
			fa[i] = fr();
			d[fa[i]] ++;
		}
		for (int i = 1,j = 1;i <= n - 2; i ++,j ++) {
			while (d[j]) j ++;
			w[i] = fa[j];
			while (i <= n - 2 && !(-- d[w[i]]) && w[i] < j) {
				w[i + 1] = fa[w[i]];
				i ++;
			}
		}
		lwl ans = 0;
		for (int i = 1; i <= n - 2; i ++) {
			ans ^= (lwl)i * w[i];
		}
		fw(ans);
	} else {
		for (int i = 1; i <= n - 2; i ++) {
			w[i] = fr();
			d[w[i]] ++;
		}
		w[n - 1] = n;
		for (int i = 1, j = 1; i < n; i++, j++) {
			while (d[j]) j ++;
			fa[j] = w[i];
			while (i < n && !(-- d[w[i]]) && w[i] < j) {
				fa[w[i]] = w[i + 1];
				i ++;
			}
		}
		lwl ans = 0;
		for (int i = 1; i < n; i ++) {
			ans ^= (lwl)i * fa[i];
		}
		fw(ans);
	}
	return 0;
}

练习

 还是图论爽啊！什么模拟什么二分什么双指针，我的评价是不如图论。前面三题都是原题，其中还有一个是今天中午刚刚做的，而且我的 \(cpp\) 文件都没有关掉。

A.电话连线（dial）

 就是比较裸的最小生成树，就是建边的时候不是直接输入的罢了。

struct node{
	int a,b,w;
	bool operator  < (const node &t) const{
		return w < t.w;
	}
}e[N];

int n,m;
int h[N];

int find(int x) {
	if (h[x] != x) h[x] = find(h[x]);
	return h[x];
}

int main(){
	n = fr();
	for (int i = 1; i <= n; i ++) {
		h[i] = i;
	}
	int idx = 0;
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			int a = fr();
			if (!a) {
				h[find(i)] = find(j);
			} else {
				if (i > j) continue;
				e[++ idx] = {i,j,a};
			}
		}
	}
	int ans = 0,cnt = 0;
	sort(e + 1,e + 1 + idx);
	for (int i = 1; i <= idx; i ++) {
		int ha = find(e[i].a),hb = find(e[i].b);
		if (ha != hb) {
			cnt ++;
			ans += e[i].w;
			h[ha] = hb;
		}
	}
	fw(cnt),ch;
	fw(ans);
	return 0;
}

B.过路费

 就是上面说的 \(kruskal\) 重构树，一开始用的之前写货车运输那个写法，但总是 \(80\) 分，就直接写重构树了，还挺好用的。

struct EDGE{
	int a,b,w;
	bool operator < (const EDGE &t) const{
		return w < t.w;
	}
}edge[M];

int n,m,Q;
int h[N];
vector<int> e[N];
int de[N];
int fa[N][30];
int w[N];

int find(int x){
	if (h[x] != x)
		h[x] = find(h[x]);
	return h[x];
}

void init(int u,int p){
	de[u] = de[p] + 1;
	fa[u][0] = p;
	for (int k = 1; k <= log2(de[u]); k ++){
		fa[u][k] = fa[fa[u][k - 1]][k - 1];
	}
	for (auto &v : e[u]){
		if (v == p) continue;
		init(v,u);
	}
}

int LCA(int x,int y){
	if (de[x] < de[y])
		swap(x,y);
	
	int dh = de[x] - de[y];
	int kmax = log2(dh);
	for (int k = kmax; k >= 0; k --){
		if (dh & (1 << k)){
			x = fa[x][k];
		}
	}
	
	if (x == y) return w[x];
	
	kmax = log2(de[x]);
	for (int k = kmax; k >= 0; k --){
		if (fa[y][k] != fa[x][k]){
			x = fa[x][k];
			y = fa[y][k];
		}
	}
	
	return w[fa[x][0]];
}

signed main(){
	n = fr(), m = fr();
	int a,b,ww;
	for (int i = 1; i <= n; i ++)
		h[i] = i;
	for (int i = 1; i <= m; i ++){
		a = fr(),b = fr(),ww = fr();
		edge[i] = {a,b,ww};
	}
	
	sort(edge + 1,edge + 1 + m);
	int cnt = n;
	for (int i = 1; i <= m; i ++){
		int ha = find(edge[i].a);
		int hb = find(edge[i].b);
		if (ha != hb){
			cnt ++;
			h[ha] = cnt;
			h[hb] = cnt;
			h[cnt] = cnt;
			e[ha].push_back(cnt);
			e[cnt].push_back(ha);
			e[hb].push_back(cnt);
			e[cnt].push_back(hb);
			w[cnt] = edge[i].w;
		}
	}
	
	init(cnt,0);
	
	Q = fr();
	while (Q --){
		a = fr(),b = fr();
		int ans = LCA(a,b);
		fw(ans);
		ch;
	}
	return 0;
}

C.新的开始

 也是一个裸的 \(kruskal\) 重构树，然后用了一个虚拟点来处理前面的。

struct node{
	int a,b,w;
	bool operator < (const node &t) const{
		return w < t.w;
		
	}
}e[N * N];

int n,m;
int w[N];
int h[N];

int find(int x) {
	if (h[x] != x) h[x] = find(h[x]);
	return h[x];
}

int main(){
	n = fr();
	int idx = 0;
	for (int i = 1; i <= n; i ++) {
		w[i] = fr();
		e[++ idx] = {0,i,w[i]};
		h[i] = i;
	}
	for (int i = 1; i <= n; i ++) {
		for (int j = 1; j <= n; j ++) {
			int a = fr();
			if (i <= j) continue;
			e[++ idx] = {i,j,a};
		}
	}
	lwl ans = 0;
	sort(e + 1,e + 1 + idx);
	for (int i = 1; i <= idx; i ++) {
		int ha = find(e[i].a),hb = find(e[i].b);
		if (ha != hb) {
			h[ha] = hb;
			ans += e[i].w;
		}
	}
	fw(ans);
	return 0;
}

D.归程

 这个题是 \(kruskal\) 重构树、\(dijkstra\) 最短路还有 \(LCA\) 杂糅。

 首先先对图跑一遍 \(dijkstra\) 最短路，然后再根据每条边的海拔建 \(kruskal\) 重构树，

 然后对于每次询问来说，车能够通过的路径就是 \(a > p\) 的任意边，也就是说能通过车到达重构树的任意子树，然后再在这些子树中选出到达 \(1\) 点最短的点，然后他到 \(1\) 点的距离就是需要走的最短路径。

 然后我一开始写的时候写不出正解，就把前面的 \(45\) 分暴力给写了，本来理论上来说应该还有十分的暴力分的，但我确实是懒得打了，理论上来说那个代码应该是可以过那 \(10\) 分的树的，但是都 \(TLE\) 了，无所谓，不管了。

数组也开的不多吧，也就开了八行是不是。

struct node{
	int a,b,w,p;
	bool operator < (const node &t) const{
		return p > t.p;
	}
}e[M];

struct EDGE{
	int v,w;
};

int idx;
int n,m,p,v;
int dis[N];
int fa[N][20];
int de[N],minn[N];
int w[N],h[N];
bool flag[N];
vector<int> tr[N];
vector<EDGE> edge[N];

void dij() {
	memset(dis,0x3f,sizeof dis);
	memset(flag,0,sizeof flag);
	priority_queue<pii,vector<pii>,greater<pii> > q;
	q.push({0,1});
	dis[1] = 0;
	while (q.size()) {
		auto t = q.top();
		q.pop();
		
		int u = t.se;
		if (flag[u]) continue;
		
		for (auto &it : edge[u]) {
			if (dis[it.v] > dis[u] + it.w) {
				dis[it.v] = dis[u] + it.w;
				q.push({dis[it.v],it.v});
			}
		}
		flag[u] = true;
	}
}

int find(int x) {
	if (h[x] != x) h[x] = find(h[x]);
	return h[x];
}

void dfs(int u,int father) {
	de[u] = de[father] + 1;
	fa[u][0] = father;
	minn[u] = dis[u];
	for (int k = 1; k <= log2(de[u]); k ++) {
		fa[u][k] = fa[fa[u][k - 1]][k - 1];
	}
	for (auto &v : tr[u]) {
		if (v == father) continue;
		dfs(v,u);
		minn[u] = min(minn[u],minn[v]);
	}
}

void kruskal() {
	memset(w,0,sizeof w);
	for (int i = 1; i <= n * 2; i ++) {
		tr[i].clear();
		h[i] = i;
	}
	sort(e + 1,e + 1 + m);
	
	idx = n;
	int cnt = 0;
	for (int i = 1; i <= m; i ++) {
		int ha = find(e[i].a),hb = find(e[i].b);
		if (ha != hb) {
			cnt ++;
			h[ha] = h[hb] = ++ idx;
			w[idx] = e[i].p;
			tr[idx].push_back(ha);
			tr[idx].push_back(hb);
		}
		if (cnt == n - 1) break;
	}
}

int qurrey(int u) {
	int ans = minn[v];
	int kmax = log2(de[u]);
	for (int k = kmax; k >= 0; k --) {
		if (w[fa[u][k]] > p) {
			ans = min(ans,minn[fa[u][k]]);
			u = fa[u][k];
		}
	}
	for (auto v : tr[u]) {
		ans = min(ans,minn[v]);
	}
	return ans;
}

int main(){
	int T = fr();
	while (T --) {
		n = fr(),m = fr();
		for (int i = 1; i <= n; i ++) {
			edge[i].clear();
		}
		for (int i = 1; i <= m; i ++) {
			int a = fr(),b = fr(),ww = fr(),d = fr();
			e[i] = {a,b,ww,d};
			edge[a].push_back({b,ww});
			edge[b].push_back({a,ww});
		}
		dij();
		kruskal();
		memset(fa,0,sizeof fa);
		dfs(idx,0);
		
		int ans = 0;
		int Q = fr(),K = fr(),S = fr();
		S ++;
		while (Q --) {
			v = fr(),p = fr();
			if (K) {
				v = (v + ans - 1) % n + 1;
				p = (p + ans) % S;
			}
			ans = qurrey(v);
			fw(ans);
			ch;
		}
	}
	return 0;
}

本栏目推荐文章
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• 【LeetCode 2701. 连续递增交易】MySQL用户变量编程得到严格递增连续子序列的开始位置，结束位置，长度等统计信息
• python经典有序序列的list列表推导式
• 【Leetcode 2474. 购买量严格增加的客户】MySQL用户变量编程解决严格递增连续子序列问题
• 解题报告P2501 [HAOI2006] 数字序列
• matlab使用长短期记忆（LSTM）神经网络对序列数据进行分类|附代码数据
• 【问题记录】【Fastjson】Fastjson 反序列化失败，syntax error, position at 0, name value
• System.ArgumentException: 使用 JSON JavaScriptSerializer 进行序列化或反序列化时出错。字符串的长度超过了为 maxJsonLength 属性设置的值。
• delphi JSON序列化（五）
• P4093 [HEOI2016/TJOI2016] 序列 题解

序列 kruskal Prufer序列kruskal prufer 序列prufer 序列 笔记prufer 序列 公式cayley prufer 小记 序列prufer 序列 笔记prufer 21 序列 数学prufer 序列codeforces amp prufer prufer kruskal