文章目录

最近公共祖先算法算法1.向上标记算法 时间复杂度O(n)算法2.倍增算法算法3. Tarjan算法 时间复杂度 O（n+m）//离线做法

最近公共祖先算法

算法1.向上标记算法 时间复杂度O(n)

两个节点分别向上标记 找出第一个同时标记的点 就是他们的最近公共祖先 代码实现略（太简单）

算法2.倍增算法

倍增是对向上标记算法的一个优化 向上标记的过程中 我们可以使用倍增思想加速 跳的过程

代码如下：

#include <iostream> #include <algorithm> #include <cstdio> #include <string> #include <cstring> #include <queue> using namespace std; const int N = 4e5+10; int f[N][30]; //f[i][j] 表示从i开始跳 2^j 可以跳到的点 f[i][j] = f[f[i][j-1]][j-1]; int depth[N]; int root; int h[N],e[N],ne[N],idx; int n,m; void add(int a,int b) { e[idx] = b,ne[idx] = h[a],h[a] = idx++; } //bfs求出 f数组 void bfs(int a) { queue<int> q; q.push(a); f[a][0] = 0; depth[a] = 1; while(q.size()) { int u = q.front(); q.pop(); for(int i=h[u];~i;i=ne[i]) { int j = e[i]; if(j==u)continue; if(depth[j])continue; depth[j] = depth[u] + 1; f[j][0] = u; //简单dp for(int k=1;k<=15;k++) f[j][k] = f[f[j][k-1]][k-1]; q.push(j); } } } int lca(int a,int b) { if(depth[a]<depth[b])swap(a,b); //把a跳到和b同一高度 for(int k=15;k>=0;k--) if(depth[f[a][k]] >= depth[b]) { a = f[a][k]; } //如果a==b直接返回a或者b if(a==b) return b; //如果不相同 那么两个人同时向上跳 直到找到第一次相同的点 for(int k=15;k>=0;k--) if(f[a][k]!=f[b][k]) { a = f[a][k]; b = f[b][k]; } return f[a][0]; } int main() { memset(h,-1,sizeof h); cin>>n; int a,b; for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); if(b==-1)root = a; else add(a,b),add(b,a); } bfs(root); cin>>m; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); int t = lca(a,b); if(t==a)cout<<1<<endl; else if(t==b)cout<<2<<endl; else cout<<0<<endl; } return 0; }

算法3. Tarjan算法 时间复杂度 O（n+m）//离线做法

对先前的dfs的经验进行 利用

代码如下：

//树上任意两点距离 //定义 d[i] 为 i 到 1 的距离 //dist[a][b](a到b的距离) = d[a] + d[b] - 2*d[anc] //anc 为a和b的最近公共祖先 #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <queue> #include <cstdio> using namespace std; const int N = 1e5; int h[N],e[N],ne[N],val[N],idx; int d[N];//i到1 的距离 int ans[N];//保存每一个询问的值 int st[N];//tarjan中的标记数组 int f[N];//并查集数组 int n,m; vector<pair<int,int>> q[N];//保存询问 first为另一个点 second为查询的序号 void add(int a,int b,int c) { e[idx] = b,ne[idx] = h[a],val[idx] = c,h[a] = idx++; } int find(int x) { return f[x]==x?x:f[x] = find(f[x]); } void dfs(int u,int fa) { for(int i=h[u];~i;i=ne[i]) { int j = e[i]; if(j==fa)continue; d[j] = d[u] + val[i]; dfs(j,u); } } void tarjan(int u) { //把当前点标记为1 表示正在dfs中 st[u] = 1; //遍历u的儿子 for(int i=h[u];~i;i=ne[i]) { int j = e[i]; if(st[j])continue; tarjan(j); f[j] = u;//把它并入 父节点中 } for(auto t:q[u]) { int a = u; int b = t.first; //如果b已经进行dfs了 if(st[b]==2) { int anc = find(b); ans[t.second] = d[a] + d[b] - 2*d[anc]; } } //b已经完成dfs 标记为2 st[u] = 2; } int main() { memset(h,-1,sizeof h); cin>>n>>m; int a,b,c; for(int i=1;i<=n-1;i++) { scanf("%d%d%d",&a,&b,&c); add(a,b,c),add(b,a,c); } for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); q[a].push_back({b,i}); q[b].push_back({a,i}); } //初始化并查集 for(int i=1;i<=n;i++) f[i] = i; dfs(1,-1); tarjan(1); for(int i=1;i<=m;i++) cout<<ans[i]<<endl; return 0; }