LCA 在线倍增法 求最近公共祖先
2024-09-08 02:57:10
第一步:建树 这个就不说了
第二部:分为两步 分别是深度预处理和祖先DP预处理
DP预处理:
int i,j;
for(j=;(<<j)<n;j++)
for(int i=;i<n;++i)
if(fa[i][j]=-)
fa[i][j]=fa[fa[i][j-]][j-];/*DP处理出i的2^j祖先是谁*/
深度预处理:
void dfs(int now,int from,int deepth)
{
deep[now]=deepth;
for(int i=head[now];i;i=e[i].pre)
if(e[i].v!=from)
dfs(e[i].v,now,deepth+);
}
第三部分:LCA核心
int LCA(int a,int b)// 求a、b的最近公共祖先
{
int i,j;
if(deep[a]<deep[b]) swap(a,b); // 保证a的深度比b大这样便于操作
for(i=;(<<i)<=deep[a];++i);// (1<<i) 等同于2的i次方
i--;
for(j=i;j>=;j--)
if((deep[a]-(<<j))>=deep[b])// 让a节点往上蹦 直到a、b晚上一蹦就重合
a=fa[a][j];
if(a==b)return a;// 如果a的一个祖先恰好是b
for(j=i;j>=;j--)
if(fa[a][j]!=-&&fa[a][j]!=fa[b][j])// 没有越界并且祖先不同 那么就让a,b同时往上蹦
{
a=fa[a][j];
b=fa[b][j];
}
return fa[a][];
}
默写的代码:
void DP {
int i,j;
for(int j=; (<<j)<n; j++) {
for(int i=; i<n; i++)
if(fa[i][j]=-)
fa[i][j]=fa[fa[i][j-]][j-];
}
}
void dfs(int now,int deepth,int from) {
deep[now]=deepth;
for(int i=head[now]; i; i=e[i].next) {
if(e[i].v!=from) {
dfs(e[i].v,deepth+,now);
}
}
}
int LCA(int a,int b) {
int i,j;
if(deep[a]<deep[b]) swap(a,b);
for(i=; (<<i)<=deep[a]; i++);
i--;
for(j=i; j>=; j--) {
if(deep[a]-(<<j)>=deep[b])
a=fa[a][j];
}
if(a==b) return a;
for(j=i; j>=; j--) {
if(fa[a][j]!=-&&fa[a][j]!=fa[b][j]) {
a=fa[a][j];
b=fa[b][j];
}
}
return fa[a][];
}
最新文章
- QNetworkAccessManager 实现的 ftp 上传
- Qt opencv程序运行异常
- RAILS局部视图操作样例
- 深入了解session
- ceph之Placement Group
- android 4.2 root
- 常用典型的sql语句
- win10 家庭版不支持gpedit.msc的解决办法
- docker不能上传镜像到自己网站的仓库
- 第八单元 正文处理命令及tar命令
- Using Java in Debian
- vue教程3-02 vue动画
- javascript面向对象的常见写法与优缺点
- UVA-11761-马尔可夫/记忆化搜索
- 解决 PHP Fatal error: Call-time pass-by-reference has been removed
- Windows快捷键命令
- 第六天 vim编辑的使用和Xmanager远程工具的使用
- centos静默安装oracle12c
- java 实验四
- 【C++对象模型】第五章 构造、解构、拷贝 语意学
热门文章
- A8ERP管理系统(采购单管理)
- Android设计模式——MVP
- 014、BOM与DOM对象的应用
- java实现课堂随机点名小程序
- java 之 插入排序
- (转)Spring4.2.5+Hibernate4.3.11+Struts1.3.8集成方案一
- Django 路由 —— Djangon如何处理一个请求
- k8s集群之Docker安装镜像加速器配置与k8s容器网络
- Must set property &#39;expression&#39; before attempting to match
- MySQL-03 SQL语句设计