问题理解

我们有一棵 $n$ 个节点的树，根节点为 $1$（敌军总部）。
树边有炸毁代价 $w$。
每次任务给出 $k_i$ 个资源点（不含根节点 $1$），要求：

• 删除一些边，使得根节点 $1$ 与所有资源点不连通
• 最小化删除边的总代价

关键约束：$m$ 次查询，$\sum k_i \leq 5\times 10^5$，但 $n$ 可达 $2.5\times 10^5$。

---

关键观察

1. 问题转化

这是一个树上最小割问题：
要切断根节点 $1$ 到所有资源点的路径，等价于在 $1$ 与资源点集合之间求最小割。

在树上，最小割有简洁性质：
最小割 = 根节点到所有资源点路径的边集的最小权覆盖

2. 朴素解法及问题

对每次查询，如果直接在原树上 DP：

• 状态：$dp[u]$ 表示切断 $u$ 子树中所有资源点所需的最小代价
• 转移：$dp[u] = \min(\sum_{v \in son(u)} dp[v],\ min\_edge(u, parent))$
• 复杂度：每次 $O(n)$，总 $O(mn)$，不可行

3. 优化思路

由于 $\sum k_i$ 有限，但 $n$ 很大，需要减少每次处理的节点数。
解决方案：虚树（Virtual Tree）

---

虚树技术

什么是虚树

对给定的关键点集合 $S$（包括根），虚树保留：

• 所有关键点
• 关键点两两的 LCA
• 根节点

虚树规模：$O(|S|)$

为什么有效

在最小割问题中，只有关键点及其 LCA 处的决策影响结果，中间节点可以压缩。

---

算法框架

预处理

1. 树结构预处理：

   • DFS 遍历，记录欧拉序、深度、父节点信息
   • 倍增 LCA 预处理（或 ST 表 + 欧拉序）

2. 边权预处理：

   • 记录每个节点到父节点的边权 $minEdge[u]$

每次查询处理

1. 构建虚树：

   • 关键点 = $\{1\} \cup \{h_1, h_2, \dots, h_{k_i}\}$
   • 按 DFS 序排序，相邻求 LCA，加入虚树点集
   • 根据 DFS 序和深度构建虚树边

2. 虚树上 DP：

   • $dp[u]$：切断 $u$ 在虚树中子树的所有资源点的最小代价
   • 初始化：
     • 如果 $u$ 是资源点：$dp[u] = \infty$（必须切断其与父亲的边）
     • 否则：$dp[u] = 0$
   • 转移：
     • 设 $u$ 在虚树中的儿子为 $v_1, v_2, \dots, v_t$
     • $cost = \sum dp[v_i]$
     • $dp[u] = \min(cost, minEdge[u])$
       • 其中 $minEdge[u]$ 是原树中 $u$ 到父节点的边权

3. 答案：$dp[1]$（根节点的 DP 值）

---

虚树构建细节

步骤

1. 关键点按 DFS 序排序
2. 相邻点求 LCA，加入点集
3. 再次按 DFS 序排序去重
4. 用栈构建虚树：
   • 维护一条从根到当前节点的链
   • 根据 DFS 序和深度关系确定父子关系

虚树边权

虚树边 $(u,v)$ 的权值取原树路径 $u\to v$ 上的最小边权。
但本题中，由于转移只用到节点到父节点的边权，实际上只需记录 $minEdge[u]$。

---

正确性分析

为什么虚树 DP 正确

• 资源点：必须被切断，所以 $dp[u] = \infty$ 迫使选择割掉 $u$ 与父节点的边
• 非资源点：可以选择割掉与父节点的边，或者承担所有儿子的代价
• 虚树保留了所有关键决策点，压缩的路径不影响最小割值

时间复杂度

• 预处理：$O(n \log n)$
• 每次查询：
  • 排序 + 求 LCA：$O(k_i \log k_i)$
  • 虚树 DP：$O(k_i)$
• 总复杂度：$O((n + \sum k_i) \log n)$，可接受

---

样例分析

样例树结构（简化）：

1--5--6
|  |
9  7--8--10
|
2--4
|
3

边权见输入。

第一次查询：资源点 $\{10, 6\}$
虚树包含：1, 5, 6, 7, 10 等节点
最小割需要割掉 1-5(13) 和 5-6(8) 中的较小者等，计算得 12。

第二次查询：资源点 $\{5,7,8,3\}$
需要割掉更多边，代价 32。

第三次查询：资源点 $\{9,4,6\}$
代价 22。

---

总结

这道题的核心是：

1. 问题识别：树上根到叶集的最小割
2. 虚树技术：压缩树规模，只保留关键点
3. 树形DP：在虚树上做最小割决策
4. LCA预处理：高效构建虚树

通过虚树，将每次查询复杂度从 $O(n)$ 降为 $O(k_i \log k_i)$，从而处理大规模数据。