1.倍增法

import java.io.*;
import java.util.*;


public class Main{
    static class Reader{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer=new StringTokenizer("");
        String next() throws IOException {
            while(!tokenizer.hasMoreTokens()) {
                tokenizer=new StringTokenizer(br.readLine());
            }
            return tokenizer.nextToken();
        }
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    static int N=500010,M=2*N,n,m,s,idx;
    static int[]h=new int[N];
    static int[]e=new int[M];
    static int[]ne=new int[M];
    static int[]dep=new int[N];//dep[u]存储u节点的深度
    static int[][]fa=new int[N][20];//f[u][i]存储从u节点向上跳 2^i 层的祖先节点 因为最多只有50万个节点所以高度最高为50万 2^20=100万 可以包含


    static void add(int a,int b) {
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    static void dfs(int u,int father) {
        dep[u]=dep[father]+1;

        fa[u][0]=father;//向上跳一步就是它的父亲节点
        for (int i = 1; i <=19; i++) {
            fa[u][i]=fa[fa[u][i-1]][i-1];
        }
        for(int i=h[u];i!=-1;i=ne[i]) {
            int j=e[i];
            if(j!=father) dfs(j, u);
        }
    }
    static int lca(int u,int v) {
        if(dep[u]<dep[v]) {//要确保u的层数大于等于v 即u在v的下面 方便后面代码书写
            int t=u;
            u=v;
            v=t;
        }
        //先跳到同一层
        for (int i = 19; i >=0 ; i--)
            if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
        if(u==v) return v;
        //再跳到lca的下一层
        for (int i = 19; i >=0 ; i--)
            if(fa[u][i]!=fa[v][i]) {
                u=fa[u][i];
                v=fa[v][i];
            }
        //返回父节点
        return fa[u][0];
    }
    public static void main(String[] args) throws IOException {
        Arrays.fill(h, -1);
        Reader sc=new Reader();
        n=sc.nextInt();
        m=sc.nextInt();
        s=sc.nextInt();
        for (int i = 0; i < n-1; i++) {
            int a=sc.nextInt();
            int b=sc.nextInt();
            add(a, b);
            add(b, a);
        }
        dfs(s,0);
        for (int i = 0; i < m; i++) {
            int u=sc.nextInt();
            int v=sc.nextInt();
            System.out.println(lca(u, v));
        }
    }
}

1.tarjan算法

import java.io.*;
import java.util.*;

public class Main3 {

    static class Reader{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokenizer=new StringTokenizer("");
        String next() throws IOException {
            while (!tokenizer.hasMoreTokens()){
                tokenizer=new StringTokenizer(br.readLine());
            }
            return tokenizer.nextToken();
        }
        int nextInt() throws IOException {
            return Integer.parseInt(next());
        }
    }

    static class el{
        int u;
        int v;

        public el(int u, int v) {
            this.u = u;
            this.v = v;
        }
    }
    static int N=500010,n,m,s,idx;
    static int[]h=new int[N];
    static int[]e=new int[N];
    static int[]ne=new int[N];
    static int[]p=new int[N];
    static el[]query=new el[N];
    static boolean[]st=new boolean[N];
    static int[] ans=new int[N];
    static void add(int a,int b){
        e[idx]=b;
        ne[idx]=h[a];
        h[a]=idx++;
    }
    static int find(int x){
        if(x!=p[x]) p[x]=find(p[x]);
        return p[x];
    }
    static void tarjan(int u,int fa){//即深搜
        st[u]=true;//入u时标记u
        for (int i=h[u];i!=-1;i=ne[i]){
            int j = e[i];
            if(j==fa) continue;
            if(!st[j]){
                tarjan(j,u);
                p[j]=u;//回u时 j指向u
            }
        }
        //离u时 枚举lca
        for (int i = 0; i < m; i++) {
            if(u==query[i].u){
                if(st[query[i].v])ans[i]=find(query[i].v);
            }
            if(u==query[i].v){
                if(st[query[i].u])ans[i]=find(query[i].u);
            }
        }
    }

    public static void main(String[] args) throws IOException {
        Arrays.fill(h,-1);
        for (int i = 0; i < N; i++) {
            p[i]=i;
        }
        Reader sc=new Reader();
        n=sc.nextInt();
        m=sc.nextInt();
        s=sc.nextInt();
        for (int i = 0; i < n-1; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            add(a,b);
            add(b,a);
        }
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            query[i]=new el(u,v);
        }
        tarjan(s,-1);
        for (int i = 0; i < m; i++) {
            System.out.println(ans[i]);
        }
    }
}