<style type="text/css">
<!--
@page
{margin:2cm}
h3
{margin-bottom:0.21cm;
direction:ltr;
color:#000000;
text-align:justify;
widows:0;
orphans:0}
h3.western
{font-family:"Liberation Serif","Times New Roman",serif}
h3.cjk
{font-family:"Droid Sans Fallback"}
h3.ctl
{font-family:"Lohit Hindi"}
p
{margin-bottom:0.21cm;
direction:ltr;
color:#000000;
text-align:justify;
widows:0;
orphans:0}
p.western
{font-family:"Times New Roman",serif;
font-size:10pt}
p.cjk
{font-family:"宋体","SimSun";
font-size:10pt}
p.ctl
{font-family:"Times New Roman",serif;
font-size:12pt}
-->
</style>
LCA是用来求解一棵树或图中两点的最近公共祖先
LCA(Least Common Ancestor),顾名思义,是指在一棵树中,距离两个点最近的两者的公共节点。也就是说,在两个点通往根的道路上,肯定会有公共的节点,我们就是要求找到公共的节点中,深度尽量深的点。还可以表示成另一种说法,就是如果把树看成是一个图,这找到这两个点中的最短距离。
1:如果读入的树,那么应该有固定的根节点我们只要对根节点LCA即可。
2:如果读入的是无向图,那么选择1作为根节点进行LCA即可。
所以应该要注意题目读入的是树还是无向图,已经的根节点是否固定。
1Tarjan离线算法
1:Tarjan算法基于深度优先搜索的框架,对于新搜索到的一个结点,首先创建由这个结点构成的集合,用到dfs+并查集
2:再对当前结点的每一个子树进行搜索,每搜索完一棵子树,则可确定子树内的LCA询问都已解决。
3:其他的LCA询问的结果必然在这个子树之外,这时把子树所形成的集合与当前结点的集合合并,并将当前结点设为这个集合的祖先。
4:之后继续搜索下一棵子树,直到当前结点的所有子树搜索完。
5:这时把当前结点也设为已被检查过的,同时可以处理有关当前结点的LCA询问,如果有一个从当前结点到结点v的询问,且v已被检查过,则由于进行的是深度优先搜索,当前结点与v的最近公共祖先一定还没有被检查,而这个最近公共祖先的包涵v的子树一定已经搜索过了,那么这个最近公共祖先一定是v所在集合的祖先。
举例说明(非证明):
假设遍历完10的孩子,要处理关于10的请求了
取根节点到当前正在遍历的节点的路径为关键路径,即1-3-8-10
集合的祖先便是关键路径上距离集合最近的点
比如此时:
1,2,5,6为一个集合,祖先为1,集合中点和10的LCA为1
3,7为一个集合,祖先为3,集合中点和10的LCA为3
8,9,11为一个集合,祖先为8,集合中点和10的LCA为8
10,12为一个集合,祖先为10,集合中点和10的LCA为10
你看,集合的祖先便是LCA吧,所以第3步是正确的
道理很简单,LCA(u,v)便是根至u的路径上到节点v最近的点
6时间复杂度o(n+m);n是数据规模,m是询问的次数,核心如下
/*这个u是根节点*/
void LCA(int u){
ancestor[u] = u;/*建立一个集合*/
for(int i = first[u] ; i != -1 ; i = next[i]){
LCA(i);
union_Set(i , u);
ancestor[find_Set(i)] = u;
}
vis[u] = 1;/*把这个点标记为已经求过和它有关的LCA问题都可以知道*/
for(int i = 0 ; i < v[u].size() ; i++){
if(vis[v[u][i]]){
int tmp = father[find_Set(v[u][i])];
for(int j = 0 ; j < m ; j++){/*找到是那一条边询问*/
if(e[j].x == u && e[j].y == v[u][i] || e[j].y == u && e[j].x == v[u][i])
e[j].ans = tmp;
}
}
}
}
分享到:
相关推荐
LCA 详解以及完整代码详细介绍了倍增法的原理以及Pascal的完整代码 很好很强大
LCA词汇复杂度分析软件 跟官网一毛一样 可以做成本地接口
日立LCA电气图纸(K3500490).pdf
RMQ与LCA ACM必备RMQ与LCA ACM必备 RMQ与LCA ACM必备
LCA51软件是AEDK系列仿真机的调试软件。软件支持AEDK所有系列的51类新型号仿真机,包括AEDK51HB、AEDK51I、AEDK51W、AEDK320W仿真机,AEDK5196(N)仿真机的51配置方式。对于各种型号仿真机,软件功能上会稍有不同,...
LCA Tarjan: 实现原理 理解:离线算法,建好树后再查询,一次DFS 吧所有查询解决完。 时间复杂度:O(n+q); n个点 q次询问 补一下:链式向前星,并查集 ,Tarjan 代码 #include #include #include #include #...
对于LCA问题,有不少解法,这儿提供了tarjan算法,这是一种离线算法,读入所有输入然后一并处理,并且利用并查集的思想,从根节点开始DFS,对每一个DFS的节点,先把他的父亲节点指向本身,没访问完一个子节点,然后...
用户数据的读取方法,如何对LCA265显示器传输数据。
关于RMQ和LCA的关系的知识,如何用RMQ和LCA的转换
c++写的Tarjan 的 LCA 算法,最近公共祖先算法,可供算法学习参考
LCA生命周期评价,LCA生命周期评价课件,LCA生命周期评价PPT
基于LCA的玻璃纤维产品碳排放评价模型,韩乐,,玻璃纤维产品属于高能耗产品,在溶制的过程中有大量的温室气体排放。本文在对玻璃纤维产品生命周期研究的基础上,根据其碳排放特
基于某煤化工企业的现场调研和台账数据,运用生命周期评价(LCA)的基本方法,对煤炭开采加工过程、运输过程,煤制油过程等主要环节中能源消耗和污染物排量进行统计分析,并进行环境影响识别,分析整个过程中的主要污染环节...
SAS+proc lca浅类别分析安装程序
LCA系统中的数据状态控制以及数据升版操作规范
lca51仿真软件早期版本2.02版,不知是否有需要的。
郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 郭华阳《RMQ与LCA问题》 国家队论文
LCA 中文教程,内部资料--产品结构管理,还不错啊,可以看下
一个很经典的论文,关于slca的论文,现在关于查询方面的知识,好多都是基于slca的
OSRAM_LED_LCA_Summary_November_2009