虚树

虚树是虚无星神家种的树

虚树其实是虚渊玄和藤本树

时间复杂度O(mlogn)，其中m为关键点数，n为总点数。

构造方法Ⅰ：二次排序 + LCA连边

/*lca模板*/
//可以将1作为虚树根节点方便操作
int dfn[N];
vector<int> kp, a, vt[N]; // kp存储关键点, a存储虚树序列结果, vt为新建虚树
void build_virtual_tree()
{
    auto cmp = [&](int a, int b) -> bool
    { return dfn[a] < dfn[b]; };
    sort(kp.begin(), kp.end(), cmp); // 把关键点按照 dfn 序排序
    a.push_back(kp.front());
    for (int i = 1; i < kp.size(); ++i)
    {
        a.push_back(kp[i]);
        a.push_back(lca(kp[i - 1], kp[i])); // 插入 lca
    }
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
    // 建虚树
    for (int i = 1; i < a.size(); ++i)
    {
        int lc = lca(a[i - 1], a[i]);
        vt[lc].push_back(a[i]);
        vt[a[i]].push_back(lc);
    }
}

构造方法Ⅱ：单调栈

/*lca模板*/
int dfn[N];
vector<int> kp, vt[N]; // kp存储关键点
void build_virtual_tree()
{
    auto cmp = [&](int a, int b) -> bool
    { return dfn[a] < dfn[b]; };
    auto conn = [&](int a, int b) -> void
    { vt[a].push_back(b), vt[b].push_back(a); };
    sort(kp.begin(), kp.end(), cmp);
    stack<int> s;
    s.push(1);
    //vt[1].clear(); //重复使用的初始化
    for (auto i : kp) // 如果1号节点是关键节点就不要重复添加
        if (i != 1)
        {
            int lc = lca(i, s.top()); // 计算当前节点与栈顶节点的 LCA
            if (lc != s.top()) // 不同，说明当前节点不再当前栈所存的链上
            {
                int last = s.top();
                s.pop();
                while (dfn[lc] < dfn[s.top()]) // 当次大节点的Dfn大于LCA的Dfn
                {
                    conn(s.top(), last);
                    last = s.top();
                    s.pop();
                }                           // 把与当前节点所在的链不重合的链连接掉并且弹出
                if (dfn[lc] > dfn[s.top()]) // 说明LCA是第一次入栈，清空其邻接表，连边后弹出栈顶元素，并将 LCA入栈
                {
                    //vt[lc].clear();
                    conn(lc, last);
                    s.push(lc);
                }
                else // 说明LCA就是次大节点，直接弹出栈顶元素
                    conn(lc, last);
            }
            //vt[i].clear();
            s.push(i);
        }
    int last = s.top();
    s.pop();
    while (!s.empty()) // 剩余的最后一条链连接一下
    {
        conn(last, s.top());
        last = s.top();
        s.pop();
    }
    return;
}