[EER1]河童重工
给定两棵树 (T_1,T_2)，定义点 ((u,v)) 的边权为 ( extrm{dist}_1(u,v)+ extrm{dist}_2(u,v))
这是一张完全图，求解其 MST
(nle 10^5)，时限为 ( m 4s)
( m Sol:)
先考虑子问题，Tree MST，我们可以做到 (mathcal O(nlog n))，甚至当作 (mathcal O(n)) 看待。
对于 Tree MST，我们对于每个点建立 (x') 并连接 (x' o x) 的边，边权为 (w_x)，问题变为求解这些关键点的 MST
考虑对于每个点，记 (pre_x) 表示离他最近的关键点，( extrm{dis}_x) 表示其到此点的距离，那么我们不妨枚举每条边 ((x,y))，然后将 ((pre_x,pre_y, extrm{dis}_x+ extrm{dis}_y+w(x,y))) 加入边集，然后对这 (mathcal O(n)) 条边做 Kruskal 即可得到答案。
正确性证明：
考虑 Kruskal 过程中，如果存在边 ((x,z),(y,z)) 均在 ((x,y)) 之前被考虑到，那么 ((x,y)) 这条边便没有意义。
假设上述边不够充分，那么即存在一个点对 ((x,y)) 满足这条边需要加入集合，我们可以考虑 (x o y) 的路径，设沿途依次为 (a_1,a_2...a_k) 这些节点，那么不存在 ((i,i+1)) 使得 (a_i,a_{i+1}) 离最近的点分别为 (x,y)
于是总有一段前缀与后缀满足离他最近的点为 (x,y)，设沿途最近的点依次为 ({x,x,x...z,z...p,p...y,y})，那么容易发现，(x o z) 的边权小于 (x o y)，(z o p) 的边权小于 (z o y)，依次类推，于是 (x o y) 的边无意义。
接着考虑原题：
- 类似于 Tree MST，我们对第一棵树 (T_1) 进行点分治，设当前分治重心为 (u)，然后对于无序二元组 ((x,y)) 我们定义他们的距离为 ( extrm{dist}_1(x o u o y)+ extrm{dist}_2(x,y))，那么处理完当前轮的 MST 后就可以当作子问题递归处理。
- 容易发现这样不会影响正确性（同一棵子树内的点距离更大）
这个时候我们可以转换为上述问题，考虑将这些点拿出来建立虚树，并补充特殊点，接着每轮分治我们得到 (mathcal O( m size)) 的边，总体边数为 (mathcal O(nlog n))，然后直接做一边 Kruskal 即可得到答案。