倍增LCA板子

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=5e5+10; 
int n,m,s,a,b;
vector<int> e[N];
int dep[N],fa[N][20];

void dfs(int u, int f){
  dep[u]=dep[f]+1;
  fa[u][0]=f;
  for(int i=1; i<=19; i++) 
    fa[u][i]=fa[fa[u][i-1]][i-1]; 
  for(int v : e[u])
    if(v!=f) dfs(v, u);
}
int lca(int u, int v){
  if(dep[u]<dep[v])swap(u, v);
  for(int i=19; ~i; i--)
    if(dep[fa[u][i]]>=dep[v])
      u=fa[u][i];
  if(u==v) return v;
  
  for(int i=19; ~i; i--)
    if(fa[u][i]!=fa[v][i])
      u=fa[u][i], v=fa[v][i];
  return fa[u][0];
}
int main(){
  scanf("%d%d%d", &n,&m,&s);
  for(int i=1; i<n; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b);
    e[b].push_back(a);
  }
  dfs(s, 0);
  while(m--){
    scanf("%d%d", &a, &b);
    printf("%d\n",lca(a, b));
  }
  return 0;
}

来自dx123