324 最近公共祖先 倍增算法

本文主要是介绍324 最近公共祖先 倍增算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

视频链接：

// P3379 【模板】最近公共祖先（LCA）
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N=5e5+10; 
int n,m,s,a,b;
vector<int> e[N];
int dep[N],fa[N][20];

void dfs(int u, int father){
  dep[u]=dep[father]+1;
  // 向上跳1,2,4...步的祖先节点
  fa[u][0]=father;
  for(int i=1; i<=19; i++) 
    fa[u][i]=fa[fa[u][i-1]][i-1]; 
    
  for(int v : e[u])
    if(v!=father) dfs(v, u);
}
int lca(int u, int v){
  if(dep[u]<dep[v])swap(u, v);
  // 先跳到同一层
  for(int i=19; i>=0; i--)
    if(dep[fa[u][i]]>=dep[v])
      u=fa[u][i];
  if(u==v) return v;
  // 再跳到LCA的下一层
  for(int i=19; i>=0; i--)
    if(fa[u][i]!=fa[v][i])
      u=fa[u][i], v=fa[v][i];
  return fa[u][0];
}
int main(){
  scanf("%d%d%d", &n,&m,&s);
  for(int i=1; i<n; i++){
    scanf("%d%d",&a,&b);
    e[a].push_back(b);
    e[b].push_back(a);
  }
  dfs(s, 0);
  while(m--){
    scanf("%d%d", &a, &b);
    printf("%d\n",lca(a, b));
  }
  return 0;
}

这篇关于324 最近公共祖先 倍增算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！