Problem Link

题目大意

给定一张 $n$ 个点 $m$ 条边的无向图，交互器中每个点有一个 $[0,n)$ 的颜色。

每次交互时，你可以把若干个点染成 $[0,n]$ 中的任意颜色，交互器会告诉你新图中的同色连通块数量。

请在 $2750$ 次交互之内确定每个点的颜色。

数据范围：$n\le 250$。

思路分析

先从链入手。

将所有奇数下标的点全部染成某种颜色 $c$，如果此时得到的连通块数 $<n$，说明下标为偶数的点中有颜色为 $c$ 的，否则说明没有。

以此为依据二分，可以求出每个颜色为 $c$ 的点，对每种颜色进行此过程即可还原下标为偶数的点，对于下标为奇数的点也做一遍即可求解，操作次数 $2n+n\log n$。

然后考虑推广，我们可以对链上所有下标为计数的点一次性检验，那么在图上我们可以对一个独立集状物一次性检验。

具体来说，选定一个独立集 $S$，将 $\overline S$ 中的点染成 $c$，如果返回值小于 $|S|$ 加上 $\overline{S}$ 导出子图的连通块数，那么说明 $S$ 中存在颜色 $c$，可以 $n+|S|\log n$ 还原。

考虑进一步优化，观察我们用到了独立集的什么性质。

首先要求 $S$ 内部的连通块数量为 $S$，也即 $S$ 中没有同色点相连，那么我们可以将同色且相邻的点缩成一个连通块。

其次要求每个 $S$ 中的点都至少和一个 $\overline S$ 中的点相连，这样才能在一个点颜色为 $c$ 的时候减少连通块数量。

这是容易的，取出一棵生成树并黑白染色得到两个集合分别作为 $S$ 求解即可。

最终我们只要求出每个同色连通块即可，也就是本题 $50\%$ 分数的子任务。

这个不难，考虑增量法构造，依次加入每个点 $u$ 并求出已加入的点中哪些与其同色。

将 $u$ 的邻域和 $u$ 自己保留原先颜色，其他点染颜色 $n$，设保留原颜色的点集是 $V$ 那么 $u$ 的邻域中有与 $u$ 同色的点当且仅当实际同色连通块数小于 $|V|$ 加 $\overline V$ 导出子图中的连通块数量。

注意到每次二分实际上都减少了一个点（和其他点并成同色连通块，或确定一个连通块的颜色），那么我们在 $3n+n\log n$ 次询问内解决了此问题。

实际上由于元素数的不断减少，询问次数不超过 $3n+\sum_{i=1}^n\log_2i$，可以通过。

注意特判全部点颜色相同的 Corner Case。

时间复杂度 $\mathcal O(n^2\log n)$。

代码呈现

#include<bits/stdc++.h>
using namespace std;
int perform_experiment(vector<int>E);
const int MAXN=255;
vector <int> G[MAXN],E[MAXN],R[MAXN];
int n;
struct DSU {
	int dsu[MAXN];
	void init() { iota(dsu,dsu+n,0); }
	int find(int x) { return x^dsu[x]?dsu[x]=find(dsu[x]):x; }
	bool merge(int x,int y) {
		x=find(x),y=find(y),dsu[x]=y;
		return x^y;
	}
}	F,T;
int count(const vector<int>&V) {
	static bitset<MAXN> inq;
	inq.reset(),T.init();
	for(int i:V) inq.set(i);
	int s=V.size();
	for(int i:V) for(int j:G[i]) if(inq[j]) s-=T.merge(i,j);
	return s;
}
int col[MAXN];
void solve(vector<int> S) {
	for(int c=0;c<n;++c) {
		vector <int> X;
		while(S.size()) {
			auto chk=[&](int k) {
				vector <int> q(n,c),r;
				for(int i=0;i<=k;++i) for(int u:R[S[i]]) q[u]=-1;
				for(int i=0;i<n;++i) if(~q[i]) r.push_back(i);
				int z=perform_experiment(q);
				return z<count(r)+k+1;
			};
			int l=0,r=S.size()-2,x=S.size()-1;
			if(!chk(x)) {
				X.insert(X.end(),S.begin(),S.end());
				break;
			}
			while(l<=r) {
				int mid=(l+r)>>1;
				if(chk(mid)) x=mid,r=mid-1;
				else l=mid+1;
			}
			col[S[x]]=c;
			X.insert(X.end(),S.begin(),S.begin()+x);
			S.erase(S.begin(),S.begin()+x+1);
		}
		S.swap(X);
	}
}
vector<int> find_colours(int N,vector<int>X,vector<int>Y) {
	n=N,F.init();
	for(int i=0;i<(int)X.size();++i) G[X[i]].push_back(Y[i]),G[Y[i]].push_back(X[i]);
	for(int u=0;u<n;++u) {
		static bitset <MAXN> vis;
		vis.reset();
		vector <int> Ne,C;
		for(int v:G[u]) if(v<u&&!vis[F.find(v)]) {
			Ne.push_back(F.find(v)),vis.set(F.find(v));
		}
		while(Ne.size()) {
			auto chk=[&](int k) { //qry Ne[0,k]
				vector <int> q(n,n),r;
				vis.reset(),q[u]=-1;
				for(int i=0;i<=k;++i) vis.set(Ne[i]);
				for(int i=0;i<u;++i) if(vis[F.find(i)]) q[i]=-1;
				for(int i=0;i<n;++i) if(~q[i]) r.push_back(i);
				int z=perform_experiment(q);
				return count(r)+k+2>z;
			};
			int l=0,r=Ne.size()-2,x=Ne.size()-1;
			if(!chk(x)) break;
			while(l<=r) {
				int mid=(l+r)>>1;
				if(chk(mid)) x=mid,r=mid-1;
				else l=mid+1;
			}
			C.push_back(Ne[x]);
			Ne.erase(Ne.begin(),Ne.begin()+x+1);
		}
		for(int v:C) F.merge(u,v);
	}
	vector <int> bl(n);
	for(int i=0;i<n;++i) R[bl[i]=F.find(i)].push_back(i);
	F.init();
	for(int i=0;i<n;++i) for(int j:G[i]) if(F.merge(bl[i],bl[j])) {
		E[bl[i]].push_back(bl[j]),E[bl[j]].push_back(bl[i]);
	}
	vector <int> S[2];
	function<void(int,int,int)> dfs=[&](int u,int fz,int c) {
		S[c].push_back(u);
		for(int v:E[u]) if(v^fz) dfs(v,u,c^1);
	};
	dfs(bl[0],-1,0);
	if(S[1].empty()) {
		vector <int> q(n,-1);
		for(q[0]=0;q[0]<n;++q[0]) if(perform_experiment(q)==1) {
			return vector<int>(n,q[0]);
		}
	}
	solve(S[0]),solve(S[1]);
	vector <int> cols(n);
	for(int i=0;i<n;++i) cols[i]=col[bl[i]];
	return cols;
}