[CodeForces1174F] Ehab and the Big Finale(交互，思维，树链剖分)

发表于 | 分类于 ， | 评论数： | 阅读次数：

题目链接：https://codeforces.com/contest/1174/problem/F

题意：给一棵$n$个点的树，根节点为1。并且后台确定了一个点$x$，现在给你两种可以使用的查询操作：

  1. d $u$：后台会返回$u$和$x$的距离

  2. s $u​$：后台返回$u​$到$x​$的下一个点的id，如果$u​$不是$x​$的祖先会报错。

允许询问36次，让你确定$x$的序号。

首先可以肯定我们使用d $1$可以知道$x$的深度，记为$dep[x]$.

假设我们已知某点$v$，那么通过1操作我们可以知道$x$和$v$的距离$dis(x,v)$，如果我们预处理所有点的深度$dep[i]$，并且假设$LCA(x, v)=y$，那么我们可以知道：
$$
dep[y]=\dfrac{dep[x]+dep[v]-dis(x, v)}{2}
$$
于是我们可以用$v​$点往上找$dep[v]-dep[y]​$个点就能找到$y​$，可以用树链剖分：预处理每个点的子孙数，深度、重链的儿子，每次在重链上查询，于是查询的点$y​$就是点$u​$的重链上的第$dep[y] -dep[u]​$个孩子。于是每次拿查询到的$y​$作为根继续查它的重链，直到$y​$和$x​$在同一条链上，那么下一步查询$x​$和$y​$就会重合。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
 
using namespace std;
using pii = pair<int, int>;
using LL = long long;

const int maxn = 200200;
int n;
vector<int> G[maxn];
int sz[maxn], son[maxn], dep[maxn];
int dep_x;

int query(char c,int u) {
  int v;
  cout << c << " " << u << endl;
  fflush(stdout);
  cin >> v;
  return v;
}

int init(int u, int p) {
  int ret = 0;
  dep[u] = dep[p] + 1;
  for (const auto v : G[u]) {
    if (v == p) continue;
    ret += init(v, u);
    sz[u] += sz[v];
    if (son[u] == -1 || sz[v] > sz[son[u]]) {
      son[u] = v;
    }
  }
  return sz[u] = ret + 1;
}

vector<int> heavy;

void dfs(int u) {
  heavy.clear();
  int v = u;
  while (v != -1) {
    heavy.emplace_back(v);
    v = son[v];
  }
  v = *heavy.rbegin();
  int dis_xv = query('d', v);
  int dep_y = (dep_x + dep[v] - dis_xv) / 2;
  int y = heavy[dep[y] - dep[u]];
  if (dep_y == dep_x) {
    cout << "! " << y << endl;
    return;
  }
  dfs(query('s', y));
}

signed main() {
  // freopen("in", "r", stdin);
  int u, v;
  while (~scanf("%d", &n)) {
    for (int i = 1; i <= n; i++) {
      G[i].clear();
    }
    for (int i = 0; i < n - 1; i++) {
      cin >> u >> v;
      G[u].emplace_back(v);
      G[v].emplace_back(u);
    }
    memset(sz, 0, sizeof sz);
    memset(son, -1, sizeof son);
    memset(dep, -1, sizeof dep);
    dep_x = query('d', 1);
    if (dep_x == 0) {
      cout << "! 1" << endl;
      continue;
    }
    init(1, 0);
    dfs(1);
  }
  return 0;
}