题目描述

C 城将要举办一系列的赛车比赛。在比赛前,需要在城内修建 $m$ 条赛道。

C 城一共有 $n$ 个路口,这些路口编号为 $1,2,…,n$,有 $n-1$ 条适合于修建赛道的双向通行的道路,每条道路连接着两个路口。其中,第 $i$ 条道路连接的两个路口编号为 $a_i$ 和 $b_i$,该道路的长度为 $l_i$。借助这 $n-1$ 条道路,从任何一个路口出发都能到达其他所有的路口。

一条赛道是一组互不相同的道路 $e_1,e_2,…,e_k$,满足可以从某个路口出发,依次经过道路 $e_1,e_2,…,e_k$(每条道路经过一次,不允许调头)到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全,要求每条道路至多被一条赛道经过。

目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案,使得修建的 $m$ 条赛道中长度最小的赛道长度最大(即 $m$ 条赛道中最短赛道的长度尽可能大)

输入输出格式

输入格式

输入文件第一行包含两个由空格分隔的正整数 $n,m$,分别表示路口数及需要修建的赛道数。

接下来 $n-1$ 行,第 $i$ 行包含三个正整数 $a_i,b_i,l_i$,表示第 $i$ 条适合于修建赛道的道连接的两个路口编号及道路长度。保证任意两个路口均可通过这 $n-1$ 条道路相互到达。每行中相邻两数之间均由一个空格分隔。

输出格式

输出共一行,包含一个整数,表示长度最小的赛道长度的最大值。

样例

样例输入

样例输出

数据规模与约定

其中,“分支不超过 3” 的含义为:每个路口至多有 3 条道路与其相连。 对于所有的数据,$2 \leq n \leq 50,000$,$1 \leq m \leq n − 1$,$1 \leq a_i, b_i \leq n$,$1 \leq l_i \leq 10,000$。

思路

我就顺着我考场上的思路讲一讲这道题吧。

首先对于 $m=1$ 的数据,我们显然只要找到直径长度;

对于一条链的情况,二分答案,对于每次二分出来的 $mid$,从根开始贪心选取一段边,累计长度大于等于 $mid$ 的时候就计入答案,重新开始寻找下一段,得出对于 $mid$ 最大的答案,判断它是否大于 $m$;

对于菊花图,由于路径最多经过两条边,我们实质上是要在 $n-1$ 条边中选一共 $m$ 次,每次选出一条独立的边,或者一对边,使得最终每条边的长度 / 每对边的长度和尽量大。对于每次二分出来的 $mid$,长度大于 $mid$ 的边独立地选出,而小于 $mid$ 的边尝试一长一短两两配对,用双指针在排过序的长度数据中扫描一遍,得出对于 $mid$ 最大的答案,判断它是否大于 $m$;

对于 “分支不超过 3” 的图,也就是除根节点之外,每个点只有两个儿子,同样我们二分答案。首先定义几个概念,我们称从一条赛道两端点 $LCA$ 开始的,到一个端点结束的链为对应赛道的半链,令 $f_i$ 为以 $i$ 为 $LCA$ 的最优半链长度。暂时不考虑根节点,如果 $i$ 只有一个儿子 $v$,若 $f_v + l_i \geq mid$,直接将 $f_v + l_i$ 计入答案,否则,$f_i = f_v + l_i$;如果 $i$ 有两个儿子,如果它们可以直接单独计入答案则直接计入,否则考虑是否可以将这两个儿子牵引的两条半链合并,合并后长度大于 $mid$ 则直接计入答案,否则选取最长的一段转移到 $f_i$,对于可能有三个儿子的根节点,遵循的原则同样是尽量独立选取两个儿子,否则尝试合并两条半链计入答案;

如果我们结合菊花图和 “分支不超过 3” 的图这两种情况,我们就可以搞定 100% 的数据。继承上面半链和 $f_i$ 的定义,我们要做的是在使最多的儿子对答案做出贡献的同时,尽量大地将 $f_{son}$ 的值转移给 $f_i$。因为 $f$ 的一个值最多对答案产生 1 的贡献,所以使儿子做出更少贡献,转移更大的 $f_i$ 不可能使答案变优,我们的贪心第一关键字就可以设为使儿子做出最大的贡献。在菊花图的算法中,我们只满足了第一个条件,但不需要考虑 $f_i$ 进一步的转移,而我认为这一点正是 A 掉本题的重点。也就是说,我们要在儿子的 $f$ 值中,选出一个最优的转移至 $f_i$,使得剩下的 $f$ 值的合法匹配最多。同样可以二分转移至 $f_i$ 的儿子,剩下的和菊花图的做法相同。

总结一下正解:首先二分答案,贪心计算对于 $mid$ 的最大可能答案,判断它和 $m$ 的大小。我们称从一条赛道两端点 $LCA$ 开始的,到一个端点结束的链为对应赛道的半链,令 $f_i$ 为以 $i$ 为 $LCA$ 的最优半链长度。要求对于 $i$ 所有儿子的 $f$,在保证两两匹配数最多的同时,向 $f_i$ 转移尽可能大的值。于是将所有 $f$ 排序贪心找到最大匹配数,然后,二分找到转移给 $f_i$ 的值。

复杂度不太会证,应该接近 $\Theta(n\log n \log \dfrac{\sum{l_i}}{m})$ 吧。

代码

本文同步更新于 洛谷博客

  1. kal0rona
    Oct 05, 2019

    tql

    Reply