最小共通祖先(LCA)

クイック反復二乗

最小共通祖先

リファレンス

• 
  

  最小共通祖先(LCA)

  
  
  • ツリー内の2つのノードを含む2つのノードは、祖先に沿って遡ったときに最初に共通して遭遇した頂点です.
  
  

<下図5と8のLCAが1です.>

• 
  

  最初に考える方法は、互いに出会うまで親ノードに沿って2つのノードを移動することである.

  
  
  • の2つのノードの高さが異なる場合、高さを調整して1つずつ上を見ると、ツリーの深さがHの場合、ツリーの深さはO(H)となり、最悪の場合はO(N)の時間となる.
  
  

  

  
  
  
  

LCA binary lifting

• 
  

  より速く、より効率的な方法はありますか?

  
  
  • 
    

    DP配列を用いてO(logn)時間内に
    

  • 
    

    2つのノードの15番目の祖先が異なる場合、1、2、3......15回の比較を1回ずつしないで、1回に15回直接スキップします.

    
    
    
    これはすべてのノードの
    • 第2^K祖先を記録した後に探した考えである.
    
    

    

    
    
  
  

• 
  

  DFSを使用してツリーを巡回し、すべての頂点のDepthを記録します.(2つのノードの高さが異なる場合は整列する必要があるため)

  
  
  • DP配列A[V][K]には、V番頂点の2^K個の親頂点番号が記録されている.
  
  
  • 
    

    A[V][0]は、Vノードの親ノード、すなわち最初の祖先である.このセクションはDFSを迂回して保存されます.

    
    
  • 
    

    A[V][K] = A[A[V][K-1]] [K-1].

    
    
    • 家の前に両親がいるから
      
    
    
  
  

• 
  

  このDPアレイを充填する場合、Kのループを外部に引き出す必要がある.理由は以下の通りである:

  
  
  • 
    

    Kリングが内側にある場合、

    
    

    A[1][1] = A[A[1][0]] [0];

    
    

    A[1][2] = A[A[1][1]] [1];

    
    

    A[1][3] = A[A[1][2]] [2];

    
    
  
  

• 
  

  このように充填するとA[1][1]の値が得られるが,A[A[1][1]] [1]の値はまだ知られていない.A[A[1][1]] [0]の値はDFSによって知られている.

  
  
  • 
    

    だから、祖先を2^0祖先に埋め、2^1祖先を埋め......これにより、すべての配列値が正しく求められます.

    
    

    A[2][1] = A[A[2][0]] [0];

    
    

    A[3][1] = A[A[3][0]] [0];

    
    
  
  

インプリメンテーション

• 
  

  X,YのLCAを求めるとLCA(X,Y)の実現は

  
  

  ①XとYの高さが等しい場合は、高さを1つずつ上げてみます.

  
  

  ②XとYの高さが異なる場合は、高さを調整します.

  
  同じ祖先を探す.p>
  

白駿

Python

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline
LENGTH = 21

n = int(input())
parent = [[0] * LENGTH for _ in range(n + 1)]
visited = [False] * (n + 1)
d = [0] * (n + 1)
graph = [[] for _ in range(n + 1)]

for _ in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)


def dfs(x, depth):
    visited[x] = True
    d[x] = depth

    for node in graph[x]:
        if visited[node]:
            continue
        # 우선 바로 위에 있는 부모 정보만 갱신
        parent[node][0] = x
        dfs(node, depth + 1)


# 모든 노드의 전체 부모 관계 갱신하기
def set_parent():
    dfs(1, 0)
    for i in range(1, LENGTH):
        for j in range(1, n + 1):
            # 각 노드에 대해 2**i번째 부모 정보 갱신
            parent[j][i] = parent[parent[j][i - 1]][i - 1]


def lca(a, b):
    # 무조건 b의 깊이가 더 깊도록 설정
    if d[a] > d[b]:
        a, b = b, a

    # a와 b의 깊이가 동일해주도록 설정
    for i in range(LENGTH - 1, -1, -1):
        if d[b] - d[a] >= 2**i:
            b = parent[b][i]

    if a == b:
        return a

    # 올라가면서 공통 조상 찾기
    for i in range(LENGTH - 1, -1, -1):
        if parent[a][i] != parent[b][i]:
            a = parent[a][i]
            b = parent[b][i]

    return parent[a][0]


set_parent()

m = int(input())

for _ in range(m):
    a, b = map(int, input().split())
    print(lca(a, b))

C++

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int N, M;
int dep[100001];
int A[100001][21];
int visit[100001];
vector <int> edge[100001];
 
 
int LCA(int X, int Y) {
 
 
    if (dep[X] != dep[Y]) {
        if (dep[X] > dep[Y]) { swap(X, Y); } // x 가 작은 수 y 가 큰 수
 
        for (int i = 20; i >= 0; i--) {
            if (dep[Y]-dep[X] >= (1<<i)) {  // (1<<i) 가 높이이다.
                Y = A[Y][i];
            }
        }
    } // dept 를 같게 만들어줌.
 
    if (X == Y) return X;
    
 
    if (Y != X) {
        for (int i = 20; i >= 0; i--) {
            if (A[X][i] != A[Y][i]) {
                X = A[X][i];
                Y = A[Y][i];
            }
        }
    }
 
    return A[X][0]; // 최소 공통 조상 리턴
 
}
void dfs(int n, int d, int dad) {
 
    dep[n] = d;
    d++;
 
    for (int i = 0; i < edge[n].size(); i++) {
        if (dad == edge[n][i]) continue;
 
        A[edge[n][i]][0] = n;
        dfs(edge[n][i], d, n);
    }
}
 
int main() {
 
    scanf("%d", &N);
 
 
    for (int i = 0; i < N - 1; i++) {
        int a, b; scanf("%d %d", &a, &b);
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    //dep[1] = 0;
 
    A[1][0] = 0;
    dfs(1, 0, 0);
 
    
 
    for (int y = 1; y <= 20; y++) { //DP 배열 생성
        for (int x = 1; x <= N; x++) {
            A[x][y] = A[A[x][y - 1]][y - 1];
        }
    }
 
    
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int X, Y; scanf("%d %d", &X, &Y);
        printf("%d\n", LCA(X, Y));
    }
 
 
 
    return 0;
}