算法入门：虚树

· · 算法·理论

参考资料：https://oi-wiki.org//graph/virtual-tree/

目录

  1. 虚树
    1-1. 引入
    1-2. 朴素做法
    1-3. 优化做法
    1-3-1. 观察
    1-3-2. 虚树
    1-3-2-1. 二次排序+LCA连边
    1-3-2-2. 单调栈
    1-3-3. 虚树上的DP
    1-4. 代码

  2. 练习
    2-1. [HNOI2014] 世界树
    2-1-1. 思路
    2-1-2. 代码
    2-2. [HEOI2014] 大工程
    2-2-1. 思路
    2-2-2. 代码
    2-3. Kingdom and its Cities
    2-3-1. 思路
    2-3-2. 代码
    2-4. [SDOI2018] 战略游戏
    2-5. [WC2018] 通道

正文

1. 虚树

1-1. 引入

题目： [SDOI2011] 消耗战

题目描述：
在一场战争中，战场由 n 个岛屿和 n-1 个桥梁组成，保证每两个岛屿间有且仅有一条路径可达。现在，我军已经侦查到敌军的总部在编号为 1 的岛屿，而且他们已经没有足够多的能源维系战斗，我军胜利在望。已知在其他 k 个岛屿上有丰富能源，为了防止敌军获取能源，我军的任务是炸毁一些桥梁，使得敌军不能到达任何能源丰富的岛屿。由于不同桥梁的材质和结构不同，所以炸毁不同的桥梁有不同的代价，我军希望在满足目标的同时使得总代价最小。

侦查部门还发现，敌军有一台神秘机器。即使我军切断所有能源之后，他们也可以用那台机器。机器产生的效果不仅仅会修复所有我军炸毁的桥梁，而且会重新随机资源分布（但可以保证的是，资源不会分布到 1 号岛屿上）。不过侦查部门还发现了这台机器只能够使用 m 次，所以我们只需要把每次任务完成即可。

输入：
第一行一个整数 n，表示岛屿数量。

接下来 n-1 行，每行三个整数 u,v,w ，表示 u 号岛屿和 v 号岛屿由一条代价为 w 的桥梁直接相连。

第 n+1 行，一个整数 m ，代表敌方机器能使用的次数。

接下来 m 行，第 i 行一个整数 k_i ，代表第 i 次后，有 k_i 个岛屿资源丰富。接下来 k_i 个整数 h_1,h_2,..., h_{k_i} ，表示资源丰富岛屿的编号。

输出：
输出共 m 行，表示每次任务的最小代价。

数据规模与约定：

1-2. 朴素做法

显然，若总点数较少，则可以直接对每一次询问跑 \text{DP} 。

称某次询问中被选中的点为 关键点 ，
记 dp(i) 表示使 i 不与其子树任意一个关键点联通的 最小代价 ，
记 w(a,b) 表示 a 与 b 边之间的权值，
则最终答案即为 dp(1) 。

对于遍历到的点 x ，我们可以枚举其儿子 y ，即：

如此，便能 O(nm) 计算出 dp(1) 。

然而，本题的数据范围为 2 \le n \le 2.5 \times 10^5，1 \le m \le 5 \times 10^5 ，该做法严重超时。

1-3. 优化做法

1-3-1. 观察

打表发现，对于每次 \text{DP}，有很多无用点，真正有用的点只有三种：

接着便要用到虚树了。

1-3-2. 虚树

当 查询多，关键点少，在原树上 有用点稀疏 时，可以将整棵树的有用信息压缩成一棵点数较少的树，即由 有用点 构成的 虚树，再进行操作，而非直接在原树上进行。

然而，我们不可能枚举所有的取关键点情况，O(k^2\log n)计算出有用点，建出虚树。故当务之急便是如何快速建出虚树。

下面给出两种建树方法。

1-3-2-1. 二次排序+LCA连边

之所以枚举的复杂度为 O(k^2\log n) ，是因为在枚举 \{a_1,a_2\} 时，会出现大量重复的 \text{lca}(a_1,a_2)。

我们建立点集 A ，并把所有 关键点 和 根节点 1 加入 A 。
接着将关键点 按 \text{DFS} 序 排序，再遍历关键点序列，把相邻两点 x 和 y 的 \text{LCA} 也加入序列 A 。

由于 \text{DFS} 序的特性，此时 A 已包含了所有 虚树上的点 ，接下来只要考虑如何用 A 建树即可。

把 A 再次排序并去重，再遍历一遍 A ，对于相邻点 x 和 y ，连接 \text{lca}(x,y) 和 y ，最终得到的就是虚树。

为什么可以直接连 \text{lca}(x,y) 呢？

这是因为，对于点 x 和 y ：

这样，我们便用二次排序 + \text{LCA} 连边建了一棵虚树。
时间复杂度为 O(k\log n)，树上大约 2k 个点。

伪代码： 

int dfn[N]; // DFS序
int h[N], k, a[N << 1], tot;
// h为输入的关键点序，a即上文中的A，空间注意要开两倍，因为未去重前有2k个点

inline bool cmp(int x, int y) {
  return dfn[x] < dfn[y]; // 按DFS序升序排序
}

