1174F - Ehab and the Big Finale - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

const int N = 2e5+15;

vector<vector<int>> g (N);

int rootdist;

vector<bool> vis (N);
vector<int> rep (N), parc (N);
vector<int> sz (N);
vector<int> dep (N);

void calc_depth(int u, int p) {
  if (u != p)
    dep[u] = 1 + dep[p];
  for (int v : g[u]) if (v != p)
    calc_depth(v, u);
}

int calc_size(int u, int p) {
  sz[u] = 1;
  for (int v : g[u]) if (v != p && !vis[v])
    sz[u] += calc_size(v, u);
  return sz[u];
}

int find_centroid(int u, int p, int n) {
  for (int v : g[u]) if (v != p && !vis[v] && sz[v] > n/2)
    return find_centroid(v, u, n);
  return u;
}

void centroid_decompose(int u, int p) {
  calc_size(u, u);
  int c = find_centroid(u, u, sz[u]);
  vis[c] = 1; parc[c] = p;

  cout << "d " << c+1 << endl;
  int du; cin >> du;
  if (du == 0) { cout << "! " << c+1 << endl; return; }

  bool awayfromroot = du+dep[c] == rootdist;
  if (awayfromroot) {
    cout << "s " << c+1 << endl;
    int v; cin >> v; v--;
    centroid_decompose(v, c);
    return;
  }

  for (int v : g[c]) if (!vis[v] && dep[v] < dep[c])
    centroid_decompose(v, c);
}

int main() {
  cin.tie(0); ios_base::sync_with_stdio(0);
  int n; cin >> n;
  for (int i = 0; i < n-1; i++) {
    int u, v; cin >> u >> v; u--; v--;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  calc_depth(0, 0);
  cout << "d 1" << endl;
  cin >> rootdist;
  centroid_decompose(0, 0);
}