Codeforces #563 Div2 F. Ehab and the Big Finale

これは本番とっさに思いつけと言われると大変そう。
https://codeforces.com/contest/1174/problem/F

問題

木を成すN頂点の無向グラフが与えられる。
このうち当たりの頂点を当てるInteractive問題である。

以下のクエリを36回まで用いて、頂点を当てよ。

• 指定した頂点と、当たりの頂点の距離を返す。
• 指定した頂点から、当たりの頂点に向かうパスにおいて、指定した頂点の次の頂点を返す。

解法

頂点数が200000以下なので、2*logN回程度のアプローチを取ることが考えられる。
まず木を根付き木とみなしてDFSし、各頂点において、子のうち最も大きなSubTreeを求めておこう。
そのようなSubTreeに向かう辺を、Heavy Edgeと呼ぶことにする。
最初に根頂点から当たりまでの頂点への距離を求めておこう。

以降、現在の頂点を根頂点とし、以下の動作を繰り返す。
現在の頂点から、HeavyEdgeを辿って葉まで辿るパスにおいて、その中点に対し、前者のクエリを行う。
当たりの頂点の根からの頂点はわかっているので、クエリの結果を見れば当たりの点が中点のSubTree内にあるか、そうでないかわかる。
前者の場合は現在の頂点をその中点とし、後者の場合は距離からHeavyEdgeのどの点から分岐したかわかるので、分岐した点で後者のクエリを発行し、どのSubTreeに潜ればいいかを見ていこう。

いずれにしても点の候補を毎回半分以下に絞り込める。

int N;
vector<int> E[202020];
int D[202020];
int V[202020];
int G[202020];
int C[202020];
int TX;

int query(char C,int X) {
	cout<<C<<" "<<X<<endl;
	cin>>X;
	return X;
	
}

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

int dfs2(int cur) {
	int td=query('d',G[cur]);
	int dis=(TX-D[cur]+D[G[cur]]-D[cur]-td)/2;
	while(dis--) cur=C[cur];
	
	if(D[cur]==TX) return cur;
	return dfs2(query('s',cur));
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x].push_back(y);
		E[y].push_back(x);
	}
	dfs(1,1,0);
	TX=query('d',1);
	x=dfs2(1);
	cout<<"! "<<x<<endl;
}

まとめ

答えを聞いちゃうと簡単なんだけどね。