此题与P5633类似，我想用wqs二分做

此代码与第二篇题解对拍不停，但是一直wa

求调、求hack

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=1e5+5,maxm=1e5+5;
const LL INF=1e9;
LL T;
LL n,m,k;
map<string,int> hsh;
string S1,S2;
struct data{
	LL x,y,w;
	bool operator <(data b)const{return w<b.w;}
}A[maxm],B[maxm];
LL m1,m2;
LL fa[maxn];
LL getfa(LL x){
	return fa[x]==x?x:fa[x]=getfa(fa[x]);
}
LL check(LL w){
	LL tot=0;
	for(LL i=1;i<=n;i++) fa[i]=i;
	for(LL i=1,j=1;i<=m1||j<=m2;){
		if(i<=m1&&(j>m2||A[i].w+w<B[j].w)){
			LL x=A[i].x,y=A[i].y;
			LL fx=getfa(x),fy=getfa(y);
			i++;
			if(fx==fy) continue;
			fa[fx]=fy;
			tot++;
		}
		else{
			LL x=B[j].x,y=B[j].y;
			LL fx=getfa(x),fy=getfa(y);
			j++;
			if(fx==fy) continue;
			fa[fx]=fy;
		}
	}
	return tot;
}
void work(){
	LL ans=INF;
	scanf("%lld",&m);
	hsh.clear();
	hsh["Park"]=n=1;
	m1=m2=0;
	for(LL i=1,x,y,w;i<=m;i++){
		cin>>S1>>S2>>w;
		if(!hsh[S1]) hsh[S1]=++n;
		if(!hsh[S2]) hsh[S2]=++n;
		x=hsh[S1],y=hsh[S2];
		if(x>y) swap(x,y);
		if(x==1) A[++m1]=(data){x,y,w};
		else B[++m2]=(data){x,y,w};
	}
	scanf("%lld",&k);
	sort(A+1,A+1+m1);
	sort(B+1,B+1+m2);
	for(LL p=1;p<=k;p++){
		LL L=-INF,R=INF,mid;
		while(L<=R){
			mid=L+R>>1;
			LL now=check(mid);
			if(now==p) break;else
			if(now>p) L=mid+1;
			else R=mid-1;
		}
		LL now=0;
		for(LL i=1;i<=n;i++) fa[i]=i;
		for(LL i=1,j=1,cnt=1;cnt<n&&(i<=m1||j<=m2);){
			if(i<=m1&&(j>m2||A[i].w+mid<B[j].w)){
				int x=A[i].x,y=A[i].y;
				int fx=getfa(x),fy=getfa(y);
				i++;
				if(fx==fy) continue;
				fa[fx]=fy;
				now+=A[i-1].w;
				cnt++;
			}
			else{
				LL x=B[j].x,y=B[j].y;
				LL fx=getfa(x),fy=getfa(y);
				j++;
				if(fx==fy) continue;
				fa[fx]=fy;
				now+=B[j-1].w;
				cnt++;
			}
		}
		ans=min(ans,now);
	}
	
	printf("Total miles driven: %lld\n",ans);
}
int main(){
	freopen("UVA1537.in","r",stdin);
	freopen("UVA1537.out","w",stdout);
	scanf("%lld",&T);
	while(T--){
		work();
		if(T) putchar(10);
	}
	return 0;
}