首页 > 代码库 > dfs序
dfs序
dfs序比较重要的性质:一棵子树的所有节点在dfs序里是连续一段,主要就是利用这个性质来解题
题型一:对某个点X权值加上一个数W,查询某个子树X里所有点权值和。
解:列出dfs序,实现修改一个数,查询一段序列的和,显然这个序列可以用线段树维护。
题型二:对X到Y的最短路上所有点权值加上一个数W,查询某个点的权值。
解:并没有找到该类型的题目。。。。假设有这种题目吧。。若X到Y上的点的权值都加上W,那么其实就是X到根的权值加上W,Y到根的点权值加上W,lca(X,Y)到根的权值 减去W,parent(lca(X,Y))到根的点权值减去W。
dfs序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。