Luogu6199 [EER1] 河童重工

发表于 分类于 ， ， 阅读次数：

题意：给出两棵树 ，有边权，点的标号对应。

生成无向图 ， 之间的边权为 。

求这张图的最小生成树的边权和，，时限 。

  • 子问题：AT_cf17_final_j Tree MST

  • 结论：欲求边集 的最大权值生成森林，可以先将 划分为两部分 ，分别求出两者的最大权值生成森林，，再求 的最大生成森林即可。

    用 Kruskal（拟阵的性质）容易证明。

先对 下手，在 上点分治，只考虑越过分治中心的路径对应的连边。

dfs 求出每个点的深度，则 之间连边的代价就是 注意，当两个点在同一子树内时，这个式子并不正确，但是比直接连接的真实值更大，所以不影响答案。

现在我们就是要对这个东西求一个 MST。

记 上的分治区域为点集 ，在 上对 建立虚树，然后就变成上面的子问题了。

虚树里面的辅助点不应参与连边，可以把 设置为 INF 便于判断。

子问题和建虚树的复杂度均是 ，本题的复杂度就是 。