本文主要是介绍hdu 5266 pog loves szh III LCA+RMQ，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
给你一棵树，然后询问l~r节点的最近公共祖先（LCA）。
思路：
用RMQ维护一段区间的LCA，然后询问时，将两个区间的LCA再求一次LCA即可。
code：
#pragma comment(linker, "/STACK:102400000,102400000")
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;const int N = 3e5+5;
typedef long long LL;int n, q;
int head[N], cnt;
struct Edge {int v, next;
}edge[N<<1];int par[N][30];
int dep[N];
int d[N];
int rmq[N][30];void init() {memset(head, -1, sizeof(head));cnt = 0;
}Edge t;
void addEdge(int u, int v) {t.v = v, t.next = head[u];edge[cnt] = t;head[u] = cnt++;
}void dfs(int u, int p, int d) {dep[u] = d; par[u][0] = p;for(int i = head[u];i != -1; i = edge[i].next) {int v = edge[i].v;if(v == p) continue;dfs(v, u, d+1);}
}int lca(int u, int v) {if(dep[u] > dep[v]) swap(u, v);for(int i = 0;i < 20; i++) {if(((dep[v]-dep[u])>>i) & 1)v = par[v][i];}if(u == v) return v;for(int k = 20;k >= 0; k--)if(par[v][k] != par[u][k]) {u = par[u][k];v = par[v][k];}return par[u][0];
}int query(int l, int r) {int len = r-l+1;int k = 0;while((1<<(k+1)) <= len) k++;return lca(rmq[l][k], rmq[r-(1<<k)+1][k]);
}int main() {while(scanf("%d", &n) != EOF) {init();int u, v;for(int i = 0;i < n-1; i++) {scanf("%d%d", &u, &v);addEdge(u, v);addEdge(v, u);}dfs(1, -1, 0);for(int i = 0;i+1<20; i++) {for(int u = 1;u <= n; u++) {if(par[u][i] < 0) par[u][i+1] = -1;else par[u][i+1] = par[par[u][i]][i];}}for(int i = 1;i <= n; i++) rmq[i][0] = i;for(int k = 0;k < 20; k++) for(int i = 1;i <= n; i++) {if(i+(1<<(k+1))-1 > n) break;rmq[i][k+1] = lca(rmq[i][k], rmq[i+(1<<k)][k]);//cout<<rmq[i][k+1]<<endl;}//cout<<rmq[2][2]<<endl;scanf("%d", &q);int l, r;while(q--) {scanf("%d%d", &l, &r);printf("%d\n", query(l, r));}}return 0;
}
这篇关于hdu 5266 pog loves szh III LCA+RMQ的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
