|
1 | | -#include <cstdio> |
2 | 1 | #include <vector> |
3 | | -#include <cstring> |
4 | | -#include <algorithm> |
5 | | - |
6 | | -namespace LCA { |
7 | | - const int N = 100000 + 10, POW = 15; |
8 | | - int fa[N][POW + 1], dep[N]; |
9 | | - void dfs(std::vector<int> G[], int u, int p = -1) { |
10 | | - memset(fa[u], -1, sizeof(fa[u])); |
11 | | - fa[u][0] = p; |
12 | | - dep[u] = p == -1 ? 0 : dep[p] + 1; |
13 | | - for (auto &&v: G[u]) dfs(G, v, u); |
14 | | - } |
15 | | - void build(int n) { |
16 | | - for (int i = 1; (1 << i) <= n; ++i) { |
17 | | - for (int j = 0; j < n; ++j) if (~fa[j][i - 1]) { |
18 | | - fa[j][i] = fa[fa[j][i - 1]][i - 1]; |
| 2 | + |
| 3 | +using uint32 = unsigned int; |
| 4 | + |
| 5 | +class SchieberVishkinLCA { |
| 6 | +public: |
| 7 | + void build(const std::vector<int> &preorder, const std::vector<int> &parents, int root) { |
| 8 | + const int n = preorder.size(); |
| 9 | + indices.resize(n); |
| 10 | + ascendant.resize(n); |
| 11 | + head.resize(n); |
| 12 | + |
| 13 | + for (int i = 0; i < n; ++i) indices[preorder[i]] = i + 1; |
| 14 | + inlabel.assign(indices.begin(), indices.end()); |
| 15 | + for (int i = n - 1; i > 0; --i) { |
| 16 | + int v = preorder[i], p = parents[v]; |
| 17 | + if (lowbit(inlabel[p]) < lowbit(inlabel[v])) { |
| 18 | + inlabel[p] = inlabel[v]; |
19 | 19 | } |
20 | 20 | } |
21 | | - } |
22 | | - int up(int u, int d) { |
23 | | - for (int i = 0; d; ++i, d >>= 1) { |
24 | | - if (d & 1) u = fa[u][i]; |
| 21 | + |
| 22 | + ascendant[root] = 0; |
| 23 | + for (int i = 1; i < n; ++i) { |
| 24 | + int v = preorder[i], p = parents[v]; |
| 25 | + ascendant[v] = ascendant[p] | lowbit(inlabel[v]); |
25 | 26 | } |
26 | | - return u; |
27 | | - } |
28 | | - int ask(int u, int v) { |
29 | | - if (dep[u] < dep[v]) std::swap(u, v); |
30 | | - u = up(u, dep[u] - dep[v]); |
31 | | - for (int i = POW; i >= 0; --i) { |
32 | | - if (fa[u][i] == fa[v][i]) continue; |
33 | | - u = fa[u][i]; |
34 | | - v = fa[v][i]; |
| 27 | + |
| 28 | + head[0] = root; |
| 29 | + for (int i = 1; i < n; ++i) { |
| 30 | + int v = preorder[i], p = parents[v]; |
| 31 | + if (inlabel[v] != inlabel[p]) head[indices[v] - 1] = p; |
| 32 | + else head[indices[v] - 1] = head[indices[p] - 1]; |
35 | 33 | } |
36 | | - if (u != v) u = fa[u][0]; |
37 | | - return u; |
38 | 34 | } |
39 | | -} |
| 35 | + |
| 36 | + int query(int u, int v) const { |
| 37 | + uint32 Iv = inlabel[v], Iu = inlabel[u]; |
| 38 | + uint32 hIv = lowbit(Iv), hIu = lowbit(Iu); |
| 39 | + uint32 mask = highbit((Iv ^ Iu) | hIv | hIu) - 1; |
| 40 | + uint32 j = lowbit(ascendant[v] & ascendant[u] & ~mask); |
| 41 | + int x, y; |
| 42 | + if (j == hIv) x = v; |
| 43 | + else { |
| 44 | + mask = highbit(ascendant[v] & (j - 1)) - 1; |
| 45 | + x = head[(indices[v] & ~mask | (mask + 1)) - 1]; |
| 46 | + } |
| 47 | + if (j == hIu) y = u; |
| 48 | + else { |
| 49 | + mask = highbit(ascendant[u] & (j - 1)) - 1; |
| 50 | + y = head[(indices[u] & ~mask | (mask + 1)) - 1]; |
| 51 | + } |
| 52 | + return indices[x] < indices[y] ? x : y; |
| 53 | + } |
| 54 | + |
| 55 | +private: |
| 56 | + static uint32 lowbit(uint32 x) { |
| 57 | + return x & ~x + 1; // x & (-x) or x & (x ^ (x - 1)) |
| 58 | + } |
| 59 | + static uint32 highbit(uint32 x) { |
| 60 | + return 1u << (31 - __builtin_clz(x)); |
| 61 | + } |
| 62 | + |
| 63 | + std::vector<uint32> indices; |
| 64 | + std::vector<uint32> inlabel; |
| 65 | + std::vector<uint32> ascendant; |
| 66 | + std::vector<int> head; |
| 67 | +}; |
0 commit comments