[模板] - LCA倍增

成员：

const int maxn = 1007; int up[maxn][32];//倍增数组 int depth[maxn];//每个点在树中的深度 int n,m;//n个点，m条边 bool vis[maxn]; vector<int> tree[maxn];//邻接表

---

函数：

DFS记录深度和初始化倍增数组：

//记录各节点i的深度depth[i]，dfs一遍即可O(N) void dfs(int u, int d) { depth[u] = d; vis[u] = true; for(auto i : tree[u]) if(!vis[i]) { dfs(i, d+1); up[i][0] = u; } }

处理倍增数组：

/* 预处理出倍增数组，father[i][j]表示节点i往上(往根的方向)跳2^j步的祖先标号。 -1表示不存在，也就是跳过根了。father[i][0]是节点i的父节点标号。 */ void process() { for(int j=1 ; j<31 ; j++) for(int i=1 ; i<=n ; i++) if(up[i][j-1]!=-1) up[i][j] = up[up[i][j-1]][j-1]; }

LCA函数实现：

/* 对于点对(u,v)，设depth[u]>depth[v]，此时将u往上跳到和v在同一深度 u,v在同一深度时有两种情况 1.v本来就是u的祖先，lca(u,v) = v，直接return v; 2.v不是u的祖先，两个点一起向上，每条一次都是前一次的至多一半。停下来的位置是他们俩lca的子节点，所以return up[u][0]; */ int lca(int u, int v) { if(depth[u] < depth[v]) swap(u,v); int tmp = depth[u] - depth[v]; for(int j = 0 ; j <= 30 && depth[u] != depth[v] ; j++) { if(tmp&(1<<j)) u = up[u][j]; } if(u == v) return v; for(int j = 30 ; j>=0 ; j--) { if(up[u][j] != up[v][j]) u = up[u][j], v = up[v][j]; } return up[u][0]; }

汇总：

const int maxn = 1007; int up[maxn][32];//倍增数组 int depth[maxn];//每个点在树中的深度 int n,m;//n个点，m条边 bool vis[maxn]; vector<int> tree[maxn];//邻接表 void dfs(int u, int d) { depth[u] = d; vis[u] = true; for(auto i : tree[u]) if(!vis[i]) { dfs(i, d+1); up[i][0] = u; } } void process() { for(int j=1 ; j<31 ; j++) for(int i=1 ; i<=n ; i++) if(up[i][j-1]!=-1) up[i][j] = up[up[i][j-1]][j-1]; } int lca(int u, int v) { if(depth[u] < depth[v]) swap(u,v); int tmp = depth[u] - depth[v]; for(int j = 0 ; j <= 30 && depth[u] != depth[v] ; j++) { if(tmp&(1<<j)) u = up[u][j]; } if(u == v) return v; for(int j = 30 ; j>=0 ; j--) { if(up[u][j] != up[v][j]) u = up[u][j], v = up[v][j]; } return up[u][0]; }