Codeforces #651 Div2 F2. The Hidden Pair (Hard Version)

意外とすんなり解けた。
https://codeforces.com/contest/1370/problem/F2

問題

N頂点の木が与えられる。
ここから、11回以内のクエリで2つの点S,Tを当てよ。

各クエリでは、任意個数の頂点を指定できる。
そうすると、その中でSまでの距離とTまでの距離の和が最小の点と、その合計距離を返す。

解法

まず全点を対象にクエリを実行すると、S-T間の距離と、S-Tパス上の点が手に入る。
この距離をDとし、現在わかっているパスの両端L-Rを考える。初期状態で、L-Rは初回クエリで返る点とする。

クエリでは、L-Rパスの外側で、LまたはRからの距離が(D-length(L,R))に一致する点を列挙しよう。
そうすると、LまたはRをSまたはT寄りに動かすことができる。
また、Dまでに足りない距離をクエリ毎に半減できるので、O(logN)回のクエリでL-RがS-Tに一致する。

int T;
int N;
vector<int> E[1010];
int D[1010][1010];

void dfs(int cur,int pre,int root,int d) {
	D[root][cur]=d;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,root,d+1);
}


pair<int,int> ask(vector<int> V) {
	cout<<"? "<<V.size();
	FORR(v,V) cout<<" "<<v;
	cout<<endl;
	int x,d;
	cin>>x>>d;
	return {x,d};
}

void ans(int a,int b) {
	if(a>b) swap(a,b);
	cout<<"! "<<a<<" "<<b<<endl;
	string s;
	cin>>s;
	assert(s=="Correct");
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		FOR(i,N) E[i+1].clear();
		FOR(i,N-1) {
			cin>>x>>y;
			E[x].push_back(y);
			E[y].push_back(x);
		}
		FOR(i,N) dfs(i+1,i+1,i+1,0);
		vector<int> V;
		FOR(i,N) V.push_back(i+1);
		auto p=ask(V);
		int L=p.first,R=p.first;
		int len=p.second;
		while(D[L][R]<len) {
			vector<int> V;
			cerr<<"!!"<<L<<" "<<R<<" "<<len<<" "<<D[L][R]<<endl;
			for(i=1;i<=N;i++) {
				if(D[L][i]==(len-D[L][R]+1)/2 && D[R][i]==D[L][R]+D[L][i]) {
					V.push_back(i);
				}
				else if(D[R][i]==(len-D[L][R]+1)/2 && D[L][i]==D[L][R]+D[R][i]) {
					V.push_back(i);
				}
			}
			p=ask(V);
			if(D[L][p.first]==D[L][R]+D[R][p.first]) R=p.first;
			else L=p.first;
			
		}
		ans(L,R);
		
	}
}

まとめ

この回はだいぶ簡単寄りだったね。