題目鏈接

rmq求LCA，interesting。

一直沒有學這玩意兒是因為CTSC的Day1T2，當時我打的樹剖LCA 65分，gxb打的rmq LCA 45分。。。

不過rmq理論復雜度還是小一點的，就學一下把。

RMQ求LCA

我們要用到三個數組

\(dfn[i]\):第\(i\)個節(jié)點位置的時間戳

\(id[i][j]\)：在歐拉序中\(i\)到\(i + 2^j - 1\)這段區(qū)間內深度最小的節(jié)點編號

\(dep[i]\)：第\(i\)個節(jié)點的深度

實際上用到了一個性質：

對于任意兩點的\(LCA\)，一定是它們歐拉序中兩點之間的最小值

歐拉序是什么？就是把dfs中遍歷到每一個一個節(jié)點(包括回溯時遍歷到)加到一個序列里，最終得到的就是歐拉序

時空復雜度

設\(T = 2 * n - 1\)

時間復雜度：

預處理：\(O(TlogT)\)

查詢：\(O(1)\)

空間復雜度：

考慮歐拉序中有多少個點，首先每個點被訪問到的時候會做出\(1\)的貢獻

其次在遍歷每條邊時會多出\(1\)的共貢獻

因此總空間復雜度為：\(O(T)\)

// luogu-judger-enable-o2 #include<bits/stdc++.h> const int MAXN = 1e6 + 10; using namespace std; inline int read() {char c = getchar(); int x = 0, f = 1;while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();return x * f; } int N, Q, S, tot, dfn[MAXN], rev[MAXN], dep[MAXN], id[MAXN][21], lg2[MAXN], rd[MAXN]; vector<int> v[MAXN]; void dfs(int x, int fa) {dfn[x] = ++tot; dep[x] = dep[fa] + 1; id[tot][0] = x; for(int i = 0, to; i < v[x].size(); i++) {if((to = v[x][i]) == fa) continue;dfs(to, x);id[++tot][0] = x;} } void RMQ() {for(int i = 2; i <= tot; i++) lg2[i] = lg2[i >> 1] + 1;for(int j = 1; j <= 20; j++) {for(int i = 1; (i + (1 << j) - 1) <= tot; i++) {int r = i + (1 << (j - 1));id[i][j] = dep[id[i][j - 1]] < dep[id[r][j - 1]] ? id[i][j - 1] : id[r][j - 1];}} } int Query(int l, int r) {if(l > r) swap(l, r);int k = lg2[r - l + 1];return dep[id[l][k]] < dep[id[r - (1 << k) + 1][k]] ? id[l][k] : id[r - (1 << k) + 1][k]; } int main() {freopen("a.in", "r", stdin);N = read(); Q = read(); S = read();for(int i = 1; i <= N - 1; i++) {int x = read(), y = read();v[x].push_back(y); v[y].push_back(x);}dfs(S, 0);RMQ();while(Q--) {int x = read(), y = read();printf("%d\n", Query(dfn[x], dfn[y]));}return 0; }

總結

以上是生活随笔為你收集整理的RMQ求LCA的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。