# LCA cu RMQ

Apr 18th, 2021 (edited)
487
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. const int NMAX = 2e5 + 5; /// 2 * N
2. int N, M, tour[NMAX], depth[NMAX], first[NMAX], lg2[NMAX], rmq[20][NMAX];
3. vector<int> G[NMAX];
4.
5. void dfs_Euler(int u, int parent, int level) {
6.   sz[u] = 1;
7.   tour[++M] = u;
8.   depth[M] = level;
9.   first[u] = M;
10.   for (int v : G[u])
11.     if (v != parent) {
12.       dfs_Euler(v, u, level + 1);
13.       sz[u] += sz[v];
14.       tour[++M] = u;
15.       depth[M] = level;
16.     }
17. }
18.
19. void compute_rmq() {
20.   for (int i = 2; i <= M; ++i)
21.     lg2[i] = lg2[i >> 1] + 1;
22.   for (int i = 1; i <= M; ++i)
23.     rmq[0][i] = i;
24.   for (int i = 1; (1 << i) < M; ++i)
25.     for (int j = 1; j <= M - (1 << i); ++j) {
26.       int l = 1 << (i - 1);
27.       rmq[i][j] = rmq[i - 1][j];
28.       if (depth[rmq[i - 1][j + l]] < depth[rmq[i][j]])
29.         rmq[i][j] = rmq[i - 1][j + l];
30.     }
31. }
32.
33. int lca(int u, int v) {
34.   int x = first[u], y = first[v];
35.   if (x > y)
36.     swap(x, y);
37.   int diff = y - x + 1;
38.   int l = lg2[diff];
39.   int sol = rmq[l][x];
40.   int shift = diff - (1 << l);
41.   if (depth[sol] > depth[rmq[l][x + shift]])
42.     sol = rmq[l][x + shift];
44. }
45.
46. int dist(int u, int v) {
47.   return depth[first[u]] + depth[first[v]] - (depth[first[lca(u, v)]] << 1);
48. }
RAW Paste Data