[模板] - 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<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<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];
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！