倍增算法 LCA AC30 求救！！！

#include <iostream>

using namespace std;

#define ll  long long
#define rll  register long long  // 数据始终存放在寄存器，避免读写内存

const int N = 5e5 + 5;

struct node {
  int to;
  int w;
  int next;
} edges[N << 1]; // 无向图要建立两条边
int head[N];

int depth[N];  // 每个顶点的深度数组
int fa[N][31]; // fa[i][j]表示顶点i的2^j祖先节点
int lg[N];     // lg[i] = (log2 i) + 1  lg[1] = 1 lg[2] = 2, lg[3] = 2  递推式 lg[i] = lg[i-1] + (1 << lg[i-1] == i)
               // 使用的时候要 -1

int cnt;

inline ll read() {
  ll x = 0;
  bool flag = false;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') {
      flag = true;
    }
    ch = getchar();
  }

  while ('0' <= ch && ch <= '9') {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }

  if (flag) {
    return ~(x - 1);
  }
  return x;
}

// 添加一条边
void add(ll u, ll v, ll w) {
  // cout << "add: " << u << ", " << v << endl;
  edges[++cnt].to = v;
  edges[cnt].w = w;
  edges[cnt].next = head[u];
  head[u] = cnt;
}

// 对树中的节点进行预处理，计算每个节点的深度，每个节点的第2^j祖先 
// 当前节点root, 其父节点fand
void dfs(int root, int fand) {
  fa[root][0] = fand; // 2^0 = 1, 第1级的祖先就是其父节点
  depth[root] = depth[fand] + 1;
  // 更新2^j祖先
  for (rll i=1; i<=lg[depth[root]]-1; i++) {
    fa[root][i] = fa[fa[root][i-1]][i-1];
  }
  // 递归处理孩子节点
  for (rll i=head[root]; i; i=edges[i].next) {
    if (edges[i].to != fand) {
      dfs(edges[i].to, root);
    }
  }
}

// 计算最近公共祖先，整体思路是通过倍增游走，将u,v搞到LCA的下一层
ll LCA(ll u, ll v) {
  // cout << "LCA: " << u << ", " << v << endl;
  if (depth[u] < depth[v]) {
    swap(u, v);
  }
  while (depth[u] > depth[v]) {
    u = fa[u][lg[depth[u]-depth[v]]-1];
  }
  if (u == v) return u;

  for (rll i=lg[depth[u]]-1; i>=0; i--) {
    if (fa[u][i] != fa[v][i]) {
      u = fa[u][i];
      v = fa[v][i];
    }
  }
  return fa[u][0];
}

int main() {
  // freopen("1.in", "r", stdin);
  ll n = read();
  ll m = read();
  ll s = read();

  for (rll i=1; i<n; i++) {
    ll u, v, w;
    u = read();
    v = read();
    w = 1;
    add(u, v, w), add(v, u, w);
  }

  for (rll i=1; i<31; i++) {
    lg[i] = lg[i-1] + (1 << lg[i-1] == i);
  }

  dfs(s, 0);

  for (rll i=1; i<=m; i++) {
    ll u, v;
    u = read();
    v = read();

    ll lca = LCA(u, v);
    printf("%lld\n", lca);
  }

  return 0;
}