dfs序是指你用dfs遍歷一棵樹時，每個節點會按照遍歷到的先后順序得到一個序號。然后你用這些序號，可以把整個遍歷過程表示出來。

如上圖所示，則整個遍歷過程為1 2 3 2 4 5 4 6 4 2 1 7 8 7 1

反正按照實現目的不同，dfs序會長得不太一樣，比如說為了實現LCA就需要上面形式的dfs序。

用vs[]來保存整個遍歷過程。

id[i]用來保存i節點的序號第一次出現在vs[]中時的下標。

這樣當詢問u，v點的LCA是誰是，你只要找到在vs[id[u]<= i <= id[v]]中最小值即可，那個最小值所對應的節點就是u，v的LCA

而這個過程你可以用RMQ進行預處理，然后O（1）就可以得到。（你應該知道vs[]的總長度為n*2-1）

1 #include<bits/stdc++.h> 2 using namespace std; 3 const int M = 1e5 + 10 ; 4 vector<int> g[M] ; 5 int n ; 6 7 vector<int> vs ;//dfs order 8 int tot ; 9 int orm[M] ; 10 int id[M] ; 11 int dep[M] ; 12 13 int d[M][30] ;//RMQ 14 void dfs (int o , int u ,int DEP) { 15 int tmp = tot ++ ; 16 dep[u] = DEP ; 17 id[u] = vs.size () ; 18 orm[tmp] = u ; 19 vs.push_back (tmp) ; 20 21 for (int i = 0 ; i < g[u].size () ; i ++) { 22 int v = g[u][i] ; 23 if (v == o) continue ; 24 dfs (u , v , DEP + 1) ; 25 } 26 int len = vs.size () ; 27 if (vs[len-1] == tmp) vs.push_back (vs[id[o]]) ; 28 else vs.push_back (tmp) ; 29 } 30 31 void init_RMQ () { 32 for (int i = 0 ; i < 2*n-1 ; i ++) d[i][0] = vs[i] ; 33 for (int j = 1 ; (1 << j) <= n ; j ++) { 34 for (int i = 0 ; i + (1 << j) <= n ; i ++) { 35 d[i][j] = min (d[i][j-1] , d[i+(1<<(j-1))][j-1]) ; 36 } 37 } 38 } 39 40 int RMQ (int l , int r) { 41 printf ("l = %d , r = %d\n" , l , r ) ; 42 int k = 0 ; 43 while ( (1<<(k+1)) <= r - l + 1) k ++ ; 44 int tmp = min (d[l][k] , d[1+r-(1<<k)][k]) ; 45 return orm[tmp] ; 46 } 47 void Print () { 48 for (int i = 0 ; i < 2*n-1 ; i ++) printf ("%3d " , i ) ; puts ("") ; 49 puts ("dfs order:") ; 50 for (int i = 0 ; i < 2*n-1 ; i ++) printf ("%3d " , vs[i]) ; puts ("") ; 51 puts ("deep:") ; 52 for (int i = 0 ; i < n ; i ++) printf ("%3d " , dep[i]) ; puts ("") ; 53 puts ("id :") ; 54 for (int i = 0 ; i < n ; i ++) printf ("%3d " , id[i]) ; puts ("") ; 55 } 56 57 void LCA () { 58 dfs (0,0,0) ; 59 init_RMQ () ; 60 Print () ; 61 } 62 63 int main () { 64 cin >> n ; 65 for (int i = 0 ; i < n - 1 ; i ++) { 66 int u , v ; 67 cin >> u >> v ; 68 g[u].push_back (v) ; 69 g[v].push_back (u) ; 70 } 71 LCA () ; 72 int Q ; 73 cin >> Q ; 74 while (Q --) { 75 int u , v ; 76 cin >> u >> v ; 77 if (id[u] > id[v]) swap (u , v ) ; 78 int ans = RMQ (id[u] , id[v]) ; 79 printf ("The %d and %d the lastest ans is %d , and they are away from %d\n" , u , v , ans , dep[u]+dep[v]-2*dep[ans]) ; 80 } 81 return 0 ; 82 }

測試數據：

8
0 1
0 2
1 3
1 4
2 5
4 6
4 7
3
0 4
3 4
6 2

3次詢問的答案你畫一下即可。hhhhhh（以0號節點為根）

?

轉載于:https://www.cnblogs.com/get-an-AC-everyday/p/4673255.html

總結

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

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