Kruskal 重构树学习笔记

前言

今天题单里面有这个题（AGC002D）需要用到相关知识就学习了一下。

以该题为例讲解一下kruskal重构树的构成与性质。

构造

用图片来展示构造的过程，简单来说就是将边权从小到大排序，然后给每条边的两点建出一个父亲来，父亲的点权就是原先这条边的边权，如果其中一方或双方都在某个新建节点的子树下，则以该子树根节点为儿子重复上述过程，以下为图例。

性质

从叶子到父亲，点权都在递增并且每个新建节点的子树内叶子个数即为以这条边为最大值时能经过的所有点了。在这题里二分一下也就结束了。