虚树

· · 算法·理论

最近学算法都感觉越来越看不懂别人的博客了,所以决定以后学的东西多多少少都写一点总结,以前学过的也有可能会写。

声明:以下所有求 \operatorname{lca} 均默认为 \operatorname{dfn} 求 \operatorname{lca},时间复杂度 O(n\log n)-O(1),你也可以使用自己喜欢的方法求。

\operatorname{Part\ 1.} 引入

来看一道例题:

\operatorname{Part\ 2.} 优化

考虑这个做法慢在那里。

显然你没必要每次把所有点都算出来。

你总共 dp 算过的点数是 O(nm) 级别的,远大于 k。

有一个非常牛的想法:取出若干点,使得只 dp 这些点也可以得到正确的答案,你也可以理解为把原树中不影响答案的长链全都缩掉。

现在要求哪些点必须保留。显然关键点必须被保留。

接着观察一些性质:

对于这个题因为答案是 f_1,所以你还需要保留 1 节点。

\operatorname{Part\ 3.} 虚树的定义

由上面的证明,我们引出虚树的概念。

定义. 给定原树 T 和关键点集合 S,虚树 T' 是满足以下条件的最小树:

  1. 包含 S 中所有点;
  2. 包含 S 中任意两点的 LCA;

性质. |V(T')|\le 2|S|-1。

证明:最坏情况为构造一颗二叉树,如果想深究可以继续往下看,下面的构造部分都会讲到。

所以只要我们能高效地构造出这棵虚树,就能把一次 DP 的规模从 O(n) 降到 O(|S|)。

\operatorname{Part\ 4.} 构造

先考虑怎么把所有需要的点丢进来,再考虑怎么连边。

直接 O(k^2) 枚举点对求 LCA 肯定不行,但有一个非常牛的性质:

把关键点按 \operatorname{dfn} 排序后,任意两个关键点的 LCA,一定是某对相邻关键点的 LCA。

所以只需要加入 \operatorname{dfn} 排序后,相邻对的 \operatorname{lca} 即可,时间复杂度降至 O(k\log k)。

同样的,这个也可以解释前一部分中虚树点的数量上限,因为相邻对数量是 O(|S|) 的。

点选完了,接着考虑怎么把树建出来。

还是按照 \operatorname{dfn} 排序,用单调栈动态维护当前树的右链。

处理当前点 u 时,令 l=\operatorname{lca}(u,\text{栈顶}),显然我们得到的是 u 在虚树中的父亲。

由于按照 \operatorname{dfn} 顺序加入,所以 l 一定已经被加过了,之前的也是 l 左边的链,那么一直弹栈直到栈顶为 l 即可,注意之前加入的点也是父子关系,所以要在弹栈的过程中动态更新虚树的边即可。

\operatorname{Part\ 5.} 在虚树上 DP

构造完虚树后,直接在虚树上跑原题 DP:

其中 w_{\text{虚}}(u,v) 是原树上 u\to v 路径的最小边权。

有前面的证明可知这是等价的,但是时间复杂度边为 O(k)。

综合一下,虚树解决整个问题的时间复杂度降至了 O(k\log n)。

非常建议看一下代码,不要只听想法不会实现了。

:::success[P2495 【模板】虚树 / [SDOI2011] 消耗战 Code] 感觉还是比较好写的。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int lg = 19;
const ll inf = 1e18;
const int N = 2.5e5 + 5;
int n, m, k;
ll minx[lg][N];
int cnt, dfn[N], dep[N];
int st[lg][N], up[lg][N];
vector<pair<int, int>> g[N];
int get(int x, int y)
{
    return dep[x] < dep[y] ? x : y;
}
int lca(int u, int v)
{
    if(u == v) return u;
    u = dfn[u], v = dfn[v];
    if(u > v) swap(u, v);
    int k = __lg(v - u++);
    return up[0][get(st[k][u], st[k][v - (1 << k) + 1])];
}
ll getmin(int u, int v)
{
    ll res = inf;
    for(int i = lg - 1; i >= 0; i--)
    {
        if(dep[up[i][v]] >= dep[u]) res = min(res, minx[i][v]), v = up[i][v];
    }
    return res;
}
struct VirtualTree
{
    ll f[N];
    bool vis[N];
    vector<int> nodes;
    int top, fa[N], stk[N];
    void build(vector<int> vec)
    {
        nodes = vec;
        for(auto x : nodes) vis[x] = 1;
        sort(nodes.begin(), nodes.end(), [&](int x, int y)
        {
            return dfn[x] < dfn[y];
        });
        int m = nodes.size();
        for(int i = 0; i + 1 < m; i++) nodes.push_back(lca(nodes[i], nodes[i + 1]));
        nodes.push_back(1);
        sort(nodes.begin(), nodes.end(), [&](int x, int y)
        {
            return dfn[x] < dfn[y];
        });
        nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
        top = 0, stk[++top] = 1;
        for(auto u : nodes)
        {
            if(u == 1) continue;
            int l = lca(u, stk[top]);
            while(dep[stk[top - 1]] >= dep[l]) fa[stk[top]] = stk[top - 1], top--;
            stk[++top] = u;
        }
        while(top > 1) fa[stk[top]] = stk[top - 1], top--;
        return;
    }
    ll solve()
    {
        for(auto u : nodes) f[u] = 0;
        for(int i = nodes.size() - 1, u; i >= 0; i--)
        {
            u = nodes[i];
            if(vis[u]) f[u] = inf;
            f[fa[u]] += min(f[u], getmin(fa[u], u));
        }
        return f[1];
    }
    void clear()
    {
        for(auto u : nodes) vis[u] = 0;
        nodes.clear();
        return;
    }
}tr;
void dfs(int u, int fa, int w)
{
    dfn[u] = ++cnt, dep[u] = dep[fa] + 1;
    up[0][u] = fa, st[0][cnt] = u, minx[0][u] = w;
    for(int i = 1; i < lg; up[i][u] = up[i - 1][up[i - 1][u]], minx[i][u] = min(minx[i - 1][u], minx[i - 1][up[i - 1][u]]), i++);
    for(auto [v, w] : g[u])
    {
        if(v == fa) continue;
        dfs(v, u, w);
    }
    return;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen(".in", "r", stdin);
    // freopen(".out", "w", stdout);
    cin >> n;
    for(int i = 1, u, v, w; i < n; i++)
    {
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    for(int i = 0; i < lg; minx[i][0] = inf, i++);
    dfs(1, 0, inf);
    for(int j = 1; j < lg; j++)
    {
        for(int i = 1; i + (1 << j) - 1 <= n; st[j][i] = get(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]), i++);
    }
    cin >> m;
    while(m--)
    {
        cin >> k;
        tr.clear();
        vector<int> vec;
        vec.reserve(k);
        for(int i = 1, x; i <= k; i++) cin >> x, vec.push_back(x);
        tr.build(vec);
        cout << tr.solve() << "\n";
    }
    return 0;
}

:::

\operatorname{Part\ 6.} 练习