题解 CF1583H Omkar and Tours

· · 题解

第一问的做法比较简单。

我们将询问离线，按照限制从小到大排序，随时加入变为合法的边，并查集维护一下即可。

难点在于第二问。

注意到两点间费用为边权的最大值。我们考虑建立原树的 \texttt{Kruscal} 重构树，就将求路径上最大值转化为了求 lca 的点权。由于 \texttt{Kruscal} 重构树为一个大根堆，因此深度最小的 lca 即为第二问的答案。

我们有引理，要使两点之间 lca 的深度最小，应当尽量让两点的 dfs 序差异尽量大。这一点画图很好理解，网上也有很多证明，这里就不再赘述。

由此我们可以知道，一个点到一个联通点集之间最小深度的 lca 有两种情况：从这个点到点集中 dfs 序最小的节点，或者到点集中 dfs 序最大的节点。同样可以并查集维护。

时间复杂度 \mathcal O((n+q)\ logn)，取决于 lca 的求法。

AC代码