10分求助

#include <cmath>
#include <iostream>
#include <vector>

using namespace std;

const int MaxN = 500010, MaxK = 20;

int n, m, s;
int f[MaxN][MaxK], d[MaxN];
vector<int> g[MaxN];

int Q(int u, int k) {
  for (int i = 0; i < MaxK; i++) {
    if (k & (1 << i)) {
      u = f[u][i];
    }
  }
  return u;
}

void DFS(int u, int fa, int cnt) {
  f[u][0] = fa;
  for (int i = 1; i < MaxK; i++) {
    f[u][i] = f[f[u][i - 1]][i - 1]; 
  }
  d[u] = cnt;
  for (int i : g[u]) {
    if (i == fa) continue;
    DFS(i, u, cnt + 1);
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> m >> s;
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  DFS(s, s, 1);
  for (int x, y; m; m--) {
    cin >> x >> y;
    int md = min(d[x], d[y]);
    x = Q(x, d[x] - md), y = Q(y, d[y] - md);
    for (int i = 0; i < MaxK; i++) {
      if (x != y) {
        x = f[x][i], y = f[y][i];
      } 
    }
    cout << x << '\n';
  }
  return 0;
}