750F - New Year and Finding Roots - CodeForces Solution

#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<vector>
std::vector<std::vector<int>>buc;
std::vector<int>my_query(const int x){
	if(!buc[x].empty())return buc[x];
	std::cout<<'?'<<' '<<x<<'\n';
	std::cout.flush();
	int k;
	std::cin>>k;
	if(!k)exit(0);
	buc[x].resize(k);
	for(int i=0;i<k;i++)std::cin>>buc[x][i];
	return buc[x];
}
void answer(const int x){
	std::cout<<'!'<<' '<<x<<'\n';
	std::cout.flush();
}
int find_leaf(int u,int from,std::vector<int>&ans){
	ans.emplace_back(u);
	for(bool flag=true;flag;){
		flag=false;
		std::vector<int>_u=my_query(u);
		if((int)_u.size()==2)return u;
		for(int v:_u)
			if(v!=from){
				from=u,u=v;
				ans.emplace_back(u);
				flag=true;
				break;
			}
	}
	return 0;
}
void solve(const int h){
	int tmp;
	buc.clear();
	buc.resize(1<<h);
	int lim=1<<h,a,b;
	for(int i=1,cur;i<h;i++){
		cur=i*(i+1)/2+(1<<(h-i))-2;
		if(lim>cur)lim=cur,a=i,b=h-i;
	}
	int x=1;
	my_query(x);
	if((int)buc[x].size()==2)return answer(x);
	std::vector<int>chain;
	if((tmp=find_leaf(buc[x][0],x,chain)))return answer(tmp);
	std::reverse(chain.begin(),chain.end());
	if((tmp=find_leaf(x,buc[x][0],chain)))return answer(tmp);
	while((int)chain.size()<2*a-1){
		const int _h=((int)chain.size()+1)>>1,y=chain[_h-2],z=chain[_h];
		chain.resize(_h);
		x=chain.back();
		if((tmp=find_leaf(buc[x][0]^buc[x][1]^buc[x][2]^y^z,x,chain)))return answer(tmp);
	}
	{
		const int _h=((int)chain.size()+1)>>1,y=chain[_h-2],z=chain[_h];
		chain.resize(_h);
		x=chain.back();
		std::vector<std::pair<int,int>>f,g;
		f.emplace_back(buc[x][0]^buc[x][1]^buc[x][2]^y^z,x);
		int cnt=(1<<(h-_h))-1;
		for(int i=1;i<h;i++){
			for(const std::pair<int,int>&p:f){
				const int u=p.first,from=p.second;
				if(!(--cnt)||(int)my_query(u).size()==2)return answer(u);
				for(int v:buc[u])
					if(v!=from)
						g.emplace_back(v,u);
			}
			std::swap(f,g),g.clear();
		}
	}
	return answer(-1);
}
int main(){
	int t;
	std::cin>>t;
	for(int i=1,h;i<=t;i++){
		std::cin>>h;
		solve(h);
	}
	return 0;
}