2 条题解

  • 3
    @ 2026-11-3 14:06:37

    感谢此题让我知道我的代码能力现在区完了。

    思路非常简单的题,要求找到一条路径满足上面最小的一个点最大。显然路径应该是最大生成树上的简单路径。类似克鲁斯卡尔的,问题的本质是从大到小加边,问两点最早什么时候联通,使得两点联通的边就是答案(如果仔细研究过最小生成树就能更好的理解)。

    实现上:建立最大生成树(可能有多个但是对于这个问题来说本质相同),对于每组询问查询两点简单路径上的最小点权 minmin,两端点的点权分别减去 minmin 求和就是答案。查询可以树上倍增实现或者树剖套st表。

    强烈建议大家写一写货车运输和严格次小生成树来加深对这一类问题的理解

    某zt先认为应该二分套可持久化并查集做显然是火箭毛毛虫。值得一提的是去年九月遇到了该题目的弱化版(只有一个询问),我深刻指出二分套可持久化并查集的做法成功带跑一机房人的思路。

    • 1
      @ 2026-11-3 16:06:23

      最新研究表明本题可以使用树剖加线段树双log草过去。只需要在并查集上使用路径压缩加启发式合并卡常即可。

      • 1

      [2026济南登峰营] D1 P3 恼鬼偷袭(vex) - 文件读写

      信息

      ID
      964
      时间
      2000ms
      内存
      512MiB
      难度
      9
      标签
      (无)
      递交数
      54
      已通过
      5
      上传者