DDOSvoid's Blog

虚树

发表于 更新于 分类于
本文字数： 1.4k 阅读时长 ≈ 1 分钟

简介

大概就是将给定的树上的 $k$ 个点和它们之间的 $lca$ 拿出来重新建一棵树，时间复杂度为 $O(k\log k)$

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void solve(int n, int rt) {
    for (int i = 1; i <= n; ++i) col[a[i]] = 1; 
    sort(a + 1, a + n + 1, [](const int &u, const int &v) { return id[u] < id[v]; });
    stack<int> S; S.push(rt); 
    for (int o = 1, u = a[o]; o <= n; u = a[++o]) {
        if (u == rt) continue; int lca = get_lca(u, S.top());
        while (S.top() != lca) {
            int t = S.top(); S.pop();
            if (id[S.top()] < id[lca]) S.push(lca);
            add_edge(S.top(), t);
        } S.push(u);
    }
    while (S.top() != rt) {
        int t = S.top(); S.pop();
        add_edge(S.top(), t);
    } dfs(rt, 0);
    cout << dp[rt] << "\n";
    clear(rt, 0), c1 = 0;
}

例题

  1. 简要题意：给定一棵以 $1$ 为根的有根树，边权不为 $1$，现在有 $m$ 次询问，每次询问给定一个点集 $|S|$，保证该点集不包含 $1$，现在要求断掉一些边，使得点集中任意一个点都不与 $1$ 相连，求最小代价

    $n\le 2.5\times 10^5,m,\sum |S|\le 5\times 10^5$

    简要题解：虚树模板题，我们将虚树建出来之后跑 $dp$ 即可

    Luogu P2495 [SDOI2011]消耗战

  2. 简要题意：给定一棵 $n$ 个节点的树，现在有 $m$ 次询问，每次询问给出 $k_i$ 个关键点，然后将树上的每个点划分到离他最近的关键点，如果距离两个关键点相同，则划分给编号较小的关键点，输出每个关键点被分配到多少点

    $n,m,\sum k_i\le 3\times 10^5$

    简要题解：我们考虑建出关键点的虚树，然后通过两次 $dfs$，求出离每个点最近的关键点

    然后我们考虑计算每条边的贡献，如果这条边的两个端点属于同一个关键点，那么这条边一定也属于这个关键点，否则我们二分分界点即可，处理时需要一些技巧

    时间复杂度 $O(n\log^2 n)$，如果优化求距离到 $O(1)$，可以做到 $O(n\log n)$

    Luogu P3233 [HNOI2014]世界树

  3. 简要题意：给定一棵 $n$ 个点的无根树，每个点有一个点权 $a_i$，现在有 $m$ 次询问，每次询问给定一条树上的路径 $(u,v)$ 和权值 $w$，求 $\prod_{t\in (u,v)}gcd(a_t,w)$

    $n\le 10^5,a_i,w\le 10^7$

    简要题解：我们考虑对于每个数分解质因数，对于每个质因数建虚树单独做，注意到 $a_i\le 10^7$，所以每个点最多只有不超过 $7$ 个不同的质因数，对于询问，也要按照质因数拆分，注意把询问的点也扔进虚树里

    对于询问，我们将其拆成到根的树链，$dfs$ 的时候预处理即可，时间复杂度 $O(7n\log a_i)$

    CF 986E Prince’s Problem