题意：求一种特殊的最小生成树。给定一个有你$n$个节点和$m$条边的图，找出一个生成树满足从根节点1直接连向其余节点的边要恰好是$k$条，在此条件下生成树的权值和最小。

二分一个数$x$，给每条与1相连的边加上这个权值，跑最小生成树判断与1相连的边大于还是小于$k$即可。

代码：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #define M 100010 6 using namespace std; 7 struct point{ 8     int u,v,co,dis,id;bool flag; 9 }e[M];10 int n,m,k,l,r,cnt;11 int res[M],fa[M];12 bool cmp(point a1,point a2) {
   return a1.dis
         
          
           e[i].v) swap(e[i].u,e[i].v);39 e[i].co=(e[i].u==1||e[i].v==1);40 e[i].id=i;41 }42 l=-1e5,r=1e5;int minn=1e9;43 while(l<=r)44 {45 int mid=(l+r)/2;46 int num=check(mid);47 if(num>=k) l=mid+1,minn=mid;48 else r=mid-1;49 }50 if(minn==1e9) {puts("-1");return 0;}51 else52 {53 for(int i=1;i<=m;i++) if(e[i].co==1) e[i].dis+=minn;54 sort(e+1,e+1+m,cmp);55 int tot=0,ans=0;56 for(int i=1;i<=n;i++) fa[i]=i;57 for(int i=1;i<=m;i++)58 {59 int u=e[i].u,v=e[i].v;60 if(find(u)!=find(v)&&tot+(e[i].co==1)<=k)61 {62 fa[find(v)]=find(u);63 tot+=(e[i].co==1);64 ++ans;65 e[i].flag=true;66 } 67 }68 if(ans