题目描述
C 城将要举办一系列的赛车比赛。在比赛前，需要在城内修建 mm 条赛道。
C 城一共有 nn 个路口，这些路口编号为 1,2,…,n1,2,…,n，有 n-1n−1 条适合于修建赛道的双向通行的道路，每条道路连接着两个路口。其中，第 ii 条道路连接的两个路口编号为 a_iai 和 b_ibi，该道路的长度为 l_ili。借助这 n-1n−1 条道路，从任何一个路口出发都能到达其他所有的路口。
一条赛道是一组互不相同的道路 e_1,e_2,…,e_ke1,e2,…,ek，满足可以从某个路口出发，依次经过 道路 e_1,e_2,…,e_ke1,e2,…,ek（每条道路经过一次，不允许调头）到达另一个路口。一条赛道的长度等于经过的各道路的长度之和。为保证安全，要求每条道路至多被一条赛道经过。
目前赛道修建的方案尚未确定。你的任务是设计一种赛道修建的方案，使得修建的 mm 条赛道中长度最小的赛道长度最大（即 mm 条赛道中最短赛道的长度尽可能大）
输入输出格式
输入格式：
输入文件第一行包含两个由空格分隔的正整数 n,mn,m，分别表示路口数及需要修建的 赛道数。
接下来 n-1n−1 行，第 ii 行包含三个正整数 a_i,b_i,l_iai,bi,li，表示第 ii 条适合于修建赛道的道 路连接的两个路口编号及道路长度。保证任意两个路口均可通过这 n-1n−1 条道路相互到达。每行中相邻两数之间均由一个空格分隔。
输出格式：
输出共一行，包含一个整数，表示长度最小的赛道长度的最大值。
题意 一棵树 给定建m条赛道 要使得这m条赛道中最短的赛道最长 赛道上每一条边只经过一次
解题方法
m = 1 贪心求树的直径就完事了
链上部分分 二分 最短的赛道的长度 上界为直径 下界为1 nlog所有边边长和 完事了
菊花图 将权值排序 将最大的与第m大的组成赛道 第二大与第m-1大组成赛道 .... 完事了
55pts get
满分做法
我们要做的是在使最多的儿子对答案做出贡献的同时，传递上去的值是最大的
具体做法如下
二分最短赛道的长度
1.每个树节点 保存子节点传来的最大值加上与该节点的连边长度。若该值大于等于k 则答案+1。 若小于k 将该值插入multiset集合 （将该值往上传）。
2.然后处理multiset集合中的元素 若集合仅有一个元素 那将该元素传至父节点（该数是传至父节点的最大的数）
若有多个元素 找到第一个大于等于k-begin的数 （即能和begin组成一条赛道的数）
如果该数等于begin且begin仅有一个数 （这种情况一般是begin>k-begin） 迭代器++
找下一个大于他的数 如果迭代器等于end 即找不到与begin组成大于k的数 将begin删除 如果找到 begin和该数一同删除 答案++ 然后就解决啦！
#include <cstdio>
#include <algorithm>
#include <set>
#include <iostream>
using namespace std;
const int M = ;
int head[M],nxt[M],to[M],c[M];
int val;
int ans;
int size;
int n ,m;
int zj,gd;
multiset<int> s[M];
multiset<int> ::iterator it;
void add(int u ,int v,int w)
{
nxt[++size] = head[u];
head[u] = size;
to[size] = v;
c[size] = w;
}
void dfs(int now,int fa,int k) // 求树的直径
{
if(k > zj) gd = now,zj = k;
for(int i = head[now];i;i = nxt[i])
{
if(to[i] == fa) continue;
dfs(to[i],now,k+c[i]);
}
}
int dfs1(int now,int fa,int k)
{
s[now].clear();
for(int i = head[now];i;i = nxt[i])
{
if(to[i] == fa) continue;
val = dfs1(to[i],now, k) + c[i];
if(val >= k) ans++;
else s[now].insert(val);
}
int Max = ;
while(!s[now].empty())
{
if(s[now].size() == ) return max(Max,*s[now].begin());
it = s[now].lower_bound(k-*s[now].begin());
if(it == s[now].begin()&&s[now].count(*it) == ) it++;
if(it == s[now].end())
{
Max = max(Max,*s[now].begin());
s[now].erase(s[now].find(*s[now].begin()));
}
else{
ans++;
s[now].erase(s[now].find(*s[now].begin()));
s[now].erase(s[now].find(*it));
}
}
return Max;
}
bool check(int k)
{
ans = ;
dfs1(,,k);
if(ans >= m) return true;
else return false;
}
int main(){
scanf("%d%d",&n,&m);
int u , v , w;
for(int i = ;i <= n - ;i++)
{
scanf("%d%d%d",&u,&v,&w);
add(u ,v , w);
add(v , u ,w);
}
dfs(,,); //
dfs(gd,,); // 两遍dfs求树的直径
int l = ,r = zj;
while(l < r)
{
int mid = (l + r + ) >> ;
if(check(mid)) l = mid;
else r = mid - ;
}
printf("%d",l);
}