网站信息内容建设责任制落实情况,建德营销型网站建设,融资计划书,成都微信小程序定制开发公司LCA#xff08;Lowest Common Ancestor#xff09;
定义
在树上取两点 x,yx,y#xff0c;他们的 LCA 为距离他们最近的公共祖先。
本章主要讲的是倍增求 LCA。
暴力求取
从 xx 开始向上移动到根结点#xff0c;并标记沿途结点。从 yy 开始向上移动到根结点#xff0c…LCALowest Common Ancestor
定义
在树上取两点 x,yx,y他们的 LCA 为距离他们最近的公共祖先。
本章主要讲的是倍增求 LCA。
暴力求取
从 xx 开始向上移动到根结点并标记沿途结点。从 yy 开始向上移动到根结点第一个被标记的就是 xx 和 yy 的 LCA。
倍增求 LCA
从任意点对 (x,y)(x,y) 移到 xx 和 yy 的 LCA 的距离可拆分为 22 的幂的和。
若预处理任意点 xx 移动 22 的幂步所到达的结点编号则不超过 \log_2{n}log2n 次即可找到 LCA。
具体实现
first预处理倍增 DP
定义状态 dp_{i,j}dpi,j 表示点 ii 向上移动 2^j2j 步到达的结点编号。
状态转移方程枚举 jj 从 11 到 \log_2 nlog2ndp_{i,j}dp_{dp_{i,j-1},j-1}dpi,jdpdpi,j−1,j−1。
初始状态dp_{i,0}fa_idpi,0fai。
代码片段
void pre_lca(int cur, int fa)
{dep[cur]dep[fa]1;dp[cur][0]fa;for(int i1;(1i)dep[cur];i){dp[cur][i]dp[dp[cur][i-1]][i-1];}for(int nxt:nbr[cur]){if(nxt!fa)pre_lca(nxt,cur);}
}
second处理单次询问
第一步约定深度较大的点若 dep_xdep_ydepxdepy交换 xx 和 yy。
第二步将深度较大的结点 yy 倍增向上跳至深度等于 xx。
第三步判断 xx 是否等于 yy。若已经相等则 xx 为 LCA停止寻找。
第四步xx 和 yy 一起倍增向上跳只要 xx 和 yy 不重合。
第五步xx 向上一步即为 LCA。
代码片段
int lca(int x, int y)
{if(dep[y]dep[x])swap(x,y);for(int i20;i-1;i--){if(dep[dp[y][i]]dep[x]){ydp[y][i];}}if(xy)return x;for(int i20;i-1;i--){if(dp[x][i]!dp[y][i]){xdp[x][i],ydp[y][i];}}return dp[x][0];
}
时间复杂度
预处理是 O(n \log_2 n)O(nlog2n) 的中间单次求取仅为 O(n)O(n)
模板代码
#includebits/stdc.h
#define int long long
using namespace std;
int dp[500005][21],dep[500005], n, m, s;
vectorint nbr[500005];
void pre_lca(int cur, int fa)
{dep[cur]dep[fa]1;dp[cur][0]fa;for(int i1;(1i)dep[cur];i){dp[cur][i]dp[dp[cur][i-1]][i-1];}for(int nxt:nbr[cur]){if(nxt!fa)pre_lca(nxt,cur);}
}
int lca(int x, int y)
{if(dep[y]dep[x])swap(x,y);for(int i20;i-1;i--){if(dep[dp[y][i]]dep[x]){ydp[y][i];}}if(xy)return x;for(int i20;i-1;i--){if(dp[x][i]!dp[y][i]){xdp[x][i],ydp[y][i];}}return dp[x][0];
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0);cinnms;for(int i1;in;i){int x, y;cinxy;nbr[x].push_back(y);nbr[y].push_back(x);}pre_lca(s,0);for(int i1;im;i){int x, y;cinxy;coutlca(x,y)\n;}
}
LCA 应用
求树上两点之间距离。树上差分。
LCA 求树上两点之间距离
维护 dis_xdisx 表示根结点到 xx 的距离。
xx 到 yy 的简单路径的长度为 dis_xdis_y-2\times dis_{\texttt{lca}(x,y)}disxdisy−2×dislca(x,y)。
LCA 例题
firstP5836
方法 1
点权可以转为 00 或 11维护 dis_idisi 表示由根结点到 ii 的距离。
维护深度 dep_idepi对于每次询问若 (dis[a]dis[b]-2*dis[lcad]w[lcad]dep[a]dep[b]-2*dep[lcad]1)c!H 或 dis[a]dis[b]-2*dis[lcad]w[lcad]0cH 则输出 00否则输出 11。
方法 2
若一条边的两个端点的 ww 相同则 unionn 这两个端点。
若一条路径上点权相同则两个端点一定在同一集合。若该集合的权值不等于询问输出 00否则输出 11。
while(m--)
{int x, y;char c;cinxyc;if(cH){cout!(find(x)find(y)w[x]0);}else{cout!(find(x)find(y)w[x]1);}
}
方法 3
维护 dp_{i,j}dpi,j 表示 ii 向上动 2^j2j 步到达的结点编号维护 yes_{i,j,0/1}yesi,j,0/1 表示 ii 向上跳 2^j2j 步是否有 ww 为 0/10/1 的点。
yes[cur][i][0]yes[cur][i-1][0]|yes[dp[cur][i-1]][i-1][0],yes[cur][i][1]yes[cur][i-1][1]|yes[dp[cur][i-1]][i-1][1];。
初始状态dp_{i,0}fa_idpi,0faiyes_{i,0,w_{fa}}1yesi,0,wfa1。
secondCF519E
若 AA 到 BB 的距离为奇数则答案直接为 00。
否则分情况讨论 中间位置的点 xlcaxlca xx 儿子结点中包含 AA 和 BB 的子树剔除其余为答案。 中间位置的点 xx 不是 lcalca 约定深度较大的点为 BB找到 BB 向上距离 xx 一步的点 pp则答案为 size_x-size_psizex−sizep。
注意特殊情况ABAB 时答案为 nn。
从 lcalca 到 xx 的距离为 \frac{dep_B-dep_A}{2}2depB−depA。
void work(int x,int y)
{if(xy){coutn\n;return ;}if(dep[x]dep[y]){for(int i14;i0;i--){if(dp[x][i]!dp[y][i]){xdp[x][i],ydp[y][i];}}coutsize[1]-size[x]-size[y]\n;return ;}if(dep[x]dep[y]) swap(x,y);if((dep[x]-dep[y])%21){cout0\n;return ;}int x2x,len(dep[x]-dep[y])/2;for(int i14;i0;i--){if(dep[dp[x][i]]dep[y]){xdp[x][i];}}if(xy){lendep[x];for(int i14;i0;i--){if(dep[dp[x2][i]]len){x2dp[x2][i];}}coutsize[dp[x2][0]]-size[x2]\n;return ;}for(int i14;i0;i--){if(dp[x][i]!dp[y][i]){xdp[x][i],ydp[y][i];}}lendep[x]-1;for(int i14;i0;i--){if(dep[dp[x2][i]]len){x2dp[x2][i];}}coutsize[dp[x2][0]]-size[x2]\n;
}
ThirdP8972 一切都已过去
见 题解P8972 『GROI-R1』 一切都已过去 - 洛谷专栏
方便阅读搬过来。
从数据范围很容易发现如果我们把边权累乘再判整数炸掉是必然的这时候我们来发现一个性质只有小数部分有 22 和 55 相乘的时候才可能变成整数。当然这并不是绝对的例如 2.02 \times 52.02×5 就不是整数。从上面举的例子很容易发现一个性质两个实数的乘积是否为整数与小数点数位也有关系。一对 22 和 55 可以抵消掉一个小数点数位22 和 55 可以在任意且不同数位上并且 22 和 55 的倍数也有用。这时我们可以将边权通过不断 \times 10×10 变成整数并分解质因数分别求因数中 22 和 55 的个数点权也要处理。22 和 55 的个数求出来了小数点数位也很好处理。最终的小数点位数应该是所有路径上的边权小数点位数之和所以我们在将边权化整数时再维护一个变量统计小数点位数并记录到邻接矩阵里。若路径 xx 到 yy 的总边权乘上 xx 的点权得到的结果中 22 的个数和 55 的个数大于或等于总小数点位数则其为整数。分别维护即可。
注意若边权或点权为 00 则对应维护的当前点权或点权的 22 和 55 赋予极大值。 Latex有双倍问题完整版请在安全访问中心 - 洛谷查看
