摘要：
题目 思路假设我们直接计算最小生成树，此时，最小生成树上有一条边是连接点。当恰好有一条连接边时，设最小生成树权重之和为，则我们可以将其视为二维平面上的一个点。连接这些点后，必须有一个较低的凸壳。因为在仅仅删除黑边和添加白边的过程中，为了使生成树的权重尽可能小，必须选择差异最小的一个并首先添加。所以我们可以使用wqs二分法来解决这个问题。时间复杂度，其中是最大边权重。
题目链接：https://www.luogu.com.cn/problem/P5633
给你一个有 (n) 个节点，(m) 条边的带权无向图，你需要求得一个生成树，使边权总和最小，且满足编号为 (s) 的节点正好连了 (k) 条边。
(nleq 5 imes 10^4,mleq 5 imes 10^5,kleq 100)。
假设我们直接求出了最小生成树，此时最小生成树上有 (t) 条边是连接 (s) 点的。不妨设 (t<k)。
如果此时加入一条没被选择的连接 (s) 的边，必然会形成一个环，那么我们找到环上权值最大的不连接 (s) 的边删去。重复上述过程就可以得到一个有 (k) 条边连接 (s) 的生成树。
设恰好有 (i) 条连接 (s) 的边时最小生成树权值和为 (s_i)，那么我们可以把 ((i,s_i)) 看做一个二维平面上的点。连接这些点之后必然是一个下凸壳。因为在刚刚删去黑边加入白边的过程中，为了让生成树权值尽量小，一定是选择差值最小的先加入。
于是就可以采用 wqs 二分解决这个问题了。
时间复杂度 (O(mlog mlog V))，其中 (V) 是边权最大值。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=50010,M=500010;
int n,m,s,k,cnt,maxd,father[N];
ll sum,ans;
struct edge
{
int u,v,dis;
}e[M];
bool cmp(edge x,edge y)
{
return x.dis<y.dis;
}
int find(int x)
{
return x==father[x]?x:father[x]=find(father[x]);
}
void kruskal()
{
sort(e+1,e+1+m,cmp);
for (int i=1;i<=m;i++)
{
int x=find(e[i].u),y=find(e[i].v);
if (x!=y)
{
if (e[i].u==s || e[i].v==s) cnt++;
sum+=e[i].dis; father[x]=y;
}
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&k);
for (int i=1;i<=n;i++) father[i]=i;
for (int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].dis);
if (e[i].u!=s && e[i].v!=s)
father[find(e[i].u)]=find(e[i].v),cnt++;
maxd=max(maxd,e[i].dis);
}
if (cnt+k<n-1) { cout<<"Impossible"; return 0; }
int l=-maxd,r=maxd,mid;
ans=-1;
while (l<=r)
{
mid=(l+r)>>1;
for (int i=1;i<=m;i++)
if (e[i].u==s || e[i].v==s) e[i].dis+=mid;
cnt=sum=0;
for (int i=1;i<=n;i++) father[i]=i;
kruskal();
if (cnt>=k) l=mid+1,ans=sum-1LL*mid*k;
else r=mid-1;
for (int i=1;i<=m;i++)
if (e[i].u==s || e[i].v==s) e[i].dis-=mid;
}
if (ans!=-1) cout<<ans;
else cout<<"Impossible";
return 0;
}