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;
}