題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=5266

解題思路：

考慮dfs序，通過在簡單的證明可知L~R的LCA為L?~R?中dfs序較小的那個位置與dfs序較大的那個位置的LCA。因此只要通過st表處理L~R最大dfs序與最小dfs序的編號即可。 這里用線段樹維護dfs序的最大和最小值。

#pragma comment(linker, "/STACK:102400000,102400000") #include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std;const int maxn = 300005; const int inf = 0x3f3f3f3f; struct Edge {int to,next; }edge[maxn<<1]; struct Seg {int l,r,Min,Max; }tree[maxn<<2]; int n,q,cnt,tot,head[maxn]; int ver[maxn],R[maxn],first[maxn]; int dp[maxn<<1][20],minl,maxr;void addedge(int u,int v) {edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++; }void initRMQ() {for(int i = 1; i <= tot; i++)dp[i][0] = i;for(int j = 1; (1 << j) <= tot; j++)for(int i = 1; i + (1 << j) - 1 <= tot; i++){if(R[dp[i][j-1]] < R[dp[i+(1<<j-1)][j-1]])dp[i][j] = dp[i][j-1];else dp[i][j] = dp[i+(1<<j-1)][j-1];} }int findLCA(int l,int r) {int k = (int)(log(r - l + 1.0) / log(2.0));if(R[dp[l][k]] < R[dp[r-(1<<k)+1][k]])return ver[dp[l][k]];return ver[dp[r-(1<<k)+1][k]]; }void build(int rt,int l,int r) {tree[rt].l = l, tree[rt].r = r;if(l == r){tree[rt].Max = tree[rt].Min = first[l];return;}int mid = (l + r) >> 1;build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);tree[rt].Max = max(tree[rt<<1].Max,tree[rt<<1|1].Max);tree[rt].Min = min(tree[rt<<1].Min,tree[rt<<1|1].Min); }void query(int rt,int l,int r) {if(l <= tree[rt].l && tree[rt].r <= r){minl = min(minl,tree[rt].Min);maxr = max(maxr,tree[rt].Max);return;}int mid = (tree[rt].l + tree[rt].r) >> 1;if(l <= mid) query(rt<<1,l,r);if(mid < r) query(rt<<1|1,l,r); }void dfs(int u,int fa,int depth) {first[u] = ++tot;R[tot] = depth;ver[tot] = u;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(v == fa) continue;dfs(v,u,depth+1);ver[++tot] = u;R[tot] = depth;} }int main() {int u,v,l,r;while(scanf("%d",&n)!=EOF){cnt = tot = 0;memset(head,-1,sizeof(head));for(int i = 1; i < n; i++){scanf("%d%d",&u,&v);addedge(u,v);addedge(v,u);}dfs(1,-1,0);build(1,1,n);initRMQ();scanf("%d",&q);while(q--){scanf("%d%d",&l,&r);maxr = -1,minl = inf;query(1,l,r);int lca = findLCA(minl,maxr);printf("%d\n",lca);}}return 0; }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu 5266(线段树+LCA)的全部內容，希望文章能夠幫你解決所遇到的問題。

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