[国家集训队]Tree I

CXXXVII.[国家集训队]Tree I

两年前刚学MST时做这题WA了，然后两年后才把它补上……

明显直接wqs二分就行了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,q,dsu[50100],ip;
int read(){
	int x=0;
	char c=getchar();
	while(c>'9'||c<'0')c=getchar();
	while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+(c^48),c=getchar();
	return x;
}
struct dat{
	int u,v,w,c;
	void READ(){u=read()+1,v=read()+1,w=read(),c=!read();}
	int calc()const{return c?ip+w:w;}
	friend bool operator<(const dat&u,const dat&v){return u.calc()==v.calc()?u.c<v.c:u.calc()<v.calc();}
}p[100100];
vector<dat>v[2];
int find(int x){return dsu[x]==x?x:dsu[x]=find(dsu[x]);}
bool merge(int x,int y){x=find(x),y=find(y);if(x==y)return false;dsu[x]=y;return true;}
int che(){
//	printf("%lld:\n",ip);
	for(int i=0,j=0;i<v[0].size()||j<v[1].size();)if(i!=v[0].size()&&(j==v[1].size()||v[0][i]<v[1][j]))p[i+j+1]=v[0][i],i++;else p[i+j+1]=v[1][j],j++;
	int f=0,F=0;
	for(int i=1;i<=n;i++)dsu[i]=i;
	for(int i=1,j=1;i<=m;i=j){
		while(j<=m&&p[i].calc()==p[j].calc())j++;
		for(int k=i;k<j;k++)if(merge(p[k].u,p[k].v))f+=p[k].calc(),F+=p[k].c;
	}
	
	int g=0,G=0;
	for(int i=1;i<=n;i++)dsu[i]=i;
	for(int i=1,j=1;i<=m;i=j){
		while(j<=m&&p[i].calc()==p[j].calc())j++;
		for(int k=j-1;k>=i;k--)if(merge(p[k].u,p[k].v))g+=p[k].calc(),G+=p[k].c;
	}
	if(F>q)return 1;
	if(G<q)return -1;
	printf("%d\n",f-ip*q);
	return 0;
}
int main(){
//	freopen("P2619_10.in","r",stdin);
	n=read(),m=read(),q=read();
	for(int i=1;i<=m;i++)p[i].READ(),v[p[i].c].push_back(p[i]);
	for(int i=0;i<2;i++)sort(v[i].begin(),v[i].end());
	int l=-100,r=100;
	while(true){
		ip=(l+r)>>1;
		int tp=che();
		if(tp==-1)r=ip-1;
		if(tp==1)l=ip+1;
		if(!tp)return 0;
	}
	return 0;
}