题目链接：Codeforces 1174F

这是一道交互题。

给定一棵有 $n$ 个点的树，节点 $1$ 为根节点。

我们选择一个隐藏节点 $x$，你需要进行以下三种操作来找到这个节点 $x$ 的编号。

• d u：你会得到节点 $u$ 和 $x$ 之间的距离。两个节点之间的距离定义为最短路径上的边数。
• s u：你会得到节点 $u$ 到 $x$ 的最短路径上的第二个节点。但是如果 $u$ 不是 $x$ 的祖先，你会直接得到 Wrong answer 的结果！
• ! u：回答隐藏节点 $x$ 的编号为 $u$。

你需要在 $36$ 次询问（不包括回答）内找到 $x$ 的编号。这个隐藏节点 $x$ 不会根据你的询问而改变。

数据范围：$2 \le n \le 2 \times 10 ^ 5$。

Solution

为了找到点 $x$，我们不断缩小子树搜索范围。

设当前子树的根 $u$，考虑一条 $u$ 到子树内某个叶子节点 $v$ 的路径，那么 $x$ 一定在路径上从根节点开始的某些点的子树内。而满足条件的深度最大的节点一定是 $v$ 和 $x$ 的 $\text{LCA}$，设为 $y$。

我们可以询问得到 $\text{dist}(v, x)$ 即可求出 $y$ 的具体编号。

如果 $y$ 的深度等于 $x$，那么答案一定是 $y$；否则递归计算 $y$ 到 $x$ 路径上的第二个点。

由于树的形态是给定的，我们为了每次更大幅度地减小当前子树的 $\text{size}$，对原树进行树链剖分，显然路径 $u - v$ 应该是沿着重儿子查找下去的，这样路径上所有点均为父亲的重儿子，递归查找时子树的 $\text{size}$ 至少减半。

总询问次数不超过 $2 \left \lfloor \log_{2} n\right \rfloor$ 次。

时间复杂度：$\mathcal O(n)$

Code

#include <cstdio>
#include <vector>

const int N = 2e5 + 5, M = 4e5 + 5;

int n, tot, depx, lnk[N], ter[M], nxt[M], dep[N], siz[N], hvy[N];

int query(char opt, int v) {
    printf("%c %d\n", opt, v);
    fflush(stdout);
    int x;
    scanf("%d", &x);
    return x;
}
void addEdge(int u, int v) {
    ter[++tot] = v, nxt[tot] = lnk[u], lnk[u] = tot;
}
void dfs(int u, int p) {
    siz[u] = 1, hvy[u] = 0, dep[u] = dep[p] + 1;
    for (int i = lnk[u]; i; i = nxt[i]) {
        int v = ter[i];
        if (v == p) continue;
        dfs(v, u);
        siz[u] += siz[v];
        if (siz[v] > siz[hvy[u]]) hvy[u] = v;
    }
}
void getPath(int u, std::vector<int> &p) {
    p.emplace_back(u);
    if (hvy[u]) getPath(hvy[u], p);
}
int solve(int u) {
    std::vector<int> p;
    getPath(u, p);
    int v = p.back();
    int depy = (depx + dep[v] - query('d', v)) >> 1, y = p[depy - dep[u]];
    return (depx == depy ? y : solve(query('s', y)));
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i < n; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        addEdge(u, v), addEdge(v, u);
    }
    dfs(1, 0);
    depx = query('d', 1) + 1;
    printf("! %d\n", solve(1));
    fflush(stdout);
    return 0;
}