题目链接：hdu 5266 pog loves szh III
思路：因为它查询的是区间上的lca，所以我们需要用在线lca来处理，达到单点查询的复杂度为O(1),所以我们在建立线段树区间查询的时候可以达到O(1*nlgn)的时间复杂度
ps：因为栈很容易爆，所以。。。。。你懂的 --》#pragma comment(linker, "/STACK:1024000000,1024000000")
/************************************************************** Problem:hdu 5266 User: youmi Language: C++ Result: Accepted Time:3790Ms Memory:82816k ****************************************************************/ #pragma comment(linker, "/STACK:1024000000,1024000000") //#include<bits/stdc++.h> #include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <map> #include <stack> #include <sstream> #include <cmath> #include <queue> #include <string> #include <vector> #define zeros(a) memset(a,0,sizeof(a)) #define ones(a) memset(a,-1,sizeof(a)) #define sc(a) scanf("%d",&a) #define sc2(a,b) scanf("%d%d",&a,&b) #define rep(i,n) for(int i=0;i<n;i++) #define lson (step<<1) #define rson (lson+1) #define esp 1e-6 #define oo 0x3fffffff #define TEST cout<<"*************************"<<endl using namespace std; typedef long long ll; int n,q; const int M=20; int bit[M]; const int maxn=300000+10; struct side { int v,next; }e[maxn<<1]; struct node { int l,r,fa; }seg[maxn<<2]; int head[maxn],euler[maxn<<1],pos[maxn],depth[maxn<<1],vis[maxn]; int dp[maxn<<1][M]; int T,tot; void Swap(int &a,int &b) { int c; c=a; a=b; b=c; } void ebuild(int u,int v) { e[T].v=v; e[T].next=head[u]; head[u]=T++; } void dfs(int u,int dep) { vis[u]=1; euler[++tot]=u; depth[tot]=dep; pos[u]=tot; for(int i=head[u];~i;i=e[i].next) { int v=e[i].v; if(!vis[v]) { dfs(v,dep+1); euler[++tot]=u; depth[tot]=dep; } } } void ST(int len) { for(int i=1;i<=len;i++) dp[i][0]=i; int k=(int )(log(len*1.0)/log(2.0)); for(int j=1;j<=k;j++) { for(int i=1;i+bit[j]<=len;i++) { int l=dp[i][j-1]; int r=dp[i+bit[j-1]][j-1]; dp[i][j]=depth[l]<depth[r]?l:r; } } } int RMQ(int x,int y) { int len=(y-x+1); int k=(int )(log(len*1.0)/log(2.0)); int l=dp[x][k]; int r=dp[y-bit[k]+1][k]; return depth[l]<depth[r]?l:r; } int lca(int x,int y) { int l=pos[x]; int r=pos[y]; if(l>r) Swap(l,r); return euler[RMQ(l,r)]; } void pushup(int step) { if(seg[lson].fa==seg[rson].fa) seg[step].fa=seg[lson].fa; else { seg[step].fa=lca(seg[lson].fa,seg[rson].fa); } } int query(int step,int l,int r) { //printf("step->%d stepl->%d stepr->%d l->%d r->%d ",step,seg[step].l,seg[step].r,l,r); if(l==seg[step].l&&r==seg[step].r) return seg[step].fa; int mid=(seg[step].l+seg[step].r)>>1; if(mid>=r) return query(lson,l,r); else if(mid<l) return query(rson,l,r); else { return lca(query(lson,l,mid),query(rson,mid+1,r)); } } void qbuild(int step,int l,int r) { seg[step].l=l; seg[step].r=r; if(l==r) { seg[step].fa=l; return ; } int mid=(l+r)>>1; qbuild(lson,l,mid); qbuild(rson,mid+1,r); pushup(step); } void init() { ones(head); zeros(vis); T=0; tot=0; int u,v; for(int i=0;i<n-1;i++) { scanf("%d%d",&u,&v); ebuild(u,v); ebuild(v,u); } dfs(1,1); ST(2*n-1); qbuild(1,1,n); } int main() { //freopen("in.txt","r",stdin); for(int i=0;i<=M;i++) bit[i]=(1<<i); while(~sc(n)) { init(); sc(q); int l,r; while(q--) { sc2(l,r); printf("%d ",query(1,l,r)); } } return 0; }