板子測試POJ1330，一發入魂，作者是KuangBin神犇，感謝???

#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 10010; int rmq[2 * MAXN]; // rmq數組,就是歐拉序列對應的深度序列struct ST {int mm[2 * MAXN];int dp[2 * MAXN][20]; // 最小值對應的下標void init(int n){mm[0] = -1;for (int i = 1; i <= n; i++){mm[i] = ((i & (i - 1)) == 0) ? mm[i - 1] + 1 : mm[i - 1];dp[i][0] = i;}for (int j = 1; j <= mm[n]; j++){for (int i = 1; i + (1 << j) - 1 <= n; i++){dp[i][j] = rmq[dp[i][j - 1]] < rmq[dp[i + (1 << (j - 1))][j - 1]] ? dp[i][j - 1] : dp[i + (1 << (j - 1))][j - 1];}}}int query(int a,int b) // 查詢[a,b]之間最小值的下標{if (a > b){swap(a, b);}int k = mm[b - a + 1];return rmq[dp[a][k]] <= rmq[dp[b - (1 << k) + 1][k]] ? dp[a][k] : dp[b - (1 << k) + 1][k];} };// 邊的結構體定義 struct Edge {int to, next; };Edge edge[MAXN * 2];int tot, head[MAXN]; int F[MAXN * 2]; // 歐拉序列,就是dfs遍歷的順序,長度為2*n-1,下標從1開始 int P[MAXN]; // P[i]表示點i在F中第一次出現的位置 int cnt; ST st;void init() {tot = 0;memset(head, -1, sizeof(head)); }void addedge(int u, int v) // 加邊,無向邊需要加兩次 {edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; }void dfs(int u, int pre, int dep) {F[++cnt] = u;rmq[cnt] = dep;P[u] = cnt;for (int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if (v == pre){continue;}dfs(v, u, dep + 1);F[++cnt] = u;rmq[cnt] = dep;} }void LCA_init(int root, int node_num) // 查詢LCA前的初始化 {cnt = 0;dfs(root, root, 0);st.init(2 * node_num - 1); }int query_lca(int u, int v) // 查詢u,v的lca編號 {return F[st.query(P[u], P[v])]; } bool flag[MAXN];int main() {int T;int N;int u, v;scanf("%d", &T);while(T--){scanf("%d", &N);init();memset(flag, false, sizeof(flag));for (int i = 1; i < N; i++){scanf("%d%d", &u, &v);addedge(u, v);addedge(v, u);flag[v] = true;}int root;for (int i = 1; i <= N; i++){if (!flag[i]){root = i;break;}}LCA_init(root, N);scanf("%d%d", &u, &v);printf("%d\n", query_lca(u, v));}return 0; }

?

總結

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

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