최소 공통 조상(LCA) — 트리에서 두 노드의 만남 지점

        1
       / \
      2   3
     / \   \
    4   5   6
   /
  7

LCA(7, 5) = 2   (7의 조상: 4, 2, 1 / 5의 조상: 2, 1 → 공통 중 가장 깊은 것: 2)
LCA(7, 6) = 1   (7의 조상: 4, 2, 1 / 6의 조상: 3, 1 → 공통: 1)
LCA(4, 5) = 2

// 나이브 LCA — O(N)
public int lcaNaive(int u, int v, int[] parent, int[] depth) {
    // 1. 깊이 맞추기
    while (depth[u] > depth[v]) u = parent[u];
    while (depth[v] > depth[u]) v = parent[v];

    // 2. 같은 노드가 될 때까지 올라가기
    while (u != v) {
        u = parent[u];
        v = parent[v];
    }
    return u;
}

parent[0][v] = v의 직접 부모
parent[k][v] = parent[k-1][parent[k-1][v]]  (2^k = 2^(k-1) + 2^(k-1))

public class LCA {
    private static final int LOG = 20; // log2(최대 정점 수)
    private int[][] parent;
    private int[] depth;
    private List<List<Integer>> tree;
    private int n;

    public LCA(List<List<Integer>> tree, int root, int n) {
        this.tree = tree;
        this.n = n;
        this.parent = new int[LOG][n];
        this.depth = new int[n];

        // DFS로 depth와 parent[0] 채우기
        Arrays.fill(depth, -1);
        dfs(root, -1, 0);

        // 희소 테이블 구성
        for (int k = 1; k < LOG; k++) {
            for (int v = 0; v < n; v++) {
                if (parent[k - 1][v] != -1) {
                    parent[k][v] = parent[k - 1][parent[k - 1][v]];
                } else {
                    parent[k][v] = -1;
                }
            }
        }
    }

    private void dfs(int u, int par, int d) {
        depth[u] = d;
        parent[0][u] = par;
        for (int v : tree.get(u)) {
            if (v != par) {
                dfs(v, u, d + 1);
            }
        }
    }

    public int query(int u, int v) {
        // 1. 깊이 맞추기 — 2^k 단위로 점프
        if (depth[u] < depth[v]) {
            int temp = u; u = v; v = temp;
        }

        int diff = depth[u] - depth[v];
        for (int k = 0; k < LOG; k++) {
            if (((diff >> k) & 1) == 1) {
                u = parent[k][u];
            }
        }

        // 2. 같으면 바로 반환
        if (u == v) return u;

        // 3. 동시에 올라가기 — 큰 점프부터
        for (int k = LOG - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u]; // 한 칸 위가 LCA
    }
}

트리:     1
        / \
       2   3
      / \
     4   5

오일러 투어: [1, 2, 4, 2, 5, 2, 1, 3, 1]
깊이:       [0, 1, 2, 1, 2, 1, 0, 1, 0]

public class EulerTourLCA {
    private int[] euler;      // 오일러 투어 순서
    private int[] eulerDepth; // 오일러 투어의 깊이
    private int[] firstPos;   // 각 노드가 처음 나타나는 위치
    private int idx;
    private int[][] sparse;   // RMQ 희소 테이블

    public void build(List<List<Integer>> tree, int root, int n) {
        euler = new int[2 * n];
        eulerDepth = new int[2 * n];
        firstPos = new int[n];
        Arrays.fill(firstPos, -1);
        idx = 0;

        dfs(tree, root, -1, 0);

        // 희소 테이블로 RMQ 전처리
        buildSparseTable();
    }

    private void dfs(List<List<Integer>> tree, int u, int par, int d) {
        euler[idx] = u;
        eulerDepth[idx] = d;
        if (firstPos[u] == -1) firstPos[u] = idx;
        idx++;

        for (int v : tree.get(u)) {
            if (v != par) {
                dfs(tree, v, u, d + 1);
                euler[idx] = u;
                eulerDepth[idx] = d;
                idx++;
            }
        }
    }

    public int query(int u, int v) {
        int l = Math.min(firstPos[u], firstPos[v]);
        int r = Math.max(firstPos[u], firstPos[v]);
        return rmq(l, r); // 깊이가 최소인 노드 반환
    }

    // 희소 테이블 RMQ 구현 (O(1) 쿼리)
    private void buildSparseTable() {
        int len = idx;
        int log = (int) (Math.log(len) / Math.log(2)) + 1;
        sparse = new int[log][len];

        for (int i = 0; i < len; i++) sparse[0][i] = i;

        for (int k = 1; k < log; k++) {
            for (int i = 0; i + (1 << k) <= len; i++) {
                int left = sparse[k - 1][i];
                int right = sparse[k - 1][i + (1 << (k - 1))];
                sparse[k][i] = eulerDepth[left] <= eulerDepth[right] ? left : right;
            }
        }
    }

    private int rmq(int l, int r) {
        int k = (int) (Math.log(r - l + 1) / Math.log(2));
        int left = sparse[k][l];
        int right = sparse[k][r - (1 << k) + 1];
        int minIdx = eulerDepth[left] <= eulerDepth[right] ? left : right;
        return euler[minIdx];
    }
}

# 두 브랜치의 공통 조상 커밋 찾기
git merge-base feature main

/home/user/project/src/main/java/Service.java
/home/user/project/src/test/java/ServiceTest.java
→ 공통 조상: /home/user/project/src