虚树学习笔记

当我们遇到一类频繁询问关键点信息的题目时，往往数据范围颇大，而对关键点总和有一定限制，此时我们可以建立虚树，将问题规模转化为关键点总和级别的。

定义

什么是虚树？
当我们在树上有部分结点是无用的或用处不大的时，我们可以将其在树上删去，仅仅保留关键点和连接关键点的边。

如图，图中红点是关键点，右图即为建立的虚树。

性质

空间线性性质

虚树的点数是$O(n)$的，因为其仅仅包含$n$个关键点和它们的$lca$，而$lca$的个数最多$n-1$个，故虚树结点数最多$2n-1$。

结构相似性质

通过保留关键点的$lca$，我们可以尽可能地做到使虚树结构与原树相似，这样便使得我们的转化是有效的。

建立过程

1.初始化

初始化ST表并将关键点按照Dfs序排序。

2.得到虚树上的点

利用倍增求出排好序过后的关键点相邻两点的LCA，并加入关键点数组中，重新按照Dfs序排序并去重。

容易发现，此时虚树上的所有点都存在于数组中了。

3.构建虚树

我们已经得到了虚树先序遍历的结果，现在我们要构建虚树，分为两种情况讨论。

1.当前点在栈顶子树中

将栈顶和当前点连边，并将当前点入栈。

2.当前点不在栈顶子树中

说明此时栈顶所在的一段链已经Dfs完毕，弹栈，重复执行该过程直到满足情况$1$

代码

void build(vector<int>& a) {
	int tmp=a.size();
	for(int i=0; i<tmp-1; i++)a.push_back(LCA(a[i],a[i+1]));
	sort(a.begin(),a.end(),cmp);
	auto it=unique(a.begin(),a.end());
	a.erase(it,a.end());
	static int top=0,S[maxn];
	root=S[++top]=a[0];
	for(int i=1; i<a.size(); i++) {
		int now=a[i];
		while(top>=1) {
			if(First[now]>=First[S[top]]&&First[now]<=Last[S[top]]) {
				AddTreeEdge(S[top],now);
				break;
			}
			top--;
		}
		if(S[top]!=now)S[++top]=now;
	}
}