핵심 통찰: 부모를 2^k 번 거슬러 올라간 조상 을 미리 표로 만들면, 임의 높이 차를 O(log N) 비트 분해로 빠르게 맞출 수 있다.
시각화
핵심 아이디어
invariant: parent[u][k] = u 에서 2^k 번 조상. DP로 O(N log N) 전처리.
parent[u][0] = immediate parent of uparent[u][k] = parent[parent[u][k-1]][k-1] for k ≥ 1
두 노드 u, v 의 LCA:
depth[u] ≥ depth[v] 로 swap.
u 를 binary lifting 으로 v 와 같은 depth 로 올림.
u, v 가 같으면 그것이 LCA. 다르면 둘 다 LCA 바로 아래 까지 함께 올림.
최종 부모가 LCA.
알고리즘
preprocess(root): DFS(root, -1, 0) # depth, parent 계산 logN = ceil(log2(N)) for k = 1..logN: for u = 0..N-1: if parent[u][k-1] != -1: parent[u][k] = parent[parent[u][k-1]][k-1]lca(u, v): if depth[u] < depth[v]: swap(u, v) diff = depth[u] - depth[v] for k in bits_of(diff): # u 를 v depth 로 u = parent[u][k] if u == v: return u for k = logN..0: # 공통 조상 바로 아래로 if parent[u][k] != parent[v][k]: u = parent[u][k] v = parent[v][k] return parent[u][0]
구현
// Binary Lifting LCA, O((N + Q) log N)#include <bits/stdc++.h>using namespace std;const int MAXN = 1e5, LOG = 17;vector<int> adj[MAXN];int parent[MAXN][LOG], depth[MAXN];int N;void dfs(int u, int p, int d) { parent[u][0] = p; depth[u] = d; for (int v : adj[u]) if (v != p) dfs(v, u, d + 1);}void build() { dfs(0, -1, 0); for (int k = 1; k < LOG; k++) for (int u = 0; u < N; u++) if (parent[u][k-1] != -1) parent[u][k] = parent[parent[u][k-1]][k-1]; else parent[u][k] = -1;}int lca(int u, int v) { if (depth[u] < depth[v]) swap(u, v); int diff = depth[u] - depth[v]; for (int k = 0; k < LOG; k++) if (diff & (1 << k)) u = parent[u][k]; if (u == v) return u; for (int k = LOG - 1; k >= 0; k--) if (parent[u][k] != parent[v][k]) { u = parent[u][k]; v = parent[v][k]; } return parent[u][0];}int main() { int Q; cin >> N >> Q; for (int i = 0; i < N - 1; i++) { int a, b; cin >> a >> b; a--; b--; adj[a].push_back(b); adj[b].push_back(a); } build(); while (Q--) { int u, v; cin >> u >> v; u--; v--; cout << lca(u, v) + 1 << "\n"; }}
# Binary Lifting LCAimport sysfrom collections import dequeinput = sys.stdin.readlineN, Q = map(int, input().split())adj = [[] for _ in range(N)]for _ in range(N - 1): a, b = map(int, input().split()) a -= 1; b -= 1 adj[a].append(b); adj[b].append(a)LOG = 17parent = [[-1] * LOG for _ in range(N)]depth = [0] * Ndef dfs(u, p, d): parent[u][0] = p depth[u] = d for v in adj[u]: if v != p: dfs(v, u, d + 1)dfs(0, -1, 0)for k in range(1, LOG): for u in range(N): if parent[u][k-1] != -1: parent[u][k] = parent[parent[u][k-1]][k-1]def lca(u, v): if depth[u] < depth[v]: u, v = v, u diff = depth[u] - depth[v] for k in range(LOG): if diff & (1 << k): u = parent[u][k] if u == v: return u for k in range(LOG - 1, -1, -1): if parent[u][k] != parent[v][k]: u = parent[u][k] v = parent[v][k] return parent[u][0]out = []for _ in range(Q): u, v = map(int, input().split()) u -= 1; v -= 1 out.append(str(lca(u, v) + 1))print("\n".join(out))
// Binary Lifting LCAimport java.util.*;import java.io.*;public class Main { static final int LOG = 17; static List<Integer>[] adj; static int[][] parent; static int[] depth; static int N; static void dfs(int u, int p, int d) { parent[u][0] = p; depth[u] = d; for (int v : adj[u]) if (v != p) dfs(v, u, d + 1); } static void build() { dfs(0, -1, 0); for (int k = 1; k < LOG; k++) for (int u = 0; u < N; u++) if (parent[u][k-1] != -1) parent[u][k] = parent[parent[u][k-1]][k-1]; else parent[u][k] = -1; } static int lca(int u, int v) { if (depth[u] < depth[v]) { int t = u; u = v; v = t; } int diff = depth[u] - depth[v]; for (int k = 0; k < LOG; k++) if ((diff & (1 << k)) != 0) u = parent[u][k]; if (u == v) return u; for (int k = LOG - 1; k >= 0; k--) if (parent[u][k] != parent[v][k]) { u = parent[u][k]; v = parent[v][k]; } return parent[u][0]; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); int Q = Integer.parseInt(st.nextToken()); adj = new ArrayList[N]; for (int i = 0; i < N; i++) adj[i] = new ArrayList<>(); parent = new int[N][LOG]; depth = new int[N]; for (int i = 0; i < N - 1; i++) { st = new StringTokenizer(br.readLine()); int a = Integer.parseInt(st.nextToken()) - 1; int b = Integer.parseInt(st.nextToken()) - 1; adj[a].add(b); adj[b].add(a); } build(); StringBuilder sb = new StringBuilder(); while (Q-- > 0) { st = new StringTokenizer(br.readLine()); int u = Integer.parseInt(st.nextToken()) - 1; int v = Integer.parseInt(st.nextToken()) - 1; sb.append(lca(u, v) + 1).append('\n'); } System.out.print(sb); }}
💬 댓글