一种神秘的 O(n logn) 建虚树方式

· · 算法·理论

如题，我在 2025.6.20 的模拟赛中，只记得应该按 dfn 排序后找相邻两个的 LCA，忘记该怎么建边了。于是场上手搓了一个神秘做法，由于我的实现太垃圾了写成了 O(n^2)，但很容易写成只有排序和 LCA 的 O(n\log n)。

首先按 dfn 从小到大排序，将 LCA(p_i,p_{i+1}) 加入点集，将新的点集再次排序去重。

注意到此时的第一个点一定是虚树的根，第二个点一定是它的儿子，且第二个点的子树就是后面一段连续的区间。

我赛时的 n^2 实现是暴力将每个儿子的子树分出来，递归建树，但实际上是没有必要的（感谢 @[supperpiggy]() 小姐姐）。

预处理子树内 dfn 最大值 ed_u，假如当前递归到点 u，当前队头是 v，如果 dfn_v\le ed_u，说明 v 是 u 的儿子，直接将 v 连向 u ，弹出 v 并递归到 v；否则，v 不在 u 子树内，直接回溯。

容易说明，这样做的时间复杂度是 O(n\log n) 的。

理论上，这种建树方式的常数主要是递归带来的，比二次排序 + LCA 连边少了 n 次求 LCA，应当比 O(\log n) 的倍增 LCA 要快。

实际测试确实得到了这样的结果（P2495）：

注意到它甚至比 O(1) LCA 还快（尽管可能有一定的评测机波动），但即使效率相近也已经很感人了。（这个时间看上去有点长，是因为我用了大量 vector 导致其他部分的常数较大）

代码并没有比 LCA 连边复杂多少，太令人感动了（）

vector<int> V;
vector<pair<int,int> > E[N];
int rt;
inline bool isanc(int u,int v){
    return dfn[u]<=dfn[v] && dfn[v]<=ed[u];
}
inline void dfs(int u){
    // 递归建树直到当前队头不在子树内
    while(!V.empty() && isanc(u,V.back())){
        int v=V.back(),w=getmn(u,v);
        V.pop_back();
        E[u].emplace_back(mkp(v,w));
        dfs(v);
    }
}
inline void buildtr(vector<int> &vec){
    for(int x:vec) V.emplace_back(x);
    V.emplace_back(1);
    sort(V.begin(),V.end(),[](int x,int y){return dfn[x]<dfn[y];});
    int sz=V.size();
    rep(i,1,sz-1) V.emplace_back(lca(V[i-1],V[i]));
    sort(V.begin(),V.end(),[](int x,int y){return dfn[x]>dfn[y];});
    V.resize(unique(V.begin(),V.end())-V.begin());
    // 以上和二次排序一模一样
    for(auto x:V) E[x].clear();
    rt=V.back();V.pop_back();
    dfs(rt);
}

upd：伟大的前队长 xmg 告诉我，这个东西本质是用递归实现单调栈，单调栈建树中弹出栈顶和我的递归回溯本质是相同的。

于是我被偏序了（显然它打不过单调栈），还是太不会虚树了呜呜。

但感觉这个比传统单调栈建虚树好理解一点点，大概递归还是比较自然的想法。

反向思维一下，似乎树上遍历（比如 dp）也可以求 dfn 后用单调栈实现，如果遍历次数多的话感觉常数会略小一些，但可读性会大大降低，得不偿失。