【算法】虚树学习笔记

Author Avatar
Sakits 3月 31, 2018

简介

  最近简单地学了一下虚树,做做学习笔记…
  虚树是将原树上询问所需的点取出后新建的一棵树。设询问次数为qq次,询问总点数为mm,用新建的虚树来处理询问可以将复杂度从O(nq)O(nq)降低到O(m)O(m)
  一般用来写给定一棵树,每次询问一堆点的题…

虚树的构造

  先跑出原树上所有点的dfs序,对于一个询问的点,按dfn序排序。
  维护一个栈,保存即将插入虚树上的一条链。假设现在要把新的点xx加入虚树,设栈顶为pp,栈顶往下第二个点为qq
  求出fa=lca(x,p)fa=lca(x,p),如果fa=pfa=p,显然xx可以接在这条链后面,将xx加入栈中即可。
  如果fafa不是pp,那么说明ppxxfafa的两棵不同子树中,并且因为按dfs序排序了,所以此时pp所在子树已经遍历完了,那么将栈中ppfafa这条链插入虚树,再把xx塞进栈中即可。
  注意将ppfafa插入虚树里的时候,如果弹栈的时候qq不是fafa,那么得往虚树中插入fafa,因为这个点也是有用的。
  构造虚树时加入xx的步骤:
    11.求出fa=lca(x,p)fa=lca(x,p)
    22.若fa=pfa=p,则直接将xx加入栈中,退出
    33.若dfn(fa)<dfn(q)dfn(fa)<dfn(q)qqpp连边,弹出pp,重复直到dfn(fa)dfn(q)dfn(fa)\geq dfn(q)
    44.若dfn(fa)=dfn(q)dfn(fa)=dfn(q)fafapp连边,将xx加入栈中,退出
    55.若dfn(fa)>dfn(q)dfn(fa)>dfn(q)fafapp连边,将fafa加入栈中,将xx加入栈中,退出
  因为kk个点只会有k1k-1个LCA,于是虚树的总点数是2k12k-1的。

例题

  11.bzoj2286: [Sdoi2011]消耗战