倍增求最近公共祖先，实际上是对暴力的优化（向上标记法）
我们来看看向上标记法的实现：
//预处理每个结点的深度，以及结点的父结点的编号 void dfs(int u, int father){ depth[u]=depth[father]+1; fa[u]=father; for(int i=h[u];~i;i=ne[i]){ int v=e[i]; if(v!=father) dfs(v,u); } } //求u和v的公共祖先 int getlca(int u,int v){ //只要u和v不同 while(u!=v){ //将深度大的结点向上移动 if(depth[u]<depth[v]) v=fa[v]; else u=fa[u]; } return u; }
dfs处理出询问节点a，b到根节点的父亲节点，然后按深度高低向上一步一步找a,b的第一个相同的祖先节点。
我们完全没有必要一步一步来，每次查询时间复杂度为O(n),m次查询就是O(nm)，时间复杂度炸裂。对！不一步一步来，我们几步几步来。我们走的步数可以通过倍增来枚举，因为我们的步数本质上可以由二进制划分来组成（利用任意一个数能由若干个2的次幂项组成！例如7 = 2 0 + 2 1 + 2 2 7=2^0+2^1+2^27=20+21+22,注意我们往上走不能反悔，所以要将步数的2的次幂项从大到小枚举。这个处理之后处理的时间复杂度为O ( n l o g n ) O(nlogn)O(nlogn),每次在线查询LCA的时间复杂度为O ( l o g n ) O(logn)O(logn)
注意设置的哨兵，简化维护的代码量：dep[0]=0;,dep[root]=1,fa数组初始化为0。
离线查询看:tarjan算法维护LCA（O(n+q))
#include <bits/stdc++.h> using namespace std; const int N = 4e4 + 10; vector<int>g[N]; int fa[N][16];//4e4数据2^15差不多了 int dep[N]; void bfs(int root)//用dfs，bfs都行，用bfs防止爆栈 { memset(dep, 0x3f, sizeof(dep)); dep[root] = 1; dep[0] = 0;//设置哨兵 queue<int>q; q.push(root); while (q.size()) { int t = q.front(); q.pop(); for (auto x : g[t]) { if (dep[x] > dep[t] + 1) { dep[x] = dep[t] + 1; q.push(x); fa[x][0] = t; for (int i = 1; i<=15; i++) { fa[x][i] = fa[fa[x][i - 1]][i - 1]; } } } } } int lca(int x, int y) { if (dep[x] < dep[y]) swap(x, y); for (int i = 15; i >= 0; i--) { if (dep[fa[x][i]] >= dep[y]) { x = fa[x][i]; } } if (x == y) return x; for (int i = 15; i >= 0; i--) { if (fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; } int main() { int n, m; cin >> n ; int root = -1; for (int i = 1; i <= n; i++) { int x, y; cin >> x >> y; if (y == -1) { root = x; } else { g[x].push_back(y); g[y].push_back(x); } } bfs(root); cin >> m; for (int i = 1; i <= m; i++) { int x, y; cin >> x >> y; int t = lca(x, y); if (t == x) { cout << 1 << endl; } else if (t == y) { cout << 2 << endl; } else { cout << 0 << endl; } } return 0; }
点个赞吧~
