首页 > 其他 > 详细

[模板] 虚树

时间:2018-10-18 17:42:52      阅读:172      评论:0      收藏:0      [点我收藏+]

目的

解决树上多组关于某些点的询问,复杂度是关于每次询问点的个数的和的

思路

把每次询问的点和某些lca(即关键点)浓缩到虚树上,两点之间的连边包含原树中两点间路径的信息,再在虚树上暴力(?)处理

做法

先按照dfs序排序,这样可以保证做到不在某点子树中的点时,它的子树中的点都已经做完了

用一个栈来记录从虚树根到当前做到的点的链。虽然树根是谁都行,但方便起见直接给成1,并把1和第一个点压入栈中

现在新加入一个点p,设栈顶元素是x,p和x的最近公共祖先是lca

有两种情况(lca绝对不会等于p来着,因为是按dfs序做的):

1.lca=x,直接把p压入栈中

2.lca!=x

  这说明lca在x的上面,而且x的子树已经做完了,我们要在栈中找到一个合适的位置把lca放下来,再把x连到一个合适的点上,再把x踢掉,再把p加进去

  循环地来做,设栈顶下面的元素是y,如果:

    1.dfn[y]>dfn[lca],即lca在y上面,那给y和x连边,然后踢了x继续做

    2.dfn[y]=dfn[lca],那么lca已经在虚树中有了,给y和x连边,踢了x然后break就行了

    3.dfn[y]<dfn[lca],说明lca在y下面,那就要给y,x连边,踢了x以后把lca压进去,再break

  最后把p也压到栈里。注意连边的时候把路径信息也记到边上

然后在建出的虚树上乱搞就可以了。注意由于询问数很多,万万不可memset,需要清空什么东西的时候怎么加进来就怎么减回去好了。清空虚树的边的话可以dfs一下

例题以后再补

[模板] 虚树

原文:https://www.cnblogs.com/Ressed/p/9811784.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!