给定一个 $n$ 个点的有根树，其中 $1$ 号顶点为根。
在树中藏了一个点 $x$。为了找到它，你可以对交互库发出两种询问：
d u ($1 \leq u \leq n$)：询问顶点 $u$ 和顶点 $x$ 之间的距离 (边的条数)。
s u ($1 \leq u \leq n$)：你需要保证 $u$ 是 $x$ 的祖先节点。它会返回 $u$ 到 $x$ 的简单路径上，最靠近 $u$ (但不是 $u$) 的一个顶点。
你需要在不超过 $36$ 次询问内找到 $x$。保证隐藏的节点 $x$ 在询问的过程中是不变的。
第一行包含一个正整数 $n$ ($2 \leq n \leq 2 \times 10^5$)，表示树的点数。
接下来的 $n - 1$ 行，每行包含两个用空格隔开的整数 $u, v$ ($1 \leq u, v \leq n$)，表示顶点 $u, v$ 之间有一条边。
如果你需要进行询问，请输出 d u 或 s u，具体意义见题目描述。
当你已经找到隐藏的节点 $x$ 时，输出 ! x 并退出程序即可。
由于询问次数只有 $36$ 次 (大约是 $\log$ 级别)，那该怎么办呢？
由于这道题也是类似问距离的题目，因此和 [loj6669]Nauuo and Binary Tree 类似，考虑使用树链剖分。
由于树的形态是已知的，因此一开始可以直接进行树链剖分，并且可以通过一次询问得到点 $x$ 的深度 $dep_x$。
取一条包含根节点 $1$ 的重链，设重链底部的叶子为 $u$。和那道题类似，通过 "树上两点间的距离公式"，询问 $u$ 和 $x$ 的距离后即可得到 $u_l = LCA \left( u, x \right)$ 的深度，从而确定该点。
此时，分两种情况讨论：
如果 $u_l$ 和 $x$ 等深度，则说明顶点 $u_l$ 即为所求顶点。
反之，说明 $x$ 在 $u_l$ 的轻边所连向的某个子树中。
而这回的树并不是二叉树，一个点会有许多子节点，又该怎么处理呢？
其实这并不难，只需要使用一次操作 s 即可得到它所连向的子节点。
由轻重链剖分的性质，询问次数至多不超过 $O \left( \log n \right)$，总时间复杂度 $O \left( n \right)$。
#include <bits/stdc++.h>
#define EB emplace_back
using std::cin;
using std::cout;
using std::endl;
typedef std::vector <int> vector;
const int N = 200054, M = N * 2;
int n, E = 0, Dans;
int to[M], first[N], next[M];
int dep[N], size[N], prf[N];
vector chain[N];
inline int query(char type, int node) {return cout << type << ' ' << node << endl, cin >> node, node;}
inline void addedge(int u, int v) {
to[++E] = v, next[E] = first[u], first[u] = E;
to[++E] = u, next[E] = first[v], first[v] = E;
}
void dfs_pre(int x, int px = 0) {
int i, y, &z = prf[x]; size[x] = 1;
for (i = first[x]; i; i = next[i])
if ((y = to[i]) != px) {
dep[y] = dep[x] + 1, dfs_pre(y, x);
size[y] > size[z] ? z = y : 0;
size[x] += size[y];
}
if (z) std::swap(chain[x], chain[z]); chain[x].EB(x);
}
int dfs(int x) {
int cnt = chain[x].size() - 1, remain = Dans - dep[x], dist = query(100, chain[x].back());
int i = (cnt + remain - dist) / 2, y = chain[x][i];
return dep[y] == Dans ? y : dfs(query(115, y));
}
int main() {
int i, u, v;
std::ios::sync_with_stdio(false), cin.tie(NULL);
scanf("%d", &n);
for (i = 1; i < n; ++i) scanf("%d%d", &u, &v), addedge(u, v);
Dans = query(100, 1), dfs_pre(1);
for (i = 1; i <= n; ++i) if (!chain[i].empty()) std::reverse(chain[i].begin(), chain[i].end());
cout << '!' << ' ' << dfs(1) << endl;
return 0;
}
坑1：和那题类似，计算点 $x$ 的 "深度" 时还是要注意用原先的深度减去当前根的深度，即 $dep'_x = dep_x - dep_r$。