P5021 [NOIP2018 提高组] 赛道修建 题解

· · 题解

好题，鉴定为人类智慧题。

考虑在二分答案时如何 check。

发现这并不好做，因为我们并不好确定具体的路径。

尝试用类似树形 DP 的方法，求出一个子树内最多能分出多少长度 ≥k 的路径。

有一个 trival 的性质，就是如果一个路径经过子树但不被完全包含（子树外也有一部分），那么这样的路径有且仅有一条。

将子树内经过子树根的路径分分类，第一类完全包含于子树，第二类就是上面的情况且只有一条路径。

发现第二类是可以传递给父亲的，于是就对每个节点维护 f_i 表示以 i 为端点保留的路径长度。父节点的 f_i 由子节点合并而来，并在此过程中统计答案。这就转化成了递归问题。

合并时采取贪心策略。如果一部分 f_v + e_{u,v} 本身就大于了 k，就不用去管，并产生 1 的贡献；剩下的两两合并，最优的方案一定是两两恰好合并为 >k 的路径并剩下一个较大的作为 f_u。

具体实现可以在 multiset 中从小到大二分，不再赘述。