虚树

虚树

2018第一篇博客啦啦啦!!!

虚树可以处理一些树上的问题中有一些关键点,并且所有询问的点数之和不是很大的问题。

 \sum{cnt_i}_{i=1}^{n}=m

对于每一个询问,将询问点按照dfs序排序,那么所有相邻两个点的LCA的集合便是两两点对的LCA的集合。因为LCA(x,z)一定是LCA(x,y)LCA(y,z)

把询问点以及所有的LCA叫作关键点。

然后有些与计数等等有关的题可能还要加上根节点,方便起见,就每次都加入根节点。

那么所有关键点的个数总和是 O(m) 的。

点全都处理好了,接下来就是建边了。

将关键点以及LCA一起按照dfs序排序。

用一个栈维护根节点到当前关键点的一条链。

维护就是若栈顶不是当前点的祖先就出栈,直到栈顶是当前点的祖先。

怎么判断是不是当前点的祖先呢,可以用dfs序中的入栈以及出栈时间戳,但我直接用LCA,因为前面处理关键点就已经 O(nlgn) 了,渐进复杂度没区别的。(好吧是我懒,懒得写出栈时间戳,虽然就两句话)

然后栈顶元素向当前点连一条边,边权……不同的题都不同的,所以就要发挥你的聪明才智了。

还有一点就是边表要重复使用,不能每次全清空。

模板(每次询问)

 

虚树
Tagged on:     

发表评论

电子邮件地址不会被公开。 必填项已用*标注