Virtual Tree (tree/virtual_tree.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-09-25 11:45:13+07:00
• Include: #include "tree/virtual_tree.hpp"

Description

Virtual Tree constructs a tree containing only specified vertices and their LCAs, preserving ancestor relationships. Useful for processing queries on a subset of vertices efficiently. Requires HLD for LCA computation.

Operations

• VirtualTree(HLD &hld)
  • Constructs virtual tree using HLD instance
  • Time complexity: $\mathcal O(1)$
• template<class V> int build(V vs)
  • Builds virtual tree from vertices vs
  • Returns the root of the virtual tree
  • Time complexity: $\mathcal O(k \log k)$ where $k$ is the number of vertices
• auto &operator[](int v)
  • Returns the adjacency list of vertex v in the virtual tree
  • Time complexity: $\mathcal O(1)$

Depends on

• Heavy-light Decomposition (tree/hld.hpp)

Code

#pragma once

#include "hld.hpp"

struct VirtualTree {
    int n;
    HLD &hld;
    vector<basic_string<int>> g;

    VirtualTree(HLD &_hld) : n(_hld.n), hld(_hld), g(n) {}

    template<class V> int build(V vs) {
        auto anc = [&](int p, int v) {
            return hld.in[p] <= hld.in[v] && hld.out[v] <= hld.out[p];
        };
        auto cmp = [&](int u, int v) { return hld.in[u] < hld.in[v]; };
        int k = (int)vs.size();
        sort(begin(vs), end(vs), cmp);
        for (int i = 1; i < k; i++) vs.push_back(hld.lca(vs[i - 1], vs[i]));
        sort(begin(vs), end(vs), cmp);
        k = unique(begin(vs), end(vs)) - begin(vs);
        for (int i = 0; i < k; i++) g[vs[i]].clear();
        stack<int> st;
        st.push(vs[0]);
        for (int i = 1; i < k; i++) {
            while (!anc(st.top(), vs[i])) st.pop();
            g[st.top()] += vs[i];
            st.push(vs[i]);
        }
        return vs[0];
    }
    auto &operator[](int v) { return g[v]; }
};

#line 2 "tree/virtual_tree.hpp"

#line 2 "tree/hld.hpp"

struct HLD {
    int n;
    vector<int> in, par, dep, out, hs;

    template<class G>
    HLD(G &g, int root = 0) :
        n((int)g.size()), in(n), par(n), dep(n), out(n), hs(n) {
        hs[root] = root;
        dfs_sz(g, root);
        dfs_hld(g, root);
        assert(time == n);
    }

    int lca(int u, int v) const {
        assert(0 <= u && u < n && 0 <= v && v < n);
        for (;; v = par[hs[v]]) {
            if (in[u] > in[v]) swap(u, v);
            if (hs[u] == hs[v]) return u;
        }
    }
    int dist(int u, int v) const {
        assert(0 <= u && u < n);
        assert(0 <= v && v < n);
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    auto path(int v, int p, bool es = 0) const {
        assert(in[p] <= in[v] && out[v] <= out[p]);
        vector<pair<int, int>> res;
        for (; hs[v] != hs[p]; v = par[hs[v]])
            res.emplace_back(in[hs[v]], in[v] + 1);
        res.emplace_back(in[p] + es, in[v] + 1);
        return res;
    }
    pair<int, int> subtree(int v) const {
        assert(0 <= v && v < n);
        return {in[v], out[v]};
    }
    int operator[](int v) { return in[v]; }
    int operator()(int v) { return out[v]; }

  private:
    int time = 0;
    template<class G> int dfs_sz(G &g, int v, int p = -1) {
        par[v] = p;
        int sz = 1, mx = 0;
        for (auto &c : g[v]) {
            if (c == p) continue;
            dep[c] = dep[v] + 1;
            int s = dfs_sz(g, c, v);
            sz += s;
            if (g[v][0] == p || mx < s) mx = s, swap(g[v][0], c);
        }
        return sz;
    }
    template<class G> void dfs_hld(G &g, int v, int p = -1) {
        in[v] = time++;
        for (auto c : g[v]) {
            if (c == p) continue;
            hs[c] = (c == g[v][0] ? hs[v] : c);
            dfs_hld(g, c, v);
        }
        out[v] = time;
    }
};
#line 4 "tree/virtual_tree.hpp"

struct VirtualTree {
    int n;
    HLD &hld;
    vector<basic_string<int>> g;

    VirtualTree(HLD &_hld) : n(_hld.n), hld(_hld), g(n) {}

    template<class V> int build(V vs) {
        auto anc = [&](int p, int v) {
            return hld.in[p] <= hld.in[v] && hld.out[v] <= hld.out[p];
        };
        auto cmp = [&](int u, int v) { return hld.in[u] < hld.in[v]; };
        int k = (int)vs.size();
        sort(begin(vs), end(vs), cmp);
        for (int i = 1; i < k; i++) vs.push_back(hld.lca(vs[i - 1], vs[i]));
        sort(begin(vs), end(vs), cmp);
        k = unique(begin(vs), end(vs)) - begin(vs);
        for (int i = 0; i < k; i++) g[vs[i]].clear();
        stack<int> st;
        st.push(vs[0]);
        for (int i = 1; i < k; i++) {
            while (!anc(st.top(), vs[i])) st.pop();
            g[st.top()] += vs[i];
            st.push(vs[i]);
        }
        return vs[0];
    }
    auto &operator[](int v) { return g[v]; }
};

Back to top page