全部评论 2

  • 我们每次二分最长路径最小值为k的情况,然后我们就要在所有路径中寻找满足条件的路径,不难发现如果当前边权w>=max-k(最大路径都满足,则其余路径均满足),并且w这条边在所有比k大的路径上,那么我们就发现当前k满足情况。那么我们怎么标记大于k的路径呢?这里就要用到我们的树上差分了,对于一段路径,起点为a,终点为b,取其lca,则我们统计树上前缀和,cf[a],cf[b],cf[lca]

    2023-03-11 来自 上海

    2
  • 首先了解一下题目是什么意思:
    给你一棵树,一些路径,让你求在去掉一条边权的情况下,最长路径长度的最小值。当我第一次看到这道题时,我第一反应想到的是点分治,看了别人思路之后发现需要用树上差分,突然发现树上差分好像很妙妙的样子,然后顿时人生明亮了起来。

    2023-03-11 来自 上海

    2

热门讨论