콘텐츠로 이동

최소 공통 조상 - $O(N)$ 전처리로 $O(\sqrt{N})$과 $O(\log N)$

트리 $G$가 주어집니다. $(v_1, v_2)$ 형태의 쿼리가 주어질 때, 각 쿼리마다 최소 공통 조상(lowest common ancestor 또는 least common ancestor)을 찾아야 합니다. 즉, 루트에서 $v_1$로 가는 경로와 루트에서 $v_2$로 가는 경로 위에 모두 놓여 있으면서 가장 낮은 정점 $v$를 찾아야 합니다. 다시 말해, 구하려는 정점 $v$는 $v_1$과 $v_2$의 조상 중 가장 아래에 있는 조상입니다. 두 정점의 최소 공통 조상이 $v_1$과 $v_2$ 사이의 최단 경로 위에 놓여 있다는 것은 자명합니다. 또한 $v_1$이 $v_2$의 조상이라면 $v_1$이 두 정점의 최소 공통 조상입니다.

알고리즘의 아이디어

쿼리에 답하기 전에 트리를 전처리해야 합니다. 루트에서 시작하여 DFS로 순회하면서, 방문하는 정점의 순서를 저장하는 리스트 $\text{euler}$를 만듭니다(정점은 처음 방문할 때, 그리고 각 자식에 대한 DFS 순회에서 돌아온 후에 리스트에 추가됩니다). 이를 트리의 오일러 투어(Euler tour)라고도 합니다. 이 리스트의 크기가 $O(N)$이라는 것은 분명합니다. 또한 각 정점 $i$에 대해 $\text{euler}$에서 처음 등장하는 위치를 저장하는 배열 $\text{first}[0..N-1]$도 만들어야 합니다. 즉, $\text{euler}[\text{first}[i]] = i$를 만족하는 $\text{euler}$ 내의 첫 번째 위치입니다. 또한 DFS를 이용하면 각 노드의 높이(루트로부터의 거리)를 구하여 배열 $\text{height}[0..N-1]$에 저장할 수 있습니다.

그렇다면 오일러 투어와 추가로 만든 두 배열을 이용하여 어떻게 쿼리에 답할 수 있겠습니까? 쿼리가 $v_1$과 $v_2$의 쌍이라고 가정합시다. 오일러 투어에서 $v_1$을 처음 방문한 시점과 $v_2$를 처음 방문한 시점 사이에 방문하는 정점들을 생각해 봅시다. $\text{LCA}(v_1, v_2)$가 이 경로에서 높이가 가장 낮은 정점이라는 것은 쉽게 알 수 있습니다. 앞서 LCA가 $v_1$과 $v_2$ 사이의 최단 경로의 일부여야 한다는 것을 확인했습니다. 분명히 LCA는 높이가 가장 작은 정점이어야 합니다. 그리고 오일러 투어는 본질적으로 최단 경로를 따라가되, 경로 위에서 만나는 모든 서브트리를 추가로 방문한다는 점만 다릅니다. 그러나 이 서브트리들에 속한 모든 정점은 트리에서 LCA보다 아래에 있으므로 높이가 더 큽니다. 따라서 $\text{LCA}(v_1, v_2)$는 오일러 투어에서 $\text{first}(v_1)$과 $\text{first}(v_2)$ 사이에 있는 정점 중 높이가 가장 작은 정점을 찾음으로써 유일하게 결정할 수 있습니다.

이 아이디어를 예시로 살펴봅시다. 다음 그래프와, 대응하는 높이가 함께 표시된 오일러 투어를 생각해 봅시다:

LCA_Euler_Tour
$$\begin{array}{|l|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline \text{Vertices:} & 1 & 2 & 5 & 2 & 6 & 2 & 1 & 3 & 1 & 4 & 7 & 4 & 1 \\ \hline \text{Heights:} & 1 & 2 & 3 & 2 & 3 & 2 & 1 & 2 & 1 & 2 & 3 & 2 & 1 \\ \hline \end{array}$$

정점 $6$에서 시작하여 $4$에서 끝나는 투어에서는 정점 $[6, 2, 1, 3, 1, 4]$를 방문합니다. 이 정점들 중 정점 $1$의 높이가 가장 낮으므로 $\text{LCA(6, 4) = 1}$입니다.

정리하면, 쿼리에 답하려면 배열 $\text{euler}$에서 $\text{first}[v_1]$부터 $\text{first}[v_2]$까지의 범위에서 높이가 가장 작은 정점을 찾기만 하면 됩니다. 따라서 LCA 문제는 RMQ 문제로 환원됩니다(구간에서 최솟값을 찾는 문제).

제곱근 분할법을 사용하면 $O(N)$ 시간의 전처리로 각 쿼리에 $O(\sqrt{N})$에 답하는 풀이를 얻을 수 있습니다.

세그먼트 트리를 사용하면 $O(N)$ 시간의 전처리로 각 쿼리에 $O(\log N)$에 답할 수 있습니다.

저장된 값이 갱신되는 경우는 거의 없으므로 희소 테이블이 더 나은 선택일 수 있습니다. 희소 테이블을 사용하면 $O(N\log N)$의 구축 시간으로 쿼리에 $O(1)$에 답할 수 있습니다.

구현

다음 LCA 알고리즘 구현에서는 세그먼트 트리를 사용합니다.

struct LCA {
    vector<int> height, euler, first, segtree;
    vector<bool> visited;
    int n;

    LCA(vector<vector<int>> &adj, int root = 0) {
        n = adj.size();
        height.resize(n);
        first.resize(n);
        euler.reserve(n * 2);
        visited.assign(n, false);
        dfs(adj, root);
        int m = euler.size();
        segtree.resize(m * 4);
        build(1, 0, m - 1);
    }

    void dfs(vector<vector<int>> &adj, int node, int h = 0) {
        visited[node] = true;
        height[node] = h;
        first[node] = euler.size();
        euler.push_back(node);
        for (auto to : adj[node]) {
            if (!visited[to]) {
                dfs(adj, to, h + 1);
                euler.push_back(node);
            }
        }
    }

    void build(int node, int b, int e) {
        if (b == e) {
            segtree[node] = euler[b];
        } else {
            int mid = (b + e) / 2;
            build(node << 1, b, mid);
            build(node << 1 | 1, mid + 1, e);
            int l = segtree[node << 1], r = segtree[node << 1 | 1];
            segtree[node] = (height[l] < height[r]) ? l : r;
        }
    }

    int query(int node, int b, int e, int L, int R) {
        if (b > R || e < L)
            return -1;
        if (b >= L && e <= R)
            return segtree[node];
        int mid = (b + e) >> 1;

        int left = query(node << 1, b, mid, L, R);
        int right = query(node << 1 | 1, mid + 1, e, L, R);
        if (left == -1) return right;
        if (right == -1) return left;
        return height[left] < height[right] ? left : right;
    }

    int lca(int u, int v) {
        int left = first[u], right = first[v];
        if (left > right)
            swap(left, right);
        return query(1, 0, euler.size() - 1, left, right);
    }
};

연습 문제