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

笛卡尔树

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

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

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

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

代码的话大概长这样:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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$ 重构树则是每次取最小值的边分树

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