虚树

简述

在一棵树上对关键点集进行运算的一种灵活的数据结构。

构造方式

首先把 \(1\) 号节点塞入栈，然后在按 \(DFS\) 序排序后的点集中选取当前最小点记为 \(x\)，并且与栈的头部取 \(LCA\) 为 \(d\)。如果这个 \(d\) 为栈头部，那么就可以直接放到栈里，否则代表并不在一条链上，需要弹栈直到当前点 \(x\) 能在一条链上为止。为了做到这一点，我们需要栈的第二个节点与 \(d\) 进行比较（存在栈头部为 \(d\) 的情况，这种情况需要直接修改栈头）

大概这么写：

void build_virtual_tree()
{
    // ktot;
    // kseq;
    sort(kseq + 1, kseq + 1 + ktot, [](const int &rhs1, const int &rhs2) { return dfn[rhs1] < dfn[rhs2]; });
    stk[++tail] = 1;
    for (int i = 1; i <= ktot; i++)
    {
        int x = kseq[i], d = getLCA(x, stk[tail]);
        if (x != 1)
        {
            while (dfn[stk[tail - 1]] > dfn[d])
                G[stk[tail - 1]].push_back(stk[tail]), tail--;
            if (dfn[stk[tail - 1]] < d)
                G[d].push_back(stk[tail]), stk[tail] = d;
            else
                G[d].push_back(stk[tail]), tail--;
        }
        stk[++tail] = x;
    }
    for (int i = 1; i < ktot; i++)
        G[stk[i]].push_back(stk[i + 1]);
}