题目
https://codeforces.com/contest/1174/problem/F
题意
给你一个n个节点树，有一个未知的x点，让你有限次询问找到x
询问的方式有两种
1、d y 询问x点与y点之间的距离
2、s y 询问y点到x点的路径中y点的下一个点。
思路
https://dudulu.net/blog/?p=1696
代码
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i = (a);i <= (b);i++)
const int N = 2000005;
vector<int> q[N];
int vis[N],deep[N],siz[N],son[N];
int n;
int depx;
vector<int> qw;
void dfss(int u,int fa)
{siz[u] = 1;deep[u] = deep[fa] + 1;son[u] = -1;for(int i = 0;i < q[u].size();i++){int v = q[u][i];if(v == fa) continue;dfss(v,u);siz[u] += siz[v];if(son[u] == -1||siz[v] > siz[son[u]]){son[u] = v;}}
}
void dffs(int u)
{qw.clear();int p = u;while(p != -1){qw.push_back(p);p = son[p];}int v = qw.back();int outt;cout<<"d "<<v<<endl;cin>>outt;int depy = (depx+deep[v]-outt)/2;int y = qw[depy-deep[u]];if(deep[y] == depx){cout<<"! "<<y<<endl;return ;}int yy;cout<<"s "<<y<<endl;cin>>yy;dffs(yy);
}int main()
{ios::sync_with_stdio(false);int n;cin>>n;rep(i,1,n-1){int u,v;cin>>u>>v;q[u].push_back(v);q[v].push_back(u);}cout<<"d 1"<<endl;fflush(stdout);cin>>depx;if(depx == 0){cout<<"! 1"<<endl;return 0;}deep[0] = 0;dfss(1,0);dffs(1);return 0;
}