void buildVirtualTree() {
  sort(h + 1, h + k + 1, cmp); // 将关键点按DFS序排序
  a[tot = 1] = 1; // 加入根节点1
  for (int i = 1; i < k; ++i) {
    a[++tot] = h[i]; // 加入关键点
    a[++tot] = lca(h[i], h[i + 1]); // 加入LCA
  } a[++tot] = h[k]; // 加入最后一个关键点
  sort(a + 1, a + tot + 1, cmp); // 二次排序
  tot = unique(a + 1, a + tot + 1) - a - 1; // 去重 
  for (int i = 1; i < tot; ++i) 
    connect(lca(a[i], a[i + 1]), a[i + 1]); // 连边
}

1-3-2-2. 单调栈

除了二次排序 + \text{LCA} 建树，我们还可以利用单调栈。

明确单调栈用途：维护目前虚树中最右端的一条链。

具体操作：

伪代码： 

int dfn[N]; // DFS序
int sta[N], top; // 栈
int h[N], k; // 输入的关键点集

inline bool cmp(int x, int y) {
  return dfn[x] < dfn[y]; // 按DFS序升序排序
}

void buildVirtualTree() {
  sort(h + 1, h + k + 1, cmp);
  sta[top = 1] = 1;
  for (int i = 1; i <= k; ++i) {
    int x = h[i], y = sta[top];
    if (x == y) continue; // 如果x为栈顶元素，直接跳过
    int lc = lca(x, y);
    if (lc != y) { // 如果x与y不在同一条链上
      while (dfn[lc] < dfn[sta[top - 1]]) {
        connect(sta[top - 1], sta[top]); // 连边
        --top;
      } // 将sta中的与x所在链没有重合部分的边连接并弹出
      if (lc != sta[top - 1]) { // 如果lc不是次栈顶，即lc在栈顶到次栈顶的边上
        connect(lc, sta[top]); // 连一条lc->sta[top]的边
        sta[top] = lc; // 将原栈顶弹出，压入lc 
      }
      else { // 如果lc就是次栈顶
        connect(lc, sta[top]); // 连边
        --top; // 弹出栈顶
      }
    }
    sta[++top] = x; // 将x压入栈
  }
  for (int i = 1; i < top; ++i) {
    connect(sta[i], sta[i + 1]); // 处理最后一条链
  }
}

1-3-3. 虚树上的DP

通过上面内容，我们已经建出了虚树，接下来就可以思考原 \text{DP} 到虚树上后的操作。

记 w(i) 为 i 到 1 路径上的边权的最小值。
记 dp(i) 为使 i 不与其子树内任意关键点连通的最小代价。

在虚树上遍历。 对于遍历到的点 x ，枚举其子节点 y :

其中，temp 初始为 0 ，dp(x) \gets \min \{ temp,w(x) \}

最终答案为 dp(1) 。

1-4. 代码（以二次排序+LCA连边为例）

code

2. 练习

2-1. [HNOI2014] 世界树

2-1-1. 思路：

按照模板建完虚树后，我们发现这题的 \text{DP} 有点恶心。

下面给出 \text{DP} 大致思路：

具体见下：

在每个点建立二元组 (\text{key},\text{dis}) ，其中 \text{key} 表示该点所属的关键点，\text{dis} 为该点到所属关键点的距离。

定义二元组 (\text{key},\text{dis}) 的大小比较为先按 \text{dis} 比，若相同，再按 \text{key} 比。

第一遍遍历，用子节点 y 更新当前节点 x ：

第二遍遍历，用当前节点 x 更新其子节点 y :

第三遍遍历，统计最终答案。对于当前遍历到达的点 x：

2-1-2. 代码：

code

2-2. [HEOI2014] 大工程

2-2-1. 思路

本题每次询问有三个输出，我们分开来思考。

先建一颗虚树，其上每条边的边权为两端点在原树上的距离。

对于第一个输出，询问 新通道的代价和 ，我们只需将虚树上每条边乘以它的贡献次数即可。
注意到，对于虚树上边 x\to y ，其对总答案的贡献为 son_y \times (k-son_y) 。其中 son_y 为点 y 的子树（包括点y）里关键点的个数，k 为总关键点数。

对于第二个输出，询问 新通道中代价最小的是多少 。我们在遍历时维护每个点到其子树中关键点的最短路长度和次短路长度（这两个关键点不应属于该点的同一个子节点），最后相加，再在所有点的最小值 + 次小值中取最小即可。

对于第三个输出，询问 新通道中代价最大的是多少 ，我们参照输出二，只是将维护内容改为最大和次大，最终再所有点的 最大值 + 次大值 中取最大即可。

注意开 \text{long long} 。

2-2-2. 代码

code

2-3. Kingdom and its Cities

2-3-1. 思路

首先我们发现，若存在父子节点都是关键点，则敌方目标不能达成，答案为 -1 。
然后我们再来考虑敌方至少要占几个非关键点。

先建虚树，再进行 \text{DP} 。
对于遍历到的点 x ，记其子节点为 y ：

统计所有断开点即为答案。

2-3-2. 代码

code

2-4. [SDOI2018] 战略游戏

2-5. [WC2018] 通道