一道例题 讲起。

题意:给定一棵 $n$ 个点,带边权的树,$m$ 次给定 $k$ 个关键点 $a_i$,要求割掉总边权最小的一些边,让 $1$ 号点和任意 $a_i$ 不连通。

$2\leq n\leq 2.5\times 10^5$,$1\leq m\leq 5\times 10^5$,$\sum k\leq 5\times 10^5$,$1\leq k\leq n$,$2\leq a_i\leq n$,$1\leq u,v\leq n$,$1\leq w\leq 10^5$。

考虑每次询问做一个很朴素的 dp,记录 $g_u$ 是使得 $u$ 子树里的关键点都和 $1$ 不连通的最小花费。

$$ g_u=\sum_{v\in son_u}\begin{cases} val(u,v)& v\text{是关键点}\\ \min\{val(u,v),g_v\}& v\text{不是关键点}\\ \end{cases} $$

于是就得到了一个 $O(nm)$ 的做法。

考虑如何优化,我们发现对于每次询问,真正对答案有贡献的点并不多。

有贡献的点有哪些呢?首先肯定关键点在里面,$1$ 在里面,关键点的 LCA 也应该在里面...

那么我们需要一个好写点的东西把这些点抽出来重新建树,这样就方便我们 dp 了。

于是就引出了虚树这个概念。

虚树就是给定一些树上的关键点,抽出一些点来,满足:

  • 所有关键点都在虚树中
  • 关键点之间的 LCA 不变

考虑 dfs 的本质,其实就是一个栈在反复的进行 push/pop 操作。

于是考虑利用这个性质建树,用一个栈记录当前模拟的 dfs 栈,即一条从根往下的路径被压在这个栈 $s$ 中。

先把所有关键点 $a_i$ 按照 dfs 序排序,然后顺次插入。

记录栈顶元素为 $t_1$,栈顶的下一个元素为 $t_2$(如果存在),对于每次插入点 $x$,流程如下:

  • 记录点 $l=\text{lca}(x,t_1)$。
  • 如果 $l=t_1$,直接把 $x$ 入栈,因为这就是正常 dfs 的顺序。
  • 否则说明 $x$ 和 $t_1$ 已经不属于同一棵子树了,应该连边 $t_2\to t_1$,然后把 $t_1$ 退栈,直到 $dfn_{t_1}\leq dfn_l\leq dfn_{t_2}$ 或是栈内只剩一个元素。
  • 此时,若 $l=t_1$,把 $x$ 压入栈,否则连边 $l\to t_1$,把 $t_1$ 退栈再压入 $x$。

提供一种比较通用的写法。

int rt,top,stk[N],dep[N],dfn[N];
void link(const int &u,const int &v){
    if(dep[u]<dep[rt]||!rt)rt=u;
    //link and init u → v
}
void insert(int u){
    if(!top)return stk[++top]=u,void();
    int l=lca(u,stk[top]);
    if(l==stk[top])return stk[++top]=u,void();
    while(top>1&&id[stk[top-1]]>=id[l])link(stk[top-1],stk[top]),top--;
    if(l!=stk[top])link(l,stk[top]),stk[top]=l;
    stk[++top]=u;
}
void build(int *b,int n){
    top=rt=0;
    For(i,1,n)insert(b[i]);
    while(top>1)link(stk[top-1],stk[top]),top--;
}

上面那道题的 代码

update 2021/8/12:

更新一种更方便的虚树建法。

先把所有点按照 dfn 排序,然后把相邻点的 lca 判重之后丢进去再排序,每个点在虚树上的父亲就是它和前驱的 lca。

最后修改:2021 年 08 月 13 日
如果觉得我的文章对你有用,请随意赞赏