kruskal重构树
kruskal重构树的性质
kruskal是在kruskal进行的过程中，把最小生成树的边权变为点权的算法。这样，重构出的树的结点数为 n + (n-1) = 2n -1.个，并且这棵树具有以下性质：
- 这是一个二叉堆。
- 原树两点间边权的最大（最小）值为两点LCA的权值。
- 重构树中原树的节点全部为叶子节点，其余节点都是新建的点。
kruskal重构树的构造
与kruskal类似。先对边进行排序，然后使用并查集辅助加边。新建一条边时，进行以下操作：
- 新建节点（编号从N+1开始）（点权为对应边权）。
- 把原有两点和新建的点加入并查集维护。
- 把原有两点所在子树连到新建节点上。
算法进行完毕后，若原图联通，则我们建立出的必然是一棵以最后新建的节点为根的有根树。
若原图不连通，则建出的为一个森林。
此时可以遍历每个节点，将其并查集的根作为树的根。
（因为在并查集的根就是最后加的节点）
下面，我们来一一考察我们前面说的kruskal重构树的性质。
为了方便性质的说明，不妨设边是从小到大排序的，因为这和从大到小排序的情况是基本相同的。
首先，考虑我们对每次加点的处理。有两种情况，第一，由两个原图上的点直接生成，这样一定是二叉的。第二，由一个原图上的点和一个之前生成的新点构成，这样还是二叉的。再考虑到我们加点的顺序，根据kruskal算法，我们是按照边权进行排序加点的，后加的点一定大于先加的点，又后加的点的深度一定小于等于先加的点的深度，故这是一个大根堆。
现在我们来对性质的第三点进行说明。其实这一点很容易理解，因为对于任意一个原图上的点，它必然有父节点且必然没有子节点，所以它是叶子节点。
现在我们来对性质里面的第二点进行说明。
第一，不难发现原图两点间的最大值最小的路径与原图的最小生成树中的两点间最大值最小的路径完全相同。因为在构建最小生成树的过程中是舍弃掉了一些边权很大的边，对这条路径不会产生影响。
第二，考虑kruskal重构树中两点LCA的意义，由于LCA只往上走而不往下走，而这是一个大根堆，所以即尽量走边权大的边，这样可以保证走出的路径一定是最优的。又这两点的lca是这条路径中边权最大的边重构成的点，故这即为所求。
应用
基础应用比如求最小值最大，最大值最小的路径等。
还可以处理一些计算边对点的贡献的题。
给定一个带权树，树上任意两点间的路径权值d(x,y)定义为x,y这两个点之间路径上的最小值，树上任意一点x的权值定义为这个点到树上其他所有点的路径权值和，即 \[ \sum_{i=1}^{n}d(x,i) \] ，现求树上一点，使得这个点的权值最大，输出这个值。
显然不可能暴力。
考虑计算每条边造成的贡献。显然一条边对所有路径经过这条边的点对都有贡献。
考虑使用kruskal重构树来计算。
原树中的边即为重构树中的非叶子节点。
从这些点的左子树到右子树必然经过这条边，且由kruskal重构树的性质，这条边是路径中最短的那条边，就可以统计该点的贡献。
区间加法使用树状数组维护即可。