挺简单的知识点（？）

概念

首先 Kruskal 算法是用来求最小生成树的算法之一，其思想是贪心。

而 Kruskal 重构树就是将整张图重建为二叉树。

在跑 Kruskal 的过程中我们会从小到大加入若干条边。现在我们仍然按照这个顺序。

首先新建 \(n\) 个集合，每个集合恰有一个节点，点权为 \(0\) 。

每一次加边会合并两个集合，我们可以新建一个点，点权为加入边的边权，同时将两个集合的根节点分别设为新建点的左儿子和右儿子。然后我们将两个集合和新建点合并成一个集合。将新建点设为根。

不难发现，在进行 \(n-1\) 轮之后我们得到了一棵恰有 \(n\) 个叶子的二叉树，同时每个非叶子节点恰好有两个儿子。这棵树就叫 Kruskal 重构树。

比如这张图

它会被重构成

性质

Kruskal 重构树有很多性质

Kruskal 重构树是一棵二叉树
原图中所有节点与 Kruskal 重构树上的叶子节点一一对应
每个节点的点权是其子树所有节点（包括本身）中的最大点权（不考虑叶子结点）
两点之间所有简单路径上最大边权的最小值 \(=\) 最小生成树上两个点之间的简单路径上的最大值 \(=\) Kruskal 重构树上两点之间的LCA的权值。

Code

动态数组版

const int N=1e5;
int n,m;
int k,t,s,d;
struct node
{
    int u,v,w;
    bool operator<(const node& e) const {return w<e.w;}
}ee[N];
vector<int> e[N];
int d[N],f[N],a[N],down[N],fa[N][18];
int cnt;
int find(int x) 
{
    return f[x]==x ? f[x] : f[x]=find(f[x]);
}
int Kruskal()
{
    sort(ee+1,ee+1+m);
    for(int i=1;i<=2*n;++i)
        f[i]=i;
    cnt=n;
    for(int i=1;i<=m;++i)
    {
        int u=find(ee[i].u),v=find(ee[i].v);
        if(u!=v)
        {
            d[++cnt]=ee[i].w;
            f[u]=f[v]=f[cnt]=cnt;
            e[cnt].fush_back(u);
            e[cnt].fush_back(v);
        }
    }
    return cnt;
}