虚树-学习笔记

为什么我现在才会

​

引入

先放一道题：

BZOJ2286：

给一棵带边权有根树，可以花费边权的代价断一些边

每次询问\(k_i\)个点，问使这些点都不与根联通的最小代价

\(n,q\le 10^5，\sum k_i \le 10^5\)

​

如果只有一个询问是个SB题……直接树形DP就好了

但是考虑到询问的总点数很有限，还是可做的

什么是虚树

像上面的例题，我们只把与询问有关的点拿出来建一棵树，就可以解决问题

那么这棵树包含所有询问点以及它们的LCA，这棵树就是虚树

​

考虑每次往虚树里加入一个询问点，最多增加一个LCA，所以虚树的点数是\(O(k)\)的

每次询问直接在虚树里做DP就可以了

这保证了复杂度

虚树的构造

按DFS序遍历每个询问点

我们用一个栈\(stack\)维护从根到当前点路径上的所有虚树点

当新加入点\(x\)是栈顶\(stack[top]\)的后代时，直接入栈

否则\(x\)与栈顶\(stack[top]\)的LCA一定要入栈（可能已经入了），同时应该把LCA的\(x\)所在子树构造好虚树

最后别忘了清栈

void insert(int x){
	if (!top) {stk[++top]=x;return;}
	int lca=LCA(x,stk[top]);
	while (top>1&&dfn[stk[top-1]]>dfn[lca])
		add(stk[top-1],stk[top],dst(stk[top-1],stk[top])),top--;
	if (dfn[stk[top]]>dfn[lca]) add(lca,stk[top],dst(lca,stk[top])),top--;
	if (!top||dfn[stk[top]]<dfn[lca]) stk[++top]=lca;
	stk[++top]=x;
}
//......
sort(h+1,h+1+K,cmp); tot=top=0;
for (int i=1;i<=K;i++) insert(h[i]);
while (top>1) add(stk[top-1],stk[top],dst(stk[top-1],stk[top])),top--;

tips

• 最后剩下的栈顶就是虚树根啦
• 每次建图清\(lnk\)很烦，可以一边DP一边清