最小共通祖先LCA

質問する

https://www.acmicpc.net/problem/11438

概要

木の最小公的祖先はLowestCommon AncesterでLCAとされている.

例えば、上記の木では、
LCA(2, 3) = 1
LCA(6, 7) = 1
LCA(15,11)=11.

に答える

LCAを見つける方法はO(N)O(N)O(N)のみを近距離で見つける方法とO(logn)O(logn)O(logn)O(logn)のみを見つける方法がある.
もちろん,ノードの個数が多ければ多いほど,O(logn)O(logn)O(logn)O(logn)を用いる効率が高くなり,この方法を用いなければならない.
この文章のポイントは、O(logn)O(logn)O(logn)O(logn)のみを探す方法を説明するので、直線を探す方法を簡単に説明します.
LCAの近距離検索方法:
1.2つのノードの深さを同じにします.
2.同じ深さで直線的に親に乗って行く.
3.親ノード番号が同じで、その番号はLCAです.
次に、O(logn)O(logn)O(logn)O(logn)で検索する方法について説明します.
O(logN)O(logN)O(logN) [検索](Find)メソッドでは、2つのノードの深さは同じです.
しかし,線形法と異なり,深さを同じにするのはO(logn)O(logn)O(logn)O(logn)のみである.
たとえば、2つのノードの深度差を15とします.
15はバイナリ数字1111(2)である.したがって,1111(2)のどの位置に1が現れるかを把握し,1が現れる位置の値に応じてノードを移動すればよい.
この概念は15=1+2+4+8で表され,計算15の修行を4回で終える方法と同じである.
この処理を完了するにはSparse Tableが必要です.
Sparse Tableは行ごとにノード番号を表し、列ごとに2の指数を表す.
したがって、次の情報を含む2 Dテーブルを作成できます.
sparseTable[i][k]=i番ノードの2 k 2^k 2 kの2番目の親ノード
ex)sparseTable[i][0]=i番ノードの202^020番目の親ノード=i番ノードの最初の親ノード

Tip : 모든 자연수는 2의 거듭제곱으로 표현할 수 있다.
따라서 어떤 노드의 모든 n번째 부모 노드의 정보를 Sparse Table로 알아낼 수 있다.

回答の全体的な流れは次のとおりです.
1.値を入力してツリーを前処理します.
2.前処理の場合、dfs、bfsのどちらも構わない.ただし、現在のノードの親ノードをsparseTable[node][0]に保存して動作する.
3.ツリー内のノードの深さをdepth[node]に保存して行います.
4.SparseTable[n][k]=sparseTable[n][k-1][k-1]を使用してSparseTableを埋めます.
5.入力クエリ(ノード1、ノード2)の2つのノードの深さの違いを計算します.
6.より深いノードをlogn後のより浅い深さと同じ深さの新しいノードにドラッグします.
7.2つのノードの深さが同じになったので、spaseTableを使用してLCAを検索します.
上記のプロセスでは、コアは4番のプロセスです.下図を見て、理解してみましょう

10番目のノードのうち,8番目のノードは212^121の親ノードである.
8番目のノードは、9番目のノードの202^020番目の親ノードです.
---> dp[10][1] == dp[ dp[10][0] ][ 0 ]
10番ノードでは、6番ノードは222^222の2番目の親ノードです.
6番目のノードは、8番目のノードから212^121番目の親ノードです.
---> dp[10][2] == dp[ dp[10][1] ][ 1 ]
すなわちsparseTable[n][k]=sparseTable[n][k-1][k-1]である.
次に、lognで異なる深さのノードだけを同じ位置に配置する方法について説明します.

上の図で15番ノードと3番ノードのLCAを見つけます.
まず深さ差diff=3を計算し、それをバイナリ数として計算し、ceil(log 3)ceil(log 3)ceil(log 3)だけで実行する.15=1+2+4+8の方法で計算した脈絡と同じである.
すなわち,より深いノードではlog(diff)log(diff)log(diff)log(diff)のみが同じ深さのノードに調整できる.
最後に,同じ深さの2つのノードでLCAを検索する過程をまとめた.
sparseTable[node 1]およびsparseTable[node 2]では、親MAXの親ノードから0までを比較します.
このうちMAXは、2 MAX 2^{MAX}2 MAX==ツリー全体の深さのMAXである.
0は、20=12^0=120=1番目の親ノードを表します.
この位置のノードがまったく存在しない場合、sparseTable[i][k]=0になります.
MAX-0の比較では、2つのノードの親ノードが異なる場合、そのフェーズで計算された親ノードにノード1とノード2が更新され、作業が続行されます.
親ノードが同じ場合は、ノード1とノード2は保持されます.
0に比較すると,正解はsparseTable[node 1][0]を出力する.(最後に、2つの異なるノードの最初の親ノードはLCAです.)
この方法の可能な理由を説明し、文章を終了します.
コアはnode 1とnode 2を更新することです.
初期の2つのノードのうち、2 k 2^k 2 kの2番目の上の親ノードが値が異なる場合、初期の2つのノードが更新されます.
このとき,最初に見つかった2つの親ノードはLCAと初期の2つのノードからの距離で最大の部分を占める.
15=23+22+21+215=2^3+2^2+2^1+2^015=23+22+21+20は、最初に見つかった部分が232323^323であることを示しています.
232^323に222^222を加え、23+22=122^3+2^2=1223+22=12を見つけます.
もう一度行うと、23+22+21=142^3+2^2+2^1=1423+22+21=14になります.
結果は更新を続け、23+22+21+20=152^3+2^2+2^1+2^0=1523+22+21+20=15の方法を見つけた.
そこで、最後にLCAを探すfor loopでは、i因子がMAX~0で減算され、これはLCAと初期の2つのノードからの距離が2の二乗和のときの指数値を表す.
下の写真を見て理解してください.

コード#コード#

import sys
from math import log2
sys.setrecursionlimit(10**5)
In = lambda: sys.stdin.readline().rstrip()
MIS = lambda: map(int, In().split())

# https://alphatechnic.tistory.com/23 와 같은 실수를 함 (sparseTable 채우는 부분)

def init():
    N = int(In())
    tree = [[] for i in range(N + 1)]
    for n in range(N - 1):
        u, v = MIS()
        tree[u].append(v)
        tree[v].append(u)
    depth = [0] * (N + 1)
    MAX = int(log2(N)) + 1
    dp = [[0] * (MAX + 1) for i in range(N + 1)] #sparseTable 부분
    M = int(In())
    return N, tree, depth, dp, M, MAX


def dfs(cur, pre, d):
    for nxt in tree[cur]:
        if nxt == pre: continue
        depth[nxt] = d + 1
        dp[nxt][0] = cur
        dfs(nxt, cur, d + 1)


def sparseTable():
    for j in range(1, MAX + 1):
        for i in range(1, N + 1):
            dp[i][j] = dp[dp[i][j - 1]][j - 1]


def findDepthDiff(u, v):
    return (depth[u] - depth[v], v, u) if depth[u] > depth[v] \
        else (depth[v] - depth[u], u, v)


def moving(depthDiff, mx):  # 깊이가 더 깊은 노드를 대상으로 깊이를 맞춰주는 작업
    j = 0
    jj = 1 << j
    while jj <= depthDiff:
        if depthDiff & jj:
            mx = dp[mx][j]
        j += 1
        jj = jj<<1
    '''
    diff = 8, 1000(2)
    j = 0, jj = 1
    j = 1, jj = 2
    j = 2, jj = 4
    j = 3, jj = 8 -> mx = dp[mx][3]
    '''
    return mx


def movingWith(mn, mx):  # 깊이는 같고 노드가 다를 경우 동시에 높이를 조절하면서 LCA 탐색
    for j in range(MAX-1, -1, -1):
        if dp[mx][j] == dp[mn][j]: continue
        if dp[mx][j] != 0 and dp[mx][j] != dp[mn][j]:
            mx = dp[mx][j]
            mn = dp[mn][j]
    ans = dp[mx][0]
    return ans


N, tree, depth, dp, M, MAX = init()
dfs(1, 0, 0)
sparseTable()

for m in range(M):
    u, v = MIS()
    depthDiff, mn, mx = findDepthDiff(u, v)
    mx = moving(depthDiff, mx)
    ans = mx
    if mn != mx:
        ans = movingWith(mn, mx)
    print(ans)