原题链接：P5021 赛道修建
题意
给定一颗树（不是二叉树），在树上找到$m$条链。
求最短链的最大值。
分析
其实在考场上想出正解了的。。
就是因为不会STL结果挂了。。
要是写出来就1=了呢。。
气死了。
首先因为要求最短链的最大值，很容易想到二分。
二分出最短链的长度$x$，然后要在树上找到$m$条长度大于$x$的链。
分析问题，每条边只能用一次，然后可以发现每个点到他的父亲点，只能有一条链向上传递，其他的链只能互相组合。
很简单的贪心，我们要让这条向上传递的链最大，其他的链组合成尽量多的链，使组合成的链大于$x$。
如果一条链本身就大于$x$，我们直接在总链数上累加。
不然记录下这条链。
我在考场上想的是，把所有的链记录下来，然后排序进行双指针。
这样好像是$O(n^2logn)$的，而且实现巨烦。。
考场上打了一个半小时，最终没有AK DAY1。。。
回来看到网上的处理方法是用multiset。。
考场上怎么就没想到STL呢。。
把所有小于$x$的链丢到multiset里去，每次取出最小的链记为$y$，在链里面找出第一个大于等于$x-y$的链，然后同时删掉这两条链就可以了。
要注意集合里只有一条链的情况。
实现起来巨简单。。。
气死我了鸭……
代码
1 #include <bits/stdc++.h> 2 #define mid ((l+r)>>1) 3 using namespace std; 4 const int N=5e5+1009; 5 int read(){ 6 char c;int num,f=1; 7 while(c=getchar(),!isdigit(c))if(c=='-')f=-1;num=c-'0'; 8 while(c=getchar(), isdigit(c))num=num*10+c-'0'; 9 return f*num; 10 } 11 int n,m,fa[N],val[N],cnt; 12 int head[N],ver[N*2],nxt[N*2],edge[N*2],tot=1; 13 int dfs(int x,int v){ 14 multiset<int>S; 15 multiset<int>::iterator it; 16 S.clear(); 17 for(int i=head[x];i;i=nxt[i]){ 18 if(ver[i]==fa[x])continue; 19 int val=dfs(ver[i],v)+edge[i]; 20 if(val>=v)cnt++; 21 else S.insert(val); 22 } 23 int maxn=0; 24 while(!S.empty()){ 25 if(S.size()==1)return max(maxn,*S.begin()); 26 it=S.lower_bound(v-*S.begin()); 27 if(it==S.begin()&&S.count(*it)==1)it++; 28 if(it==S.end()){ 29 maxn=max(maxn,*S.begin()); 30 S.erase(S.find(*S.begin())); 31 }else { 32 cnt++; 33 S.erase(S.find(*it)); 34 S.erase(S.find(*S.begin())); 35 } 36 } 37 return maxn; 38 } 39 bool check(int x){ 40 cnt=0;dfs(1,x); 41 if(cnt>=m)return 1; 42 else return 0; 43 } 44 void build(int x,int pre){ 45 for(int i=head[x];i;i=nxt[i]){ 46 if(ver[i]==pre)continue; 47 fa[ver[i]]=x; 48 build(ver[i],x); 49 } 50 } 51 void add(int u,int v,int w){ 52 ver[++tot]=u;nxt[tot]=head[v];head[v]=tot;edge[tot]=w; 53 ver[++tot]=v;nxt[tot]=head[u];head[u]=tot;edge[tot]=w; 54 } 55 int main() 56 { 57 int l=0,r=0; 58 n=read();m=read(); 59 for(int i=1;i<n;i++){ 60 int u,v,w; 61 u=read();v=read();w=read(); 62 add(u,v,w);r+=w; 63 } 64 build(1,0); 65 while(l<=r){ 66 if(check(mid))l=mid+1; 67 else r=mid-1; 68 } 69 printf("%d ",r); 70 return 0; 71 }