考场上把暴力都打满了，结果文件输入输出写错了....

当时时间很充裕，如果认真想想正解是可以想出来的..

问你 长度最小的赛道长度的最大值

显然二分答案

考虑如何判断是否可行

显然对于一个节点，它最多只能向父亲传一条路径长度

那么其它路径的合并只能在子树间进行

贪心一波，如果一段路径在子树就可以合并出合法长度

那么直接合并一定是不会比传给父亲再考虑合并更劣的

子树都合并完后，剩下的肯定传最长的长度给父亲

考虑在子树内如何贪心地进行最优合并

显然最小的边去找最小的能使它合法的边合并

（注意不是最大的边去找最小的能使它合法的边合并）

那么用一个multiset存一下当前节点的各个边长

然后就按前面的方法一个个合并就好了

注意和并时的一些细节和二分的上界，（因为multiset常数大，所以要把上界设为总长除赛道数）

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long ll;const int N=1e5+7,INF=2e9+7;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}int fir[N],from[N<<1],to[N<<1],val[N<<1],cntt;inline void add(int &a,int &b,int &c){ from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c;}int n,m,mid,cnt;int f[N];multiset 
           
             S;multiset 
            
             ::iterator it,itt,pit;void dfs(int x,int fa){ for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(fa==v) continue; dfs(v,x);//先把每个节点遍历一波再从后往前更新会比较方便(不然要开一堆set) } S.clear();//记得清空 for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(fa==v) continue; if(f[v]+val[i]>=mid) cnt++;//只考虑小于mid的长度的合并(大于的不用合并都有贡献) else S.insert(f[v]+val[i]);//注意把儿子传的边长加上父子间的边长 } it=S.begin(); while(it!=S.end()) { itt=S.lower_bound(mid-(*it)); if(itt==it) itt++;//注意细节 if(itt!=S.end()) cnt++,S.erase(itt),pit=it,it++,S.erase(pit); else it++; } f[x]=0;/*记得先清空f*/ it=S.begin(); if(S.end()!=it) it=S.end(),it--,f[x]=*it;//注意必须有边传才更新f}inline int judge(){ cnt=0; dfs(1,1); return cnt>=m;}int main(){ int a,b,c,s=0; n=read(); m=read(); for(int i=1;i
             
              1) { mid=L+R>>1; if(judge()) L=mid; else R=mid; } mid=R; printf("%d",judge() ? R : L); return 0;}