首页 > 代码库 > tarjan解决路径询问问题
tarjan解决路径询问问题
好久没更新了，就更一篇普及组内容好了。
首先我们考虑如何用tarjan离线求出lca，伪代码大致如下：
def tarjan(x): 将x标记为已访问 for c in x的孩子: tarjan(c) 将c所在并查集的父亲置为x for q in 关于x的询问: y=询问q除了x外的另一个端点 if y已访问: q的答案=y所在并查集的根
这样为什么是对的呢？考虑lca肯定是先搜到y，再搜到x，因为此时lca还没有做完，所以此时并查集的根就是lca，而且y已经和lca并在一起了，所以会询问到正确的结果。
现在我们要用tarjan来解决路径询问问题，例如每条边有边权，若干次询问，询问路径上的边权和。
首先我们要在并查集上动一些手脚，原来并查集只是用来查询祖先，我们在并查集每个点上记一个额外信息，为这个点到并查集根的信息，在本题中即为该点到根的边权和。在查询祖先时我们可以顺便更新这个信息。
查出lca时我们把这个询问扔进lca，把它称作“延迟询问”，回到lca的时候遍历所有延迟询问，这时候x和y在并查集中的祖先都是lca，直接合并信息即可。
ff=一个初始为0的数组储存并查集 info=一个初始为空的数组储存信息 def find(x): if !ff[x]: return x y=ff[x] ff[x]=find(y) info[x]=info[x]+info[y] return ff[x]def tarjan2(x): 将x标记为已访问 for c in x的孩子: tarjan2(c) ff[c]=x info[c]=c到x的边的信息 for q in 关于x的询问: y=询问q除了x外的另一个端点 if y已访问: q的lca=y所在并查集的根 在q的lca处插入延迟询问q for q in x为lca的延迟询问： (a,b)=该询问的两个端点 find(a) find(b) q的询问结果=info[a]+info[b]
tarjan解决路径询问问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。