虚树学习笔记

虚树用来解决询问多个关键点，且关键点总数不多的一类问题，记每次询问的关键点个数为$n$，通常$\sum_{n}\le 1e5$是用到虚树的题目的共性。
当树上部分节点用处不大的时候，我们可以把它们从树上删掉，只保留关键点和它们的$LCA$。
虚树的点数级别是$\Theta(n)$的，因为只包含了$n$个关键点以及它们的$LCA$，所以总点数最多是$2n-1$个。
构造虚树：

• 首先我们需要把$LCA$预处理出来，可以用$ST$表或者树链剖分，顺便处理出树的$dfs$序。
• 将询问的关键点按照$dfs$序排序，为了方便我们先把根加入数组中，求出相邻两点的$LCA$，加入关键点数组中重新再按照$dfs$序排序，并去重，现在我们已经得到了虚树上所有的点的前序遍历。
• 如果当前点在栈顶子树中 将栈顶和当前点连边，并将当前点入栈。
• 如果当前点不在栈顶子树中，说明此时栈顶所在的一段链已经$Dfs$完毕，弹栈，重复执行该过程直到满足情况1。

$\Large Code:$

inl void build() {
	memset(head, 0, sizeof(head)), tot = 0;
    sort(a.begin(), a.end(), [](int a, int b) -> bool {return dfn[a] < dfn[b]; });
	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(), [](int a, int b) -> bool {return dfn[a] < dfn[b]; });
	auto it = unique(a.begin(), a.end());
	a.erase(it, a.end());
	rt = st[++top] = a[0];
	for (int i = 1; i < a.size(); i++) {
		int now = a[i];
		while (top >= 1) {
			if (fir[now] >= fir[st[top]] && fir[now] <= las[st[top]]) {
				add(st[top], now);
				break;
			}
			top--;
		}
		if (st[top] != now) st[++top] = now;
	}
}