树

有 $n$ 个点和 $n-1$ 条边的无向连通图

笛卡尔树

考虑树 $T$ 的每个点 $u$ 有权 $a_u$，现在要对任意两点 $u,v$，求它们在树上的最短路上（显然路径唯一）的最小点权

一个不怎么优美的做法就是倍增维护，或者树链剖分，然而这样都不太好

考虑一种分治的思想：每次把点权最小的那个点拿出来，然后把它在树上的邻边都断开，然后依次对剩下的所有连通块执行这个操作，最后按照拿出来的点的先后顺序重构出一棵树，这样任意两个点在原树上的最短路上的最小点权的那个点，一定是在新树上这两个点的 $lca$

至于如何建出这棵树，那么就先按照点权从大到小考虑，这样每个点 $u$ 的重构树上的儿子就是目前为止，它所有出边的连通块的最小点权，并查集维护一下即可

代码的话大概长这样：

int root = 0;
vector<int> ids, acc(n + 5), vis(n + 5);
g = vector<vector<int> > (n + 5, vector<int> ());
for(int i = 1 ; i <= n ; ++ i) {
    ids.emplace_back(i);
}
sort(ids.begin(), ids.end(), [&] (int i, int j) {
    return w[i] > w[j];
});
for(int i = 1 ; i <= n ; ++ i) {
    acc[i] = i;
}
function<int(int)> get = [&] (int x) {
    return x == acc[x] ? x : acc[x] = get(acc[x]);
};
for(const int &u: ids) {
    vis[u] = 1;
    for(int i = head[u] ; i ; i = rest[i]) {
        int v = to[i];
        if(vis[v]) {
            g[u].emplace_back(get(v));
            acc[get(v)] = u;
        }
    }
    root = u;
}

$kruskal$ 重构树

当然点权可以转化为边权，也就是对于边 $e=(u,v)$，可以对其赋权 $a_e=\min(a_u,a_v)$，这样链上点权最小值就成了链上边权最小值

这样的话每次选取边权最小的边，然后把它断开，之后递归处理多出来的两个连通块，最后重构出棵树就好了

这里需要注意每条边实际上把它也当成了一个点来考虑了

当然边权依然可以转化为点权，只需要新建点 $w$，然后连边 $(u,w),(w,v)$，之后令 $a_u=a_v=\infty$，以及 $a_w=a_e$ 即可

如果用边权转化为点权的话，不难发现 $kruskal$ 重构树删去叶子后就是笛卡尔树了

总结

笛卡尔树实际上是每次取最小值的点分树，而 $kruskal$ 重构树则是每次取最小值的边分树

~~如果遇见了某种重构树后对其进行边分树的题的话，前者需要三度化，后者并不需要~~