CF1174F Ehab and the Big Finale 题解

题意：

这是一道交互题。

你有一棵 $n$ 个节点的有根树，$1$ 号点是根节点。这棵树中有一个隐藏的节点 $x$ ，你需要通过询问把 $x$ 找出来。你可以进行如下两种询问：

1、$d$ $u$ $(1\le u\le n)$。交互库会返回节点 $u$ 和 $x$ 的距离。

2、$s$ $u$ $(1\le u\le n)$。交互库会返回从 $u$ 到 $x$ 的路径上第二个点的标号。注意，你询问的 $u$ 必须是 $x$ 的祖先，否则会 Wrong Ans。

你需要在不超过 $36$ 次询问之内找出 $x$ 。$x$ 是预先设定好的，不会随着询问而改变。

输入格式：

The first line contains the integer $n ( 2 \le n \le 2 \cdot 10^5)$ — the number of nodes in the tree.

Each of the next $n-1$ lines contains two space-separated integers $u$ and $v~( 1 \le u,v \le n)$ that mean there’s an edge between nodes $u$ and $v$ . It’s guaranteed that the given graph is a tree.

输出格式：

Replace the formula $x$ in the following text with the actual value of $x$:

To print the answer, print ! x (without quotes).

Interaction

To ask a question, print it in one of the formats above:

$d$ $u~(1 \le u \le n)$ , or

$s$ $u~(1 \le u \le n)$ .

After each question, you should read the answer: either the distance or the second vertex on the path, as mentioned in the legend.

If we answer with $-1$ instead of a valid answer, that means you exceeded the number of queries, made an invalid query, or violated the condition in the second type of queries. Exit immediately after receiving $-1$ and you will see Wrong answer verdict. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing a query, do not forget to output end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

fflush(stdout) or cout.flush() in C++;

System.out.flush() in Java;

flush(output) in Pascal;

stdout.flush() in Python;

See the documentation for other languages.

Hacks:

The first line should contain two integers $n$ and $x~(2 \le n \le 2 \cdot 10^5,~1 \le x \le n)$.

Each of the next $n-1$ lines should contain two integers $u$ and $v ~(1 \le u,v \le n)$ that mean there is an edge between nodes $u$ and $v$. The edges must form a tree.

树上 log 级的询问，并且树是固定的，容易想到树剖，从跳重链的方向入手。

首先我们需要知道点 $x$ 的深度，依次考虑每条重链。记重链的底部为 $v_i$ ，$u_i = \mathrm{LCA}(v_i,x)$

如果 $x$ 和 $u_i$ 深度相同，则 $u_i$ 即为 $x$
反之 $x$ 一定位于 $u_i$ 某条轻边连出去的子树中。找到这个子树很简单，使用 s 询问即可。

容易发现，询问次数不超过 $2 \log n$ 。时间复杂度 $\mathcal{O}(n \log n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(2e5 + 15))

vector<int> vec[N];
int n,depx,pos=1,head[N],sz[N],dep[N],son[N];
struct Edge { int u,v,next; } e[N * 2];
void addEdge(int u,int v) { e[++pos] = {u,v,head[u]}; head[u] = pos; }
int ask(char type,int node) {
    cout << type << ' ' << node << endl;
    cin >> node; return node;
}
void dfs_pre(int u,int f)
{
    sz[u] = 1; int mx = -1;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].v; if(v == f) continue; dep[v] = dep[u] + 1;
        dfs_pre(v,u); sz[u] += sz[v]; if(sz[v] > mx) { mx = sz[v]; son[u] = v; }
    }
    if(son[u]) { swap(vec[u], vec[son[u]]); } vec[u].push_back(u);
}
int dfs(int u)
{
    int cnt = vec[u].size() - 1, D = depx - dep[u], dis = ask('d', vec[u].back());
    int i = (cnt + D - dis) / 2, y = vec[u][i];
    return dep[y] == depx ? y : dfs(ask('s', y));
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i = 1, u,v; i < n; i++) {
        cin >> u >> v; addEdge(u,v); addEdge(v,u);
    }
    depx = ask('d', 1); dfs_pre(1,0);
    for(int i = 1; i <= n; i++) if(!vec[i].empty()) {
        reverse(vec[i].begin(), vec[i].end());
    }
    cout << '!' << ' ' << dfs(1) << endl;
    return 0;
}