本文共 1287 字，大约阅读时间需要 4 分钟。

解决的问题：在一棵树上求u,v的最近公共祖先。

思路：预处理parents数组和depth数组，首先使u,v深度相同，一起向上迭代，直至找到相同父节点

/*倍增法求LCA*/#include
   
    #include
    
     #include
     
      #include
      
       using namespace std;#define N 100010vector
       
        G[N];int root,depth[N];/*根节点，节点深度*/int parents[N][25],from[N];/*parents[u][x]记录u的2^x祖先节点,from记录各个节点是否有父节点*/int n,m;void getdata()/*输入树*/{    int u,v;    memset(from,-1,sizeof(from));    scanf("%d",&n);    for(int i=1; i<=n-1; i++)    {        scanf("%d%d",&u,&v);        G[u].push_back(v);        from[v]=1;/*标记，寻找根节点*/        parents[v][0]=u;/*父节点*/    }    for(int i=1; i<=n; i++)        if(from[i]==-1) root=i;/*根节点*/}void get_depth()/*计算每一结点的深度*/{    queue
        
         q; q.push(root); while(!q.empty()) { int u=q.front(),v; q.pop(); for(int i=0; i
         
          =0; --j) /*使u上升与v同一高度*/ { if(depth[u]-(1<
          
           =depth[v])/*由大到小调节，总能等于v的深度*/ u=parents[u][j];/*向上跨越*/ } if(v!=u) { for(int j=i; j>=0; j--) /*一起迭代到最近的同一个祖宗*/ { if(parents[u][j]!=parents[v][j])/*相等说明跳的幅度大,j--*/ { u=parents[u][j]; v=parents[v][j]; } } u=parents[u][0];/*直到u,v的父亲节点相同*/ } printf("%d\n",depth[t1]-depth[u]+depth[t2]-depth[u]);}int main(){ getdata(); get_depth(); getparents(); int m,u,v; scanf("%d",&m); for(int i=1; i<=m; i++) { scanf("%d%d",&u,&v); LCA(u,v); } return 0;}