Visits: 293

又是以前学过的知识……
对于一类特殊的树上问题，虚树通常可以简化树的结构，从而降低时间复杂度。

概念

有这样一类树上数据结构题，每组询问会涉及树中若干个关键点，但所有询问涉及的关键点总数并不多（通常需要输入这些关键点，所以也不可能太多，一般与树的大小同阶）。

对于这样的问题，每次询问我们并不需要知道整棵树的结构信息，而只需要知道关键点之间的结构信息。那么，我们可以考虑建出一棵虚树，只保留关键点间的相对结构。

为了保留相对结构，我们除了要将关键点保留，还需要将它们两两的 LCA 保留，同时虚树中一条边的边权为原树中对应路径的边权和。

可以证明，树上 $k$ 个关键点两两的 LCA 个数不超过 $k-1$，这意味着虚树的节点数是 $\mathcal O(k)$ 的，非常优秀。

构造

与笛卡尔树的构造类似，核心都是用栈维护右链。

考虑按 dfs 序依次将关键点插入虚树，为了方便，我们新增一个超级根指向原来的树根。

一开始栈中只有一个超级根，当要加入点 $u$ 的时候，我们求出 $u$ 与栈顶元素 $v$ 的 LCA（由于超级根的存在，栈不会为空），记为点 $p$。

若 $p = v$，说明 $v$ 是 $u$ 的祖先，因此直接将 $u$ 加入栈，延长右链。

否则说明 $u$ 和 $v$ 在 $p$ 的不同子树中，因此我们要更新右链，注意此时 $p$ 一定在右链中，但不一定在栈中。

所以我们不断退栈并连边，直到栈顶的第二个元素的深度比 $p$ 小，分类讨论一下栈顶和 $p$ 是否为同一个点，然后退栈，加入 $p,u$。

最后将栈中的点连边即可，时间复杂度 $\mathcal O(n \log n) – \mathcal O(k \log k)$。

【模板】

const int N = 2e5 + 7;
int n, m, q, dfn[N], tot, f[N][21], d[N], s[N], t;
vi e[N], g[N];

void dfs(int x) {
    dfn[x] = ++tot;
    for (int y : e[x])
        if (y != f[x][0]) {
            d[y] = d[x] + 1, f[y][0] = x;
            for (int i = 1; f[y][i-1]; i++)
                f[y][i] = f[f[y][i-1]][i-1];
            dfs(y);
        }
}

inline int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i = 20; ~i; i--)
        if (d[f[y][i]] >= d[x]) y = f[y][i];
    if (x == y) return x;
    for (int i = 20; ~i; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

inline void virtual_tree(vi &p) {
    sort(p.begin(), p.end(), [](int x, int y) { return dfn[x] < dfn[y]; });
    //p.erase(unique(p.begin(), p.end()), p.end());
    vi q = p;
    for (int x : p) {
        int lca = ::lca(x, s[t]);
        if (lca != s[t]) {
            while (t && d[s[t-1]] >= d[lca])
                g[s[t-1]].pb(s[t]), g[s[t]].pb(s[t-1]), --t;
            if (lca != s[t])
                g[lca].pb(s[t]), g[s[t]].pb(lca), s[t] = lca, q.pb(lca);
        }
        s[++t] = x;
    }
    if (t) while (--t) g[s[t]].pb(s[t+1]), g[s[t+1]].pb(s[t]);
    p = q;
}

int main() {
    rd(n), rd(q);
    for (int i = 1, x, y; i < n; i++)
        rd(x), rd(y), e[x].pb(y), e[y].pb(x);
    d[1] = 1, dfs(1);
    while (q--) {
        rd(m);
        vi a, p;
        for (int i = 1, x; i <= m; i++)
            rd(x), a.pb(x), p.pb(x);
        virtual_tree(p);
        /*
        for (int x : p)
            for (int y : g[x])
                if (x < y) debug("%d %d\n", x, y);
        */
        // to do
        for (int x : p) g[x].clear();
    }
    return 0;
}

【练习】P3320 [SDOI2015]寻宝游戏

const int N = 1e5 + 7;
int n, m, dfn[N], rnk[N], num, d[N], f[N][21];
bool v[N];
vector<pi> e[N];
ll s[N], ans;
set<int> st;

void dfs(int x, int fa) {
    dfn[x] = ++num, rnk[num] = x, d[x] = d[f[x][0]=fa] + 1;
    for (int j = 1; f[x][j-1]; j++) f[x][j] = f[f[x][j-1]][j-1];
    for (pi o : e[x])
        if (o.fi != fa) s[o.fi] = s[x] + o.se, dfs(o.fi, x);
}

inline int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    for (int i = 20; ~i; i--)
        if (d[f[y][i]] >= d[x]) y = f[y][i];
    if (x == y) return x;
    for (int i = 20; ~i; i--)
        if (f[x][i] != f[y][i])
            x = f[x][i], y = f[y][i];
    return f[x][0];
}

inline ll S(int x, int y) {
    return s[x] + s[y] - 2 * s[lca(x,y)];
}

int main() {
    rd(n), rd(m);
    for (int i = 1, x, y, z; i < n; i++)
        rd(x), rd(y), rd(z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
    dfs(1, 0);
    while (m--) {
        int x;
        rd(x), x = dfn[x];
        if (!v[rnk[x]]) st.insert(x);
        auto it = st.lower_bound(x);
        int y = rnk[it==st.begin()?*--st.end():*--it];
        it = st.upper_bound(x);
        int z = rnk[it==st.end()?*st.begin():*it];
        if (v[rnk[x]]) st.erase(x);
        x = rnk[x];
        ll d = S(x, y) + S(x, z) - S(y, z);
        if (!v[x]) v[x] = 1, ans += d;
        else v[x] = 0, ans -= d;
        print(ans);
    }
    return 0;
}

参考资料

• Sengxian 虚树学习笔记