1/*
2 * LCA (Lowest Common Ancestor)
3 * Binary Lifting, Euler Tour, Tree Path Queries
4 *
5 * 트리에서 두 노드의 최소 공통 조상을 찾습니다.
6 */
7
8#include <stdio.h>
9#include <stdlib.h>
10#include <string.h>
11#include <math.h>
12
13#define MAXN 100005
14#define LOG 17
15
16/* =============================================================================
17 * 1. 트리 구조
18 * ============================================================================= */
19
20typedef struct AdjNode {
21 int vertex;
22 int weight;
23 struct AdjNode* next;
24} AdjNode;
25
26AdjNode* adj[MAXN];
27int depth[MAXN];
28int parent[MAXN][LOG]; /* Binary Lifting 테이블 */
29int dist[MAXN]; /* 루트로부터의 거리 */
30int n;
31
32void add_edge(int u, int v, int w) {
33 AdjNode* node = malloc(sizeof(AdjNode));
34 node->vertex = v;
35 node->weight = w;
36 node->next = adj[u];
37 adj[u] = node;
38
39 node = malloc(sizeof(AdjNode));
40 node->vertex = u;
41 node->weight = w;
42 node->next = adj[v];
43 adj[v] = node;
44}
45
46/* =============================================================================
47 * 2. Binary Lifting 전처리
48 * ============================================================================= */
49
50void dfs_preprocess(int v, int p, int d, int distance) {
51 depth[v] = d;
52 parent[v][0] = p;
53 dist[v] = distance;
54
55 for (int i = 1; i < LOG; i++) {
56 if (parent[v][i-1] != -1)
57 parent[v][i] = parent[parent[v][i-1]][i-1];
58 else
59 parent[v][i] = -1;
60 }
61
62 AdjNode* node = adj[v];
63 while (node) {
64 if (node->vertex != p) {
65 dfs_preprocess(node->vertex, v, d + 1, distance + node->weight);
66 }
67 node = node->next;
68 }
69}
70
71void preprocess(int root) {
72 memset(parent, -1, sizeof(parent));
73 dfs_preprocess(root, -1, 0, 0);
74}
75
76/* =============================================================================
77 * 3. LCA 쿼리
78 * ============================================================================= */
79
80int lca(int u, int v) {
81 /* 깊이 맞추기 */
82 if (depth[u] < depth[v]) {
83 int temp = u; u = v; v = temp;
84 }
85
86 int diff = depth[u] - depth[v];
87 for (int i = 0; i < LOG; i++) {
88 if ((diff >> i) & 1) {
89 u = parent[u][i];
90 }
91 }
92
93 if (u == v) return u;
94
95 /* 동시에 올라가기 */
96 for (int i = LOG - 1; i >= 0; i--) {
97 if (parent[u][i] != parent[v][i]) {
98 u = parent[u][i];
99 v = parent[v][i];
100 }
101 }
102
103 return parent[u][0];
104}
105
106/* =============================================================================
107 * 4. K번째 조상
108 * ============================================================================= */
109
110int kth_ancestor(int v, int k) {
111 for (int i = 0; i < LOG && v != -1; i++) {
112 if ((k >> i) & 1) {
113 v = parent[v][i];
114 }
115 }
116 return v;
117}
118
119/* =============================================================================
120 * 5. 두 노드 사이 거리
121 * ============================================================================= */
122
123int distance_between(int u, int v) {
124 int ancestor = lca(u, v);
125 return dist[u] + dist[v] - 2 * dist[ancestor];
126}
127
128/* =============================================================================
129 * 6. 경로 위 K번째 노드
130 * ============================================================================= */
131
132int kth_node_on_path(int u, int v, int k) {
133 int ancestor = lca(u, v);
134 int dist_u_lca = depth[u] - depth[ancestor];
135 int dist_v_lca = depth[v] - depth[ancestor];
136
137 if (k <= dist_u_lca) {
138 return kth_ancestor(u, k);
139 } else {
140 return kth_ancestor(v, dist_u_lca + dist_v_lca - k);
141 }
142}
143
144/* =============================================================================
145 * 7. Euler Tour + RMQ 방식
146 * ============================================================================= */
147
148int euler_tour[2 * MAXN];
149int first_occurrence[MAXN];
150int euler_depth[2 * MAXN];
151int euler_idx;
152
153/* Sparse Table for RMQ */
154int sparse_table[2 * MAXN][LOG];
155int log_table[2 * MAXN];
156
157void euler_dfs(int v, int p, int d) {
158 first_occurrence[v] = euler_idx;
159 euler_tour[euler_idx] = v;
160 euler_depth[euler_idx] = d;
161 euler_idx++;
162
163 AdjNode* node = adj[v];
164 while (node) {
165 if (node->vertex != p) {
166 euler_dfs(node->vertex, v, d + 1);
167 euler_tour[euler_idx] = v;
168 euler_depth[euler_idx] = d;
169 euler_idx++;
170 }
171 node = node->next;
172 }
173}
174
175void build_sparse_table(int len) {
176 /* log 테이블 전처리 */
177 log_table[1] = 0;
178 for (int i = 2; i <= len; i++) {
179 log_table[i] = log_table[i / 2] + 1;
180 }
181
182 /* Sparse Table 초기화 */
183 for (int i = 0; i < len; i++) {
184 sparse_table[i][0] = i;
185 }
186
187 for (int j = 1; (1 << j) <= len; j++) {
188 for (int i = 0; i + (1 << j) - 1 < len; i++) {
189 int left = sparse_table[i][j-1];
190 int right = sparse_table[i + (1 << (j-1))][j-1];
191 sparse_table[i][j] = (euler_depth[left] < euler_depth[right]) ? left : right;
192 }
193 }
194}
195
196int rmq_query(int l, int r) {
197 int k = log_table[r - l + 1];
198 int left = sparse_table[l][k];
199 int right = sparse_table[r - (1 << k) + 1][k];
200 return (euler_depth[left] < euler_depth[right]) ? left : right;
201}
202
203int lca_rmq(int u, int v) {
204 int l = first_occurrence[u];
205 int r = first_occurrence[v];
206 if (l > r) {
207 int temp = l; l = r; r = temp;
208 }
209 return euler_tour[rmq_query(l, r)];
210}
211
212void preprocess_euler(int root) {
213 euler_idx = 0;
214 euler_dfs(root, -1, 0);
215 build_sparse_table(euler_idx);
216}
217
218/* =============================================================================
219 * 테스트
220 * ============================================================================= */
221
222void cleanup(void) {
223 for (int i = 0; i < n; i++) {
224 AdjNode* node = adj[i];
225 while (node) {
226 AdjNode* temp = node;
227 node = node->next;
228 free(temp);
229 }
230 adj[i] = NULL;
231 }
232}
233
234int main(void) {
235 printf("============================================================\n");
236 printf("LCA (Lowest Common Ancestor) 예제\n");
237 printf("============================================================\n");
238
239 /*
240 * 트리 구조:
241 * 0
242 * /|\
243 * 1 2 3
244 * /| |
245 * 4 5 6
246 * /
247 * 7
248 */
249 n = 8;
250 add_edge(0, 1, 1);
251 add_edge(0, 2, 2);
252 add_edge(0, 3, 3);
253 add_edge(1, 4, 1);
254 add_edge(1, 5, 1);
255 add_edge(3, 6, 2);
256 add_edge(4, 7, 1);
257
258 /* 1. Binary Lifting 전처리 */
259 printf("\n[1] Binary Lifting LCA\n");
260 preprocess(0);
261
262 printf(" 트리: 0-1-4-7, 0-1-5, 0-2, 0-3-6\n");
263 printf(" LCA(4, 5) = %d\n", lca(4, 5));
264 printf(" LCA(4, 6) = %d\n", lca(4, 6));
265 printf(" LCA(7, 2) = %d\n", lca(7, 2));
266 printf(" LCA(5, 7) = %d\n", lca(5, 7));
267
268 /* 2. K번째 조상 */
269 printf("\n[2] K번째 조상\n");
270 printf(" 7의 1번째 조상: %d\n", kth_ancestor(7, 1));
271 printf(" 7의 2번째 조상: %d\n", kth_ancestor(7, 2));
272 printf(" 7의 3번째 조상: %d\n", kth_ancestor(7, 3));
273
274 /* 3. 거리 */
275 printf("\n[3] 두 노드 사이 거리\n");
276 printf(" dist(4, 5) = %d\n", distance_between(4, 5));
277 printf(" dist(7, 6) = %d\n", distance_between(7, 6));
278 printf(" dist(7, 2) = %d\n", distance_between(7, 2));
279
280 /* 4. 경로 위 K번째 노드 */
281 printf("\n[4] 경로 위 K번째 노드\n");
282 printf(" 7→6 경로의 0번째 노드: %d\n", kth_node_on_path(7, 6, 0));
283 printf(" 7→6 경로의 2번째 노드: %d\n", kth_node_on_path(7, 6, 2));
284 printf(" 7→6 경로의 4번째 노드: %d\n", kth_node_on_path(7, 6, 4));
285
286 /* 5. Euler Tour + RMQ */
287 printf("\n[5] Euler Tour + RMQ LCA\n");
288 preprocess_euler(0);
289 printf(" LCA_RMQ(4, 5) = %d\n", lca_rmq(4, 5));
290 printf(" LCA_RMQ(7, 6) = %d\n", lca_rmq(7, 6));
291
292 /* 6. 복잡도 비교 */
293 printf("\n[6] LCA 알고리즘 비교\n");
294 printf(" | 방법 | 전처리 | 쿼리 | 공간 |\n");
295 printf(" |----------------|-----------|-----------|------------|\n");
296 printf(" | Binary Lifting | O(n log n)| O(log n) | O(n log n) |\n");
297 printf(" | Euler + RMQ | O(n log n)| O(1) | O(n log n) |\n");
298 printf(" | Tarjan (오프라인)| O(n + q) | O(α(n)) | O(n) |\n");
299
300 cleanup();
301
302 printf("\n============================================================\n");
303
304 return 0;
305}