床长人工智能教程50免费pdf文档——Kruskal重构

.

声明：本人只是分享一些床长人工智能教程相关的免费pdf文档而已，并非床长人工智能网校的收费文章。尊重版权，支持原创！

重构树重构树

前几天做的同步赛时，我就拿了离线树剖的分暴力。

后来就知道有重构树这样一种新科技年以前就有了

什么是重构树什么是重构树

简单来讲，就是在算法进行的过程中，我们把最小生成树的边权改为点权。

这样，原树的节点个数变成个，并且有着许多有趣的性质。

重构树的性质重构树的性质

根据我们构造的过程，这是一个二叉堆后面再讲构造

原树两点之间的边权最大值是重构树上两点的权值

重构树中代表原树中的点的节点全是叶子节点，其余节点都代表了一条边的边权。

有了这些个性质，我们就可以解决一些问题了。

重构树的构造重构树的构造

相信大家都会

由于重构树中把原树的点权转换成为了新建节点的边权，这一过程是这样实现的。

首先对边排序

然后使用并查集辅助加边，每新建一条边时

新建节点编号从开始

将原有两节点所在集合改为

将原有节点与连边

新建节点的权值为当前边的边权

给一下简单的代码

代码复杂度很低，时间复杂度是优秀的

重构树的简单应用重构树的简单应用

重构树能够更快有效解决一些静态的树剖问题，而且复杂度还很优秀。

例如

【】网络

给你个点的无向,，记为。

中有条边,，第条边的长度为

现在有个询问,。

每个询问的格式是，表示询问从点走到点的所有路径中，最长的边最小值是多少？

第一行。

第行三个正整数表示与之间有一条长度为的边。

第行每行两个整数,表示询问从点走到点的所有路径中，最长的边最小值是多少？

对每个询问，输出最长的边最小值是多少。

我们好像都会求树上的倍增最小值。

但是我们发现重构树的做法更加优美，直接求出的点权即可。

||

类似的还有的货车运输。

当然，重构树还能够解决一般树剖不能够解决的问题。

比如这道

路径权值

给定一个带权树，树上任意两点间的路径权值,定义为,这两个点之间路径上的最小值，树上任意一点的权值定义为这个点到树上其他所有点的路径权值和，即,，现求树上一点，使得这个点的权值最大，输出这个值。

首先输入一个整数,接着每组数据首先输入一个整数≤≤，表示该组数据中树的点的个数。

接下来行，每行三个整数≤,≤,≤≤，表示编号为的节点和编号为的节点之间存在一条权值为的边，树上每个点的编号为

对于每组数据，首先输出数据编号，然后输出树上的点的最大权值，具体格式见输出样例。

这道题目怎么做呢？

显然，如果我们暴力枚举点对是不可行的。

既然是和树上路径有关的问题，点分治可不可行呢？

本蒟蒻太菜了，根本想不到啊

那我们试算一下边的贡献，即一条边对所有经过这一条边的点对都会有这条边长度的贡献。

怎么算呢？

我们之前提到过重构树中，两个节点的节点就是两点路径上的最大最小节点。

也就是说，对于一个非叶节点，它左子树中的节点到右子树中的节点的路径一定会经过节点所对应的边，反之亦然。

那么我们就可以建出重构树之后维护当前边对于重构树子树中节点的贡献了。

这个区间加法的过程我们可以用树状数组实现。

||。。。