CF E1 ILE 求助
  • 板块学术版
  • 楼主sbno333
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/21 02:02
  • 上次更新2024/7/21 09:36:55
查看原帖
CF E1 ILE 求助
416975
sbno333楼主2024/7/21 02:02

rt,不知道为什么 ILE,能不能帮忙指出 ILE?感谢!

#include<bits/stdc++.h>
using namespace std;
#define int long long
struct st{
	int v,ne;
}sd[10009];
int inn;
int fa[10009];
int h[10009];
int gg;
void add(int u,int v){
	sd[++inn].v=v;
	sd[inn].ne=h[u];
	h[u]=inn;
}
bool que(int t){
	cout<<"? "<<t<<endl;
	cout.flush();
	bool s;
	cin>>s;
	cout.flush();
	if(!s){
		gg++;
	}
	return s;
}
void dfs(int t){
	for(int i=h[t];i;i=sd[i].ne){
		if(sd[i].v!=fa[t]){
			fa[sd[i].v]=t;
			dfs(sd[i].v);
		}
	}
}
int bj(int t){
	int ans;
	ans=0;
	for(int i=h[t];i;i=sd[i].ne){
		if(sd[i].v!=fa[t]){
			ans=max(bj(sd[i].v)+1,ans);
		}
	}
	return ans;
}
int z[1000009];
int jnn;
void ddfs(int t,int s){
	if(s==0){
		z[++jnn]=t;
		return;
	}
	for(int i=h[t];i;i=sd[i].ne){
		if(sd[i].v!=fa[t]){
			ddfs(sd[i].v,s-1);
		}
	}
}bool fl;
void did(int t){
	int s;
	s=bj(t);int zz;zz=s;
	if(s==0){
		cout<<"! "<<t<<endl;
		cout.flush();
		fl=1;
		return;
	}
	jnn=0;
	s=(1ll<<__lg(s));
	ddfs(t,s);
	for(int i=1;i<=min(jnn,zz-gg+5);i++){
		if(que(z[i])){
			did(z[i]);
			if(fl){
				return;
			}
			s/=2;
			jnn=0;
			ddfs(t,s);
			i=0;
		}else{
			if(que(t)){
				continue;
			}else{
				cout<<"!"<<" "<<fa[fa[t]]<<endl;
				cout.flush();
				fl=1;
				return;
			}
		}
	}
}
void _main(){
	memset(sd,0,sizeof(sd));
	inn=0;
	memset(fa,0,sizeof(fa));
	memset(h,0,sizeof(h));
	int n;
	cin>>n;
	fl=0;
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		add(u,v),add(v,u);
	}
	dfs(1);
	did(1);
	if(!fl){
		cout<<"! 1"<<endl;
		cout.flush();
	}
}
signed main(){
	int t;
	cin>>t;
	while(t--){
		_main();
	}
	return 0;
}
2024/7/21 02:02
加载中...