1、输入树中的节点数N，输入树中的N-1条边。最后输入2个点，输出它们的最近公共祖先。

2、裸的最近公共祖先。

3、

dfs+ST在线算法：

/*LCA(POJ 1330)在线算法 DFS+ST*/#include
      
       #include
       
        #include
        
         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<
         
          <=n;i++)            dp[i][j]=rmq[dp[i][j-1]]
          
           <<(j-1))][j-1]]?dp[i][j-1]:dp[i+(1<<(j-1))][j-1];    }    //查询[a,b]之间最小值的下标    int query(int a,int b){        if(a>b)swap(a,b);        int k=mm[b-a+1];        return rmq[dp[a][k]]<=rmq[dp[b-(1<
           
            <
           
          
         
        
       
      

 

LCA倍增法：

/*POJ 1330LCA在线算法*/#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int MAXN=10010;const int DEG=20;struct Edge{    int to,next;}edge[MAXN*2];int head[MAXN],tot;void addedge(int u,int v){    edge[tot].to=v;    edge[tot].next=head[u];    head[u]=tot++;}void init(){    tot=0;    memset(head,-1,sizeof(head));}int fa[MAXN][DEG];//fa[i][j]表示结点i的第2^j个祖先int deg[MAXN];//深度数组void BFS(int root){    queue
          
           que;    deg[root]=0;    fa[root][0]=root;    que.push(root);    while(!que.empty()){        int tmp=que.front();        que.pop();        for(int i=1;i
           
            deg[v])swap(u,v); int hu=deg[u],hv=deg[v]; int tu=u,tv=v; for(int det=hv-hu,i=0;det;det>>=1,i++) if(det&1) tv=fa[tv][i]; if(tu==tv)return tu; for(int i=DEG-1;i>=0;i--){ if(fa[tu][i]==fa[tv][i]) continue; tu=fa[tu][i]; tv=fa[tv][i]; } return fa[tu][0];}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