【分治+并查集】Codeforces 603E Pastoral Oddities

题面在这里

​

首先“所有点度数为奇数”这个条件太难验证了，需要转化一下

观察可得，当且仅当每个联通块的点数为偶数时，存在一个子图使得所有点的度数为奇数

证明比较简单，此处略

​

然后发现答案是不增的，这样我们就可以分治了：

\(solve(ql,qr,l,r)\)表示处理\([ql,qr]\)区间内的边和询问，答案区间为\([l,r]\)

如果我们得到了第\(mid\)个询问的答案\(ans[mid]\)，就可以分治\(solve(ql,mid-1,ans[mid],r),solve(mid+1,r,l,ans[mid])\)

注意这里权值为\(ans[mid]\)的边是两个子区间共用的，如果这样的边很多复杂度就不能保证

所以直接把边权排序后的编号作为边权

如何求\(ans[mid]\)？看下图：

横坐标为询问，纵坐标为边权

先加入DHYX内所有边，然后从小到大加入THGR，出现所有联通块都是偶数就得到了\(ans[mid]\)

用按秩合并并查集维护连通性和奇联通块个数，记得撤销加边

• 如果没有得到\(ans[mid]\)：
  • 加入DXYH内所有边
  • \(solve(mid+1,qr,l,r)\)
• 得到了\(ans[mid]\)：
  • 加入SEDT内所有边
  • \(solve(ql,mid-1,ans[mid],r)\)
  • 加入DXYH内所有边
  • \(solve(mid+1,qr,l,ans[mid])\)

总时间复杂度\(O(m\cdot log^2m)\)

​

示例程序：

#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=100005,maxe=300005;
int n,e,ans[maxe];
struct data{
	int x,y,w,id;
	data () {}
	data (int _x,int _y,int _w):x(_x),y(_y),w(_w) {}
	bool operator<(const data&b)const {return w<b.w;}
}a[maxe],b[maxe];
int fa[maxn],siz[maxn],dep[maxn],del[maxe],depp[maxe],X[maxe],Y[maxe],ji,len;
inline int getfa(int x) {return fa[x]==x?x:getfa(fa[x]);}
inline void merge(int x,int y){
	x=getfa(x);y=getfa(y);
	if (x==y) return;
	if (dep[x]<dep[y]) swap(x,y);
	++len;
	if ((siz[x]&1)&&(siz[y]&1)) del[len]=-2,ji-=2;
	 else del[len]=0;
	X[len]=x;Y[len]=y; depp[len]=dep[y];
	siz[x]+=siz[y];dep[x]=max(dep[x],dep[y]+1); fa[y]=x;
}
inline void undo(){
	ji-=del[len]; dep[X[len]]=depp[len];
	siz[X[len]]-=siz[Y[len]]; fa[Y[len]]=Y[len];
	len--;
}
void solve(int ql,int qr,int l,int r){
	if (ql>qr) return;
	int mid=ql+qr>>1,ans_mid=0;
	
	int t1=len;
	for (int i=ql;i<=mid;i++)
	 if (a[i].w<l) merge(a[i].x,a[i].y);
	for (int i=l;i<=r;i++){
		if (b[i].id<=mid) merge(b[i].x,b[i].y);
		if (ji==0) {ans_mid=i;break;}
	}
	
	while (len>t1) undo();
	if (!ans_mid){
		for (int i=ql;i<=mid;i++){
			ans[i]=-1;
			if (a[i].w<l) merge(a[i].x,a[i].y);
		}
		solve(mid+1,qr,l,r);
	}else{
		ans[mid]=b[ans_mid].w;
		for (int i=l;i<ans_mid;i++)
		 if (b[i].id<ql) merge(b[i].x,b[i].y);
		solve(ql,mid-1,ans_mid,r);
		while (len>t1) undo();
		for (int i=ql;i<=mid;i++)
		 if (a[i].w<l) merge(a[i].x,a[i].y);
		solve(mid+1,qr,l,ans_mid);
	}
	while (len>t1) undo();
}
int main(){
	scanf("%d%d",&n,&e);
	ji=n; for (int i=1;i<=n;i++) fa[i]=i,dep[i]=siz[i]=1;
	for (int i=1;i<=e;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].w),a[i].id=i,b[i]=a[i];
	sort(b+1,b+1+e);
	for (int i=1;i<=e;i++) a[b[i].id].w=i;
	solve(1,e,1,e);
	for (int i=1;i<=e;i++) printf("%d\n",ans[i]);
	return 0;
}