题目描述
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$ 条道路相互到达。每行中相邻两数之间均由一个空格分隔。
输出格式
输出共一行，包含一个整数，表示长度最小的赛道长度的最大值。
样例
样例输入
9 3
1 2 6
2 3 3
3 4 5
4 5 10
6 2 4
7 2 9
8 4 7
9 4 4样例输出
15数据规模与约定
其中，“分支不超过 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})$ 吧。
代码
#include
#define mid ((l+r)>>1)
#define ll long long
#define maxn 50010
using namespace std;
struct Edge{
int to,next,val;
Edge(int a=0,int b=0,int c=0){
to=a,next=b,val=c;
}
}l[maxn<<1];
int head[maxn],cnt,n,m;
vector son[maxn];
ll f[maxn];
int subans[maxn];
void Add(int a,int b,int c){
l[++cnt]=Edge(b,head[a],c);
head[a]=cnt;
}
int check(int u,int pos,int tot,ll x){
int res=0,l=0;
for (register int r=tot-1;r;--r){
r-=r==pos;
while (l=r) break;
++res;++l;
}
return res;
}
void Dfs(int u,int fa,ll x){
f[u]=subans[u]=0;
son[u].clear();
for (register int i=head[u];i;i=l[i].next){
int v=l[i].to;
if (v==fa) continue;
Dfs(v,u,x);
f[v]+=l[i].val;
if (f[v]>=x) subans[u]++;
else son[u].push_back(f[v]);
}
int tot=son[u].size();
sort(son[u].begin(),son[u].end());
int l=0,r=tot,sub=0,res;
for (register int r=tot-1;r;--r){
while (l=r) break;
++sub;++l;
}
subans[u]+=sub;
if (sub*2==tot) return;
l=0,r=tot-1;
while(l<=r){
int tem=check(u,mid,tot,x);
if (tem==sub) res=mid,l=mid+1;
else r=mid-1;
}
f[u]=son[u][res];
}
bool check(ll x){
int tem=0;
Dfs(1,0,x);
for (register int i=1;i<=n;++i)
tem+=subans[i];
return tem>=m;
}
int main(){
ll l=0,r=0,ans,c;
scanf("%d%d",&n,&m);
for (register int i=1,a,b;i 本文同步更新于 洛谷博客。