网站系统分析的主要任务包括,网站排名软件 利搜,餐饮装修公司,做网站怎样投放广告定义
最近公共祖先简称 LCA#xff08;Lowest Common Ancestor#xff09;。两个节点的最近公共祖先#xff0c;就是这两个点的公共祖先里面#xff0c;离根最远的那个。
性质
如果 不为 的祖先并且 不为 的祖先#xff0c;那么 分别处于 的两棵不同子树中#…定义
最近公共祖先简称 LCALowest Common Ancestor。两个节点的最近公共祖先就是这两个点的公共祖先里面离根最远的那个。
性质
如果 不为 的祖先并且 不为 的祖先那么 分别处于 的两棵不同子树中前序遍历中 出现在所有 中元素之前后序遍历中 则出现在所有 中元素之后两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先即 两点的最近公共祖先必定处在树上两点间的最短路
倍增算法
过程
倍增算法是最经典的 LCA 求法他是朴素算法的改进算法。通过预处理 数组游标可以快速移动大幅减少了游标跳转次数。 表示点 的第 个祖先。 数组可以通过 dfs 预处理出来。
现在我们看看如何优化这些跳转 在调整游标的第一阶段中我们要将 两点跳转到同一深度。我们可以计算出 两点的深度之差设其为 。通过将 进行二进制拆分我们将 次游标跳转优化为「 的二进制表示所含 1 的个数」次游标跳转。 在第二阶段中我们从最大的 开始循环尝试一直尝试到 包括 如果 则 那么最后的 LCA 为 。
性质
倍增算法的预处理时间复杂度为 单次查询时间复杂度为 。 另外倍增算法可以通过交换 fa 数组的两维使较小维放在前面。这样可以减少 cache miss 次数提高程序效率。
例题 可先求出 LCA再结合性质 进行解答。也可以直接在求 LCA 时求出结果。
参考代码 #include cstdio
#include cstring
#include iostream
#include vector
#define MXN 50007
using namespace std;
std::vectorint v[MXN];
std::vectorint w[MXN];int fa[MXN][31], cost[MXN][31], dep[MXN];
int n, m;
int a, b, c;// dfs用来为 lca 算法做准备。接受两个参数dfs 起始节点和它的父亲节点。
void dfs(int root, int fno) {// 初始化第 2^0 1 个祖先就是它的父亲节点dep 也比父亲节点多 1。fa[root][0] fno;dep[root] dep[fa[root][0]] 1;// 初始化其他的祖先节点第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第// 2^(i-1) 的祖先节点。for (int i 1; i 31; i) {fa[root][i] fa[fa[root][i - 1]][i - 1];cost[root][i] cost[fa[root][i - 1]][i - 1] cost[root][i - 1];}// 遍历子节点来进行 dfs。int sz v[root].size();for (int i 0; i sz; i) {if (v[root][i] fno) continue;cost[v[root][i]][0] w[root][i];dfs(v[root][i], root);}
}// lca。用倍增算法算取 x 和 y 的 lca 节点。
int lca(int x, int y) {// 令 y 比 x 深。if (dep[x] dep[y]) swap(x, y);// 令 y 和 x 在一个深度。int tmp dep[y] - dep[x], ans 0;for (int j 0; tmp; j, tmp 1)if (tmp 1) ans cost[y][j], y fa[y][j];// 如果这个时候 y x那么 xy 就都是它们自己的祖先。if (y x) return ans;// 不然的话找到第一个不是它们祖先的两个点。for (int j 30; j 0 y ! x; --j) {if (fa[x][j] ! fa[y][j]) {ans cost[x][j] cost[y][j];x fa[x][j];y fa[y][j];}}// 返回结果。ans cost[x][0] cost[y][0];return ans;
}int main() {// 初始化表示祖先的数组 fa代价 cost 和深度 dep。memset(fa, 0, sizeof(fa));memset(cost, 0, sizeof(cost));memset(dep, 0, sizeof(dep));// 读入树节点数一共有 n 个。scanf(%d, n);for (int i 1; i n; i) {scanf(%d %d %d, a, b, c);a, b;v[a].push_back(b);v[b].push_back(a);w[a].push_back(c);w[b].push_back(c);}// 为了计算 lca 而使用 dfs。dfs(1, 0);// 查询 m 次每一次查找两个节点的 lca 点。scanf(%d, m);for (int i 0; i m; i) {scanf(%d %d, a, b);a, b;printf(%d\n, lca(a, b));}return 0;
}
