519测试

#include <iostream>
#include <vector>
using namespace std;
const int N = 5e5+10;
vector<int> e[N];
int fa[N][20], dep[N];  //f[i][j]; 从i点向上跳2的j次方的点
int num[N][20];//从i点向上跳2的j次方的点与i号点的距离
void dfs(int a, int p){//p是a节点的父节点
    dep[a] = dep[p] + 1;//深度·
    fa[a][0] = p;
   // num[a][0]=2;
    for(int i = 1; i < 20; i++)//通过递推 来求出st数组
    {
        fa[a][i] = fa[fa[a][i-1]][i-1];
       // num[a][i]=num[a][i-1]+num[fa[a][i-1]][i-1];
    } 
    for(int x : e[a])//遍历 vector
        if(x != p) dfs(x, a);
}
int lca(int a, int b){//log(10000000) =23
    if(dep[a] < dep[b]) swap(a, b);//先保证让a深度大于等于b的深度
    for(int i = 19; i >= 0; i--){//如果a点的深度不等于b点的深度 就让a点向上跳            
        if(dep[fa[a][i]] >= dep[b]) a = fa[a][i];
        //a的深度 17 b点的深度是 11
      // 17-11=6; 8 4 2 1
   }
    if(a == b) return a;//a点b点一样 随便返回一个都是最近公共祖先
    for(int i = 19; i >= 0; i--){
        if(fa[a][i] != fa[b][i]){
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];//直接返回最近公共祖先
}
int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n, m, s; cin >> n >> m >> s;
    n--;
    while(--n){
        int a, b; cin >> a >> b;
        e[a].push_back(b); e[b].push_back(a);//邻接表
    }
    dfs(s, 0);
    while(m--){
        int a, b; cin >> a >> b;
        cout << lca(a, b) << endl;
    }
    return 0;
}