最近公共祖先 lca

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

public class Main {
    static int N = (int)1e5 + 5;
    static int[] depth;
    static int[][] fa; 	// father array
    static ArrayList<ArrayList<Integer>> es; // 树的链表表示

    static void dfs(int u){	// 由es更新fa
        for(int i = 0; fa[u][i] != 0; i++)
            fa[u][i + 1] = fa[fa[u][i]][i];
        for (int v : es.get(u)) {
            if (fa[u][0] == v)
                continue;
            depth[v] = depth[u] + 1;
            fa[v][0] = u;
            dfs(v);
        }
    }

    static int lca(int _x, int _y){ // 求lca
        if (depth[_x] < depth[_y])
            return lca(_y, _x);
        int x = _x, y = _y;
        int d = depth[x] - depth[y];
        for (int i = 16; i > -1; --i)
            if ((d & (1 << i)) != 0)
                x = fa[x][i];
        if (x == y)
            return x;
        for (int i = 16; i > -1; --i)
            if (fa[x][i] != fa[y][i]) {
                x = fa[x][i];
                y = fa[y][i];
            }
        return fa[x][0];
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int T = in.nextInt();
        ArrayList<String> res = new ArrayList<>();
        while (T-- > 0){
            depth = new int[N];
            fa = new int[N][20];
            es = new ArrayList<>(N);

            int n = in.nextInt();
            int m = in.nextInt();

            for(int i = 0; i <= n; i++){
                es.add(new ArrayList());
            }

            for(int i = 1; i < n; i++){
                int u = in.nextInt();
                int v = in.nextInt();
                es.get(u).add(v);
                es.get(v).add(u);
            }
            depth[1] = 0;
            dfs(1);

            while (m-- != 0){
                int u = in.nextInt();
                int v = in.nextInt();
                
                int t1 = lca(u, v);
            }
        }
    }
}