题目地址：POJ 1330 在线LCA转RMQ第一发。所谓在线LCA，就是先DFS一次，，求出遍历路径和各个点深度，那么求最近公共祖先的时候就可以转化成求从u到v经过的点中深度最小的那个。 纯模板题。 代码如下：
using namespace std;#define LL __int64#define pi acos(-1.0)const int mod=1e9+7;const int INF=0x3f3f3f3f;const double eqs=1e-9;const int MAXN=10000+10;int fir[MAXN], F[MAXN<<1], tot, deg[MAXN], rmq[MAXN<<1];int head[MAXN], cnt;struct node{int u, v, next;}edge[30000];void add(int u, int v){edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++;}void dfs(int u, int dep, int fa){F[++tot]=u;rmq[tot]=dep;fir[u]=tot;for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].v;if(v==fa) continue ;dfs(v,dep+1,u);F[++tot]=u;rmq[tot]=dep;}}struct ST{int dp[MAXN<<1][30], i, j;void init(int n){for(i=1;i<=tot;i++){dp[i][0]=i;}for(j=1;(1<<j)<=tot;j++){for(i=1;i<=tot-(1<<j)+1;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 l, int r){if(r<l) swap(l,r);int k=0;while((1<<k+1)<=r-l+1) k++;return rmq[dp[l][k]]<rmq[dp[r+1-(1<<k)][k]]?dp[l][k]:dp[r+1-(1<<k)][k];}}st;void init(){memset(head,-1,sizeof(head));cnt=tot=0;memset(deg,0,sizeof(deg));}int main(){int t, n, i, u, v;scanf(“%d”,&t);while(t–){scanf(“%d”,&n);init();for(i=1;i<n;i++){scanf(“%d%d”,&u,&v);add(u,v);add(v,u);deg[v]++;}for(i=1;i<=n;i++){if(!deg[i]){dfs(i,0,-1);break;}}st.init(n);scanf(“%d%d”,&u,&v);printf(“%d\n”,F[st.Query(fir[u],fir[v])]);}return 0;}
充满了恐惧的声音，一种不确定的归宿的流动。
