首页 > 代码库 > 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序