题解：CF2133E I Yearned For The Mines

首先，对于每个节点，我们至少要查询一次，为了减少次数，那么就相当于每个节点都只查询一次，那么就相当于用

\frac{n}{4}

的操作对每个点进行染色，染色后的点与其他点的链接断开，考虑当前节点，如果当前节点的未染色子节点个数有三个或以上时，这个子节点一定要染色，如果当前未染色子节点的个数为两个，且当前节点没有被染色，那么就将它的父节点进行染色，这样可以保证操作次数不大于

\frac{n}{4}

，代码如下。

CPP

int e[MAXN],ne[MAXN],h[MAXN],idx;
void add(int a,int b){
	e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
//vector<int> nums;
int d[MAXN];
int vis[MAXN];
bool st[MAXN];
void dfs(int u,int f){
	int ans=0;
	for(int i=h[u];i!=-1;i=ne[i]){
		int v=e[i];
		if(v==f)continue;
		dfs(v,u);
		ans+=!st[v];
	}
	
	if(ans>=3)st[u]=1;//子儿子数大于3，必删除该点
	else if(!st[u]&&ans==2)st[f]=1;//删除父节点
	if(st[u]){
		for(int i=h[u];i!=-1;i=ne[i])
		d[e[i]]--;
	}
}

void dfs(int u){//查询链
	cout<<1<<" "<<u<<endl;
	vis[u]=1;
	for(int i=h[u];i!=-1;i=ne[i]){
		int v=e[i];
		if(st[v]||vis[v])continue;
		// debug();
		dfs(v);
	}
}
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		st[i]=0;
		d[i]=0;
		idx=0;
		h[i]=-1;
		vis[i]=0;
	}
	for(int i=1;i<n;i++){
		int a,b;
		cin>>a>>b;
		d[a]++;
		d[b]++;
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	int ans=0;
	for(int i=1;i<=n;i++)
	ans+=st[i];
	cout<<ans+n<<endl;
	for(int i=1;i<=n;i++)
	if(st[i])cout<<2<<" "<<i<<endl;
	for(int i=1;i<=n;i++)
	if(st[i])cout<<1<<" "<<i<<endl;
	else if(d[i]==1&&!vis[i])dfs(i);
	else if(d[i]==0)cout<<1<<" "<<i<<endl;
}
signed main(){
	// ios;
	int t=1;
	cin>>t;
	// cout<<fixed<<std::setprecision(15);
	while(t--)
	solve();
	return 0;
}

题解：CF2133E I Yearned For The Mines

文章操作

相关推荐

评论

题解：CF2133E I Yearned For The Mines