高级数据结构-虚树

问题类型

有些问题一次询问需要O(n)的复杂度，但多次询问时间复杂度会很大。
但如果我们只需要用到题目中给出的一些关键点和它们的LCA，并且给出的关键点个数总和并不多，我们可以求出它们的LCA，建成虚树，一次询问就变成了O(关键点个数)

解决方案

从上文得知，我们需要找出关键点的LCA并且建成虚树。

这时我们就需要用到栈。（在后文我们简称关键点的LCA为重要点）
我们用栈维护从根到当前关键点的路径上的重要点。
我们先把关键点按DFS序从小到大排序。
然后每次新枚举一个关键点u，求出它与栈顶v（上一个关键点）的LCA:w。
如果u是v的子孙，那么w=v，直接把u加入栈即可。
如果u不是v的子孙，那么w的深度一定比v要浅，所以我们就一直弹栈顶，知道栈顶的深度≤w的深度。
这时如果栈顶不是w，再把w加入栈。最后再把当前关键点加入栈。
我们在每次弹栈的时候，就把栈顶和相邻元素连边。（注意最后还要把栈弹空）

代码演示

void Build()
{
    sort(X + 1, X + num + 1, cmp);
    stack[top = 1] = X[1];
    rep(i, 2, num)
    {
        int u = lca(X[i], stack[top]);
        while (top && Deep[stack[top]] > Deep[u])
        {
            addedge(stack[top], Deep[stack[top - 1]] < Deep[u] ? u : stack[top - 1]);
            top--;
        }
        if (!top || u != stack[top]) stack[++top] = u;
        stack[++top] = X[i];
    }
    while (--top) addedge(stack[top + 1]], stack[top]);
}