BOJ 11438 LCA2

https://www.acmicpc.net/problem/11438
時間1.5秒、メモリ256 MB
input :

N(2 ≤ N ≤ 100,000)

N-1行:ツリーに接続された2つの頂点

M(1 ≤ M ≤ 100,000)

M行の頂点対

output :

第1行出力東昊で得られる最大杯面数

条件:

ツリーの各頂点は1番からN番まで、ルートは1番です.

2つのノードの最も近い共通の祖先を出力するのはいくらですか?

前のLCAを改善してこそ問題を解決することができる.

改善する

まず改良の方向からlca関数内をlogで移動する.
したがって,時間的複雑さは非常に強くなるが,2^0~2^xのノードに記録しなければならない.
そのため、メモリと時間の複雑さを交換したと見なすことができますが、まず時間が速くなります...

DP

このLCAはすべてのノードを記録すべきだと言っています.
LCAを実装する場合,parentでは2^0の上のセルに存在するノードの情報を定義する.
これにより、2 D配列ですべてを格納できます.
dfsを実行した後、2^1~2^xに移動し、漸進的に格納します.
どうして.最初に持っていた情報は2^0にあるやつだけだったから.

# 2^i 번째의 부모 노드의 값을 저장.
    for i in range(1, 21):
        # j번째 노드 기준으로.
        for j in range(1, n + 1):
            # 2번쨰 칸 위의 값을 저장하려 할 때
            # 현재 노드의 부모 노드로 이동 부모 노드의 "부모"노드의 값을 가져옴.
            # 이러한 단계로 모든 DP를 초기화 함.
            parent[j][i] = parent[parent[j][i - 1]][i - 1]

parent[j][i-1]により、2^(i-1)の上にあるセルのやつの2^(i-1)の上にあるノードを取得できます.どうせ乗って持ってきたのだ.

lca

lcaセクションは、すべての移動可能な位置を確認します.
現在深さ差が9の場合、
8マス上1マス上をこのように移動
移動可能な位置でその位置に存在する親を探すことがこの問題を貫く原則である.

import sys
sys.setrecursionlimit(100000)

def dfs(node, depth):
    visit[node] = True
    d[node] = depth

    for next_node in graph[node]:
        if visit[next_node] == 1:
            continue
        parent[next_node][0] = node
        dfs(next_node, depth + 1)

def set_parent():
    """
        dp로 모든 부모 관계를 저장한다.
    """
    dfs(1, 0)
    # 2^i 번째의 부모 노드의 값을 저장.
    for i in range(1, 21):
        # j번째 노드 기준으로.
        for j in range(1, n + 1):
            # 2번쨰 칸 위의 값을 저장하려 할 때
            # 현재 노드의 부모 노드로 이동 부모 노드의 "부모"노드의 값을 가져옴.
            # 이러한 단계로 모든 DP를 초기화 함.
            parent[j][i] = parent[parent[j][i - 1]][i - 1]

def lca(high, low):
    # 가지고 있는 값이 클수록 더 깊이 있는 거임.
    if d[high] > d[low]:
        high, low = low, high

    # 2^20 ~ 2^0 까지 반복을 수행
    for log in range(20, -1, -1):
        if d[low] - d[high] >= (1 << log):
            low = parent[low][log]

    # 서로 동일한 노드 인 경우.
    if high == low:
        return high

    for log in range(20, -1, -1):
        if parent[high][log] != parent[low][log]:
            low = parent[low][log]
            high = parent[high][log]

    return parent[high][0]

n = int(sys.stdin.readline())
graph = [[] for _ in range(n + 1)]
parent = [[0] * 21 for _ in range(n + 1)]
d = [0] * (n + 1)
visit = [0] * (n + 1)

for i in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

set_parent()

m = int(sys.stdin.readline())
for i in range(m):
    a, b = map(int, sys.stdin.readline().split())
    print(lca(a, b))