虚树
2025-11-26
在算法竞赛中,我们经常遇到在树上进行操作或查询的问题。当树的规模非常大(比如 $N$ 个节点, $N$ 可以达到 $10^5$ 或 $10^6$),而每次查询只涉及树中的少数几个关键节点(比如 $k$ 个节点, $k$ 远小于 $N$)时,如果我们的算法复杂度与 $N$ 相关,例如每次查询都遍历整棵树或者大部分树的结构,那么即使单次查询的复杂度是 $O(N)$ 或 $O(N \log N)$,在多组查询下也可能会超时。
这时候,我们就需要一种方法,能够根据当前查询所涉及的这些少量关键节点,动态地构建一棵“临时”的、规模更小的树,这棵树只包含这些关键节点以及它们之间路径上的必要“拐点”(即它们的最近公共祖先LCA)。在这棵小树上进行操作或计算,其复杂度将主要与 $k$ 相关,而不是 $N$。这,就是虚树的核心思想。
1. 为什么要学习虚树?
想象一下,你面前有一张巨大的城市地铁网络图(原始树 $T$),包含了成百上千个站点。现在,你的任务是规划一条只连接其中5个特定站点(关键节点)的最优游览路线。你真的需要考虑所有几百个站点和它们之间的每一段轨道吗?显然不需要。你只需要关注这5个站点,以及连接它们所必须经过的换乘站(LCA)。把这些站点和它们之间的路径单独拎出来,形成一张小得多的线路图(虚树 $T'$),问题就简化多了。
虚树正是这样一种技术:
- 降维打击:它将问题规模从 $O(N)$ 降低到 $O(k)$ 的级别(通常是 $O(k \log N)$ 或 $O(k \log k)$ 用于构建,后续DP在虚树上是 $O(k)$)。
- 保留核心:它保留了关键节点之间的拓扑结构和路径信息。
- 应用广泛:常用于处理多次查询,每次查询涉及少量节点,需要在这些节点构成的子结构上进行树形DP、统计路径信息等问题。
很多涉及树上点集的题目,如果直接在原树上操作会因为规模太大而超时,虚树往往是解题的关键。例如,在一些需要对特定点集进行树形动态规划的问题中,如果每次都对整棵树进行DP,时间复杂度无法承受。而如果能在虚树上进行DP,复杂度就会大大降低。
2. 前置芝士
2.1 树的深度优先搜索 (DFS)
深度优先搜索,简称DFS,是我们遍历树(或图)结构最基本也是最强大的工具之一。它如同一个勇敢的探险家,沿着一条路径走到最深处,当无路可走时再回溯,尝试其他未探索的分支。
核心思想:DFS的核心在于“深入”。从起始节点出发,递归地访问其未被访问过的邻接节点,直到当前路径的尽头,然后回溯到上一个节点,继续探索其其他分支。
DFS序 (
dfn):在DFS的过程中,我们可以记录每个节点首次被访问到的“时间戳”或者说顺序。这个顺序就是该节点的DFS序,通常用一个从1开始(或0开始)递增的整数表示,记为dfn[u]。DFS序有一个非常美妙的性质:一个节点 $u$ 的子树中的所有节点,在DFS序上会形成一个连续的区间。这个性质对于判断节点间的祖先-后代关系、处理子树问题等都非常有用。在构建虚树时,将关键节点按照DFS序排序是至关重要的一步,它使得我们能够以一种有序、高效的方式(通常是利用栈)来构建虚树的结构。子树大小 (
sz):在DFS的过程中,当一个节点 $u$ 的所有子节点都访问完毕并回溯到 $u$ 时,我们就可以统计出以 $u$ 为根的子树中包含多少个节点(包括 $u$ 自身)。这个数量就是子树大小,记为sz[u]。子树大小在很多树形问题中都有应用,例如在树链剖分或点分治中。虽然在基础的虚树构建中不直接使用sz,但它是DFS能够提供的重要信息之一。节点深度 (
dep):节点 $u$ 的深度dep[u]指的是从根节点到节点 $u$ 的路径上边的数量(有时定义为节点数量,根节点深度为0或1,需根据具体场景统一)。深度信息在计算LCA时是必不可少的,它帮助我们判断节点的相对层级。
熟练掌握DFS,并能灵活运用其衍生的DFS序、子树大小、深度等概念,是理解树结构和许多高级树形算法的基础。对于虚树而言,DFS序是构建算法的灵魂,深度信息是LCA计算的依据。
2.2 最近公共祖先 (LCA)
最近公共祖先 (Lowest Common Ancestor, LCA),指的是在一棵有根树中,两个节点 $u$ 和 $v$ 的所有共同祖先中,深度最大的那一个。换句话说,它是 $u$ 和 $v$ “分叉”前的最后一个交汇点。
为何重要?:LCA在树上路径问题中扮演着核心角色。节点 $u$ 到节点 $v$ 的唯一简单路径,必然会经过 $LCA(u,v)$。这条路径可以被分解为 $u \leadsto LCA(u,v)$ 和 $LCA(u,v) \leadsto v$ 两段。在虚树的构建中,我们不仅需要包含所有给定的关键节点,还需要包含它们两两之间的LCA。这些LCA节点是构成虚树骨架的关键“拐点”,它们确保了关键节点之间的原始拓扑路径关系在虚树中得以保持。
求解方法:
- 向上标记法 (暴力):从一个节点(如 $u$)开始,不断跳向其父节点,并标记所有经过的祖先。然后从另一个节点(如 $v$)开始,同样不断跳向其父节点,遇到的第一个已被标记的节点即为 $LCA(u,v)$。这种方法对于单次查询可能是 $O(N)$ 的,效率较低。
- 倍增法 (Binary Lifting):这是在线查询LCA的常用高效方法。
- 预处理:通过一次DFS,我们可以预处理出每个节点 $u$ 的父节点 $fa[u][0]$,以及 $u$ 的第 $2^i$ 个祖先 $fa[u][i]$。递推关系为 $fa[u][i] = fa[fa[u][i-1]][i-1]$。同时记录每个节点的深度
dep[u]。预处理复杂度为 $O(N \log N)$。 - 查询:要查询 $LCA(u,v)$,首先将深度较大的节点(不妨设为 $u$)跳到与 $v$ 相同的深度。然后,如果此时 $u=v$,则 $u$ 就是LCA。否则,让 $u$ 和 $v$ 同时向上跳相同的高度,找到它们最浅的、不相同的祖先 $u'$ 和 $v'$。那么 $fa[u'][0]$ (或 $fa[v'][0]$) 就是它们的LCA。这个过程利用了二进制拆分思想,每次尝试跳 $2^i$ 步。查询复杂度为 $O(\log N)$。
- 预处理:通过一次DFS,我们可以预处理出每个节点 $u$ 的父节点 $fa[u][0]$,以及 $u$ 的第 $2^i$ 个祖先 $fa[u][i]$。递推关系为 $fa[u][i] = fa[fa[u][i-1]][i-1]$。同时记录每个节点的深度
- Tarjan算法 (离线):如果所有查询可以离线处理(即一次性读入所有查询,再统一计算),Tarjan算法利用并查集可以在均摊 $O((N+Q)\alpha(N))$ 的时间内完成所有LCA查询,其中 $\alpha$ 是反阿克曼函数,近似为常数。但在虚树构建这种通常需要在线响应每次查询的场景下,倍增法更为常用。
对于虚树,能够快速准确地计算任意两关键节点的LCA是构建算法的前提。倍增法因其 $O(\log N)$ 的在线查询效率和 $O(N \log N)$ 的可接受预处理开销,成为实现虚树时LCA计算的首选。
2.3 树形动态规划 (Tree DP)
树形动态规划是一种在树结构上进行动态规划的技术。其核心思想是将原问题分解为若干个与子树相关的子问题,通过子问题的解来合并得到原问题的解。
基本模式:
- 状态定义:DP状态通常定义在树的节点上,例如 $dp[u]$ 表示以 $u$ 为根的子树满足某种条件下的最优值、方案数等。状态中可能包含多个维度,如 $dp[u][0]$ 表示节点 $u$ 不选时的最优值,$dp[u][1]$ 表示节点 $u$ 选上时的最优值。
- 状态转移:通常通过一次DFS实现。在DFS回溯的过程中,当一个节点 $u$ 的所有子节点 $v_1, v_2, \dots, v_m$ 的DP值都已经计算完毕后,就可以根据这些子节点的DP值以及边 $(u, v_i)$ 的信息来计算 $dp[u]$。
- 基准情况:叶子节点的DP值通常作为DP的起始点。
与虚树的联系:虚树本身就是一棵树!当我们根据 $k$ 个关键节点构建出一棵规模为 $O(k)$ 的虚树后,很多原本需要在原树 $N$ 上进行的DP操作,现在可以在这棵小得多的虚树上进行。DP的原理和方法是相通的,只是作用的对象从原树变成了虚树。
- 状态的含义:虚树节点的DP状态 $dp[u]$ 可能需要考虑 $u$ 在原树中的身份(是原始关键点还是LCA中继点)以及虚树边 $(u,v)$ 所代表的原树路径的属性(例如路径长度、路径上边权最小值等)。
- 转移的特殊性:虚树边 $(u,v)$ 压缩了原树中的一条路径。因此,在DP转移时,这条虚树边的“权值”(即原树路径的属性)会成为重要的参数。例如,如果原问题是求最小代价,那么虚树边权可能是原路径上的最小割边代价。
理解树形DP的基本思想——如何定义状态、如何从子节点向父节点转移信息——对于在虚树上解决问题至关重要。因为虚树最终的目的,往往就是为了在其上高效地执行一次(或多次)类似树形DP的计算过程。
3. 虚树的构建
虚树的构建是其核心。目标是构建一棵只包含所有关键节点以及它们两两之间的LCA的树。这些LCA节点是必要的,因为它们是连接不同关键节点路径上的“分支点”或“合并点”。
假设我们有一系列关键节点 $S = \{v_1, v_2, \dots, v_k\}$。虚树的节点集合 $V'$ 将包含 $S$ 中的所有节点,以及 $S$ 中任意两个节点 $v_i, v_j$ 的 $LCA(v_i, v_j)$。虚树的边 $(u, v)$ 代表原树中 $u$ 到 $v$ 的唯一简单路径(其中 $u$ 是 $v$ 在虚树中的父亲)。
构建虚树的关键步骤如下:
3.1. 准备工作:DFS序与LCA
首先,对原树进行一次DFS,计算出每个节点的DFS序 (dfn)、深度 (dep),以及LCA所需的 fa[u][i](节点 $u$ 的第 $2^i$ 个祖先)。
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 300005, LOGN = 20; // 节点数和log N
vector<int> g[N]; // 原树邻接表
int dep[N], dfn[N], ti;
int fa[N][LOGN]; // fa[u][k] 表示 u 的第 2^k 个祖先
void dfs1(int u, int p) {
dfn[u] = ++ti;
dep[u] = dep[p] + 1;
fa[u][0] = p;
for (int i = 1; i < LOGN; ++i) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (int v : g[u]) {
if (v == p) continue;
dfs1(v, u);
}
}
int lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = LOGN - 1; i >= 0; --i) {
if (dep[fa[u][i]] >= dep[v]) {
u = fa[u][i];
}
}
if (u == v) return u;
for (int i = LOGN - 1; i >= 0; --i) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}dfs1: 完成DFS序、深度和倍增LCA预处理。时间复杂度 $O(N \log N)$。lca: 查询两个节点的LCA。时间复杂度 $O(\log N)$。
3.2. 关键节点的筛选与排序
给定 $k$ 个关键节点,首先将它们存入一个列表(例如 vector<int> key_nds)。 一个非常重要的步骤是:将所有关键节点按照DFS序排序。 为什么要按DFS序排序?这使得我们可以用一种类似扫描线的方式,结合栈来高效地构建虚树。排序后的节点在原树中的访问顺序,与DFS遍历这些节点的(部分)顺序一致,这使得维护当前虚树最右侧链(栈顶到栈底)变得容易。
// 假设 key_nds 存储了当前查询的 k 个关键节点
// sort(key_nds.begin(), key_nds.end(), [&](int a, int b) {
// return dfn[a] < dfn[b];
// });排序时间复杂度为 $O(k \log k)$。
3.3. 虚树的栈式构建算法
这是虚树构建最精妙的部分。我们使用一个栈 stk 来辅助构建。栈中存储的节点,从栈底到栈顶,依次是当前正在构建的虚树“最右侧链”上的节点。也就是说,栈顶元素是这条链上最深的节点,它的父节点(在虚树意义下)是栈顶下面的元素,以此类推。
算法流程:
- 初始化:清空虚树的邻接表
vt_g。栈stk初始化为空。 - 将按DFS序排序后的第一个关键节点
key_nds[0]压入栈stk。 - 遍历排序后的其余关键节点
u(从key_nds[1]到key_nds[k-1]): a. 如果栈为空,直接将u压栈。(实际上,由于我们先压入了第一个节点,这一步一般用不到,除非关键节点列表为空,但那没有意义)。 b. 计算u与栈顶元素stk.top()的LCA,记为l = lca(u, stk.top())。 c. 关键判断与操作: * 当栈顶元素stk.top()的深度大于l的深度时(即dep[stk.top()] > dep[l]),说明stk.top()位于l的子树中,而不是l本身或其祖先。这意味着stk.top()与u的路径在l处分叉。 * 我们将栈顶元素x = stk.top()弹出。 * 再看新的栈顶元素y = stk.top()(如果栈不空)。 * 如果dep[y] > dep[l],说明y也是l的后代(且是x在虚树链上的父亲),则在虚树中连边(y, x)。 * 否则(dep[y] <= dep[l]),说明l是x在虚树链上的父亲(或者y就是l),则在虚树中连边(l, x)。 * 重复此过程,直到栈顶元素的深度不大于l的深度。 d. 处理l: * 在弹出元素后,如果栈顶元素stk.top()不是l(即stk.top() != l),说明l是一个新的、需要加入到当前虚树路径上的“拐点”。此时,如果l不是stk.top()的父亲(即fa[stk.top()][0]不是l,但在虚树中,l应该是stk.top()弹掉后的那个节点的父亲),则需要将l也压入栈。更准确地说,如果栈顶元素x = stk.top()不是l,那么将l压栈前,若dep[x] > dep[l](这种情况是之前的while循环处理过的,x应该被弹出了),则l成为新的链的一部分。如果l与当前栈顶stk.top()不同,则将l压入栈。这个判断的目的是确保l作为连接点被正确地加入虚树的当前链中,并且保持栈中节点从底到顶深度递增且为祖先-后代关系。 * 更简洁的处理方式: 经过步骤 c 后,栈顶元素z = stk.top()必然是l的祖先或l本身。如果z != l,说明l不在当前栈所表示的链上,但它应该是u和z之间的一个拐点。此时,将z从栈中弹出,将l压入栈,然后在虚树中连接(l, z)。 e. 将当前关键节点u压入栈stk。 - 遍历结束后,栈中可能还剩下一些节点。它们构成了虚树最右边的一条链。依次弹出栈中元素,将弹出的节点与其下面的节点(新的栈顶)在虚树中连边。例如,弹出
x,若栈不空,则与stk.top()连边(stk.top(), x)。
代码实现 (build_vt 函数):
vector<int> vt_g[N]; // 虚树邻接表
bool is_key[N]; // 标记是否为关键节点 (可选,有时有用)
int stk[N], top; // 手动模拟栈
// 清理虚树边,用于多次查询
void clr_vt(int u) {
vt_g[u].clear();
}
void vt_add_edge(int u, int v) {
// 虚树中的边是有向的(从父到子)或无向均可,取决于后续算法
// 这里用有向边,方便DFS
// 边的权值通常是原树中 u 到 v 的距离,即 dep[v] - dep[u]
// 在某些题目中可能需要存储权值,这里仅建图
vt_g[u].push_back(v);
}
// kns: key nodes (已按dfn排序)
void build_vt(vector<int>& kns) {
// 1. 对关键节点按 dfn 排序 (调用前确保已排序)
// sort(kns.begin(), kns.end(), [&](int a, int b) { return dfn[a] < dfn[b]; });
// 2. 去重 (如果输入可能有重复)
// kns.erase(unique(kns.begin(), kns.end()), kns.end());
// 3. 将必要的LCA节点也加入考虑范围 (这一步是构建虚树的关键思想体现)
// 不过,更高效的栈式构建会自动处理LCA的加入,我们这里采用纯栈式构建
// 所以,kns 中初始只有给定的关键节点
top = 0; // 清空栈
// 虚树的节点是kns中的节点以及它们之间的LCA
// 为了方便清理,可以先收集所有虚树节点,再统一清理
vector<int> vt_nodes_to_clear;
// 第一个关键节点直接入栈
if (!kns.empty()) {
stk[++top] = kns[0];
vt_nodes_to_clear.push_back(kns[0]);
}
for (size_t i = 1; i < kns.size(); ++i) {
int u = kns[i];
if (top == 0) { // 栈空,通常不会发生,除非kns[0]未处理或kns为空
stk[++top] = u;
vt_nodes_to_clear.push_back(u);
continue;
}
int l = lca(u, stk[top]);
vt_nodes_to_clear.push_back(u); // u 肯定是虚树节点
// 当栈顶不是 l 的祖先时 (即 stk[top] 在 l 的不同子树,或 l 就是 stk[top])
// 或者说,当 l 不是 stk[top] 时,且 stk[top] 比 l 深
while (top > 1 && dep[stk[top-1]] >= dep[l]) {
// stk[top-1] 是 stk[top] 的父亲
// 如果 stk[top-1] 的深度还大于等于 l 的深度,
// 说明 stk[top-1] 也是 l 的孩子(或l本身),或者在l的另一个子树分支上但更浅
// 这意味着 stk[top-1] -> stk[top] 这条边是确定的
vt_add_edge(stk[top-1], stk[top]);
top--;
}
// 此时 stk[top] (原来的栈顶或其祖先) 与 l 的关系:
// 1. stk[top] == l
// 2. l 是 stk[top] 的祖先 (dep[stk[top]] > dep[l] 且 stk[top-1]是l的祖先或者不存在)
if (stk[top] != l) { // l 不是当前栈顶,说明 l 是一个拐点
// 原来的 stk[top] 应该成为 l 的孩子
vt_add_edge(l, stk[top]);
// top--; // 弹出原来的 stk[top] (现在它是l的孩子了)
// stk[++top] = l; // l成为新的栈顶
stk[top] = l; // 用 l 替换掉原来的 stk[top],因为原来的 stk[top] 已经作为 l 的孩子连边
vt_nodes_to_clear.push_back(l); // l也是虚树节点
}
stk[++top] = u; // 当前节点 u 入栈
}
// 栈中剩余的节点构成一条链,依次连接
while (top > 1) {
vt_add_edge(stk[top-1], stk[top]);
top--;
}
// 清理本次虚树中用到的节点的邻接表 (为下次查询做准备)
// sort(vt_nodes_to_clear.begin(), vt_nodes_to_clear.end());
// vt_nodes_to_clear.erase(unique(vt_nodes_to_clear.begin(), vt_nodes_to_clear.end()), vt_nodes_to_clear.end());
// for(int node : vt_nodes_to_clear) {
// vt_g[node].clear(); // 这样清理更精确
// }
// 注意:上面的清理方式是每次build都完整清理。如果虚树节点不多,可以这么做。
// 如果追求极致,可以在dfs遍历虚树后,只清理访问到的虚树节点的vt_g。
// 但一般推荐的方式是,在build_vt的开头,就对上次可能用到的节点进行清理。
// 这里的清理逻辑可以优化,比如只清理实际加入到vt_nodes_to_clear的节点。
// 实际上,更常见的做法是,在每次查询的开始,将上次构建虚树时加入的节点(可以单独记录)的vt_g清空。
// 上面代码的 vt_nodes_to_clear 收集了所有可能成为虚树节点的点,可以在 build_vt 的最开始用它来 clr_vt。
}代码逻辑的再梳理与简化(更标准的栈式写法) 上面的 build_vt 实现了一种思路,但我们可以参考一种更广为流传且逻辑更清晰的栈版本。
核心思想:栈 stk 维护一个从虚树根(或某个LCA)到当前最深节点的链,栈中节点深度单调递增,且 stk[i] 是 stk[i+1] 在原树中的祖先。
// vector<int> vt_g[N]; // 虚树邻接表 (假设已定义)
// void vt_add_edge(int u, int v); // 假设已定义
// int stk[N], top; // 假设已定义
// int dfn[], dep[], lca(u,v) // 假设已定义
// kns: key nodes, 必须先按 dfn 排序,并且去重
// 并且,为了方便处理,可以在 kns 中加入根节点1 (如果它不是关键点的话)
// 但通常不这么做,除非题目特性需要。
// 这里假设 kns 已经是纯粹的关键节点,按dfn排序,无重复。
void build_standard_vt(vector<int>& kns) {
if (kns.empty()) return;
// 清理工作:记录本次虚树涉及的节点,在函数末尾或下次调用前清理其 vt_g
static vector<int> vt_nds_snapshot;
for(int node : vt_nds_snapshot) vt_g[node].clear();
vt_nds_snapshot.clear();
top = 0;
stk[++top] = kns[0]; // 第一个关键点入栈
vt_nds_snapshot.push_back(kns[0]);
for (size_t i = 1; i < kns.size(); ++i) {
int u = kns[i];
int l = lca(u, stk[top]);
// 如果 l 就是 stk[top],说明 u 是 stk[top] 子树中的点,u可以直接接到stk[top]下面
// (实际上是 u 作为stk[top]的直接孩子或间接孩子,具体连接在后面处理)
// 关键在于栈的处理:
// 只要栈顶不是 l 的祖先 (即 l 在 stk[top] 和 stk[top-1] 之间,或者 l 就是 stk[top-1])
// 就需要调整栈
while (dep[stk[top-1]] >= dep[l]) { // 当 stk[top-1] 的深度比 l 深或相等
// 注意: stk[0] 通常是哨兵或不存在,所以top > 1
// 或者,让 stk[0] = 0, dep[0] = 0 这样可以避免 top > 1 的判断
// 这里假设 stk[0] 是一个虚拟的深度为0的节点,或者top从1开始,循环条件是 top-1 >= 1
// 如果用 stk[0] = 0, dep[0] = 0, 那么 stk[top-1] 可以是 stk[0]
// 这里的判断应该是: 只要 stk[top-1] 不是 l 的严格祖先,就需要弹出 stk[top] 并连接 stk[top-1] -> stk[top]
// stk[top-1] >= dep[l] 意味着 l 在 stk[top-1] 的子树中(或l=stk[top-1])
// 表明 stk[top-1] -- stk[top] 这条边可以确定
vt_add_edge(stk[top-1], stk[top]);
top--;
}
// 此时 stk[top] 是 l 的孩子,或者 stk[top] == l
if (stk[top] != l) { // 如果 l 不是当前栈顶 (说明 l 是新拐点,在 u 和原stk[top]之间)
vt_add_edge(l, stk[top]); // 原栈顶 stk[top] 成为 l 的孩子
// stk[top] = l; // l 替换原栈顶,成为链的一部分
// 因为 l 肯定也是虚树节点,要加入 snapshot
bool new_l_node = true;
for(size_t j=0; j<vt_nds_snapshot.size(); ++j) if(vt_nds_snapshot[j] == l) new_l_node = false;
if(new_l_node) vt_nds_snapshot.push_back(l);
stk[top] = l; // l 替换掉原来的 stk[top] (现在它是l的孩子了)
}
stk[++top] = u; // 当前节点 u 入栈
bool new_u_node = true;
for(size_t j=0; j<vt_nds_snapshot.size(); ++j) if(vt_nds_snapshot[j] == u) new_u_node = false;
if(new_u_node) vt_nds_snapshot.push_back(u);
}
// 栈中剩余的节点构成一条链
while (top > 1) {
vt_add_edge(stk[top-1], stk[top]);
top--;
}
// 此时 stk[1] 是虚树的根 (或根之一)
}关于 vt_nds_snapshot 和清理: 在多次查询的场景下,虚树的结构每轮都会改变。因此,每次构建新的虚树前,需要清除旧虚树的边。一个好的做法是记录下每一轮虚树实际包含的节点,然后在下一轮构建前,只清理这些节点的出边列表 vt_g[node]。vt_nds_snapshot就是用来做这个的。 另一种方法,如果题目保证所有关键点+LCA的总数不多,可以每次都把1到N所有节点的vt_g清一遍,但这显然不够优。 更好的方式是,build_vt 函数返回一个包含所有虚树节点的 vector<int>,调用者在获取这个列表后,在适当的时候(比如DP完毕后)进行清理。或者像 build_standard_vt 中使用 static vector 来自动管理。
复杂度分析:
- DFS预处理:$O(N \log N)$ 或 $O(N)$ (如果用Tarjan LCA等)。
- 对 $k$ 个关键节点排序:$O(k \log k)$。
- 栈式构建:
- 每个关键节点入栈一次。
- 每个LCA节点最多入栈一次(当它成为新的拐点时)。
- 总共入栈的节点数不超过 $2k$($k$个关键节点 + 最多 $k-1$ 个LCA)。
- 每个节点出栈一次。
- 每次LCA计算 $O(\log N)$。
- 总共LCA计算次数 $O(k)$。
- 所以栈式构建本身是 $O(k \log N)$。
因此,一次虚树构建的总时间复杂度是 $O(N \log N + Q \cdot (k \log k + k \log N))$ 如果每次查询都重新排序。如果 $k$ 个节点在输入时就已按DFS序给出,或者是可以 $O(k)$ 预处理得到DFS序(比如对 $k$ 个节点单独做一次类似桶排序的dfn值提取),则可以优化到 $O(N \log N + Q \cdot k \log N)$。通常,排序的 $k \log k$ 是不可避免的。
虚树的节点数最多为 $2k-1$ (当 $k$ 个关键点形成一条链,或者像菊花图那样散开,它们的LCA可能是根)。边数是节点数减1。
3.4. 虚树边的权值
虚树中的一条边 $(u, v)$ (假设 $u$ 是 $v$ 在虚树中的父亲) 实际上代表了原树中 $u$到$v$的路径。如果我们需要在这条路径上做一些操作,或者这条路径的长度/属性很重要,那么我们需要定义虚树边的权值。 最常见的权值是原树中的距离:$w(u,v) = \text{dist}(u,v) = \text{dep}[v] - \text{dep}[u]$。 在某些问题中,权值可能是路径上最小/最大的边权,或者其他可以通过树链剖分+线段树等结构在 $O(\log N)$ 内查询的路径信息。如果只是简单的距离,dep数组就够了。
4. 虚树应用实例:树上路径信息统计
我们来看一个经典的虚树应用场景。
题意概括: 给定一棵 $N$ 个节点的树,边有边权。有 $M$ 次询问,每次询问给出 $k$ 个关键节点。要求计算这些关键节点中,所有点对 $(u,v)$ 之间的最短路径长度之和,对一个大质数取模。 或者,一个更简化但能体现虚树DP的问题:对于每次询问的 $k$ 个关键节点,计算将这些节点从原树中删除后,会形成多少个连通块。(这个问题与著名的 "割点" 问题类似,但这里我们更关注虚树上的DP)。 或者,计算包含所有 $k$ 个关键节点的最小连通子图的总边权和。
我们选择 "包含所有 $k$ 个关键节点的最小连通子图的总边权和" 作为例子。 这个最小连通子图实际上就是这些关键节点以及它们两两之间的LCA构成的虚树所有边的权值之和。
解题思路:
- 对原树进行DFS,预处理
dep(带权深度,即到根的路径权值和)、dfn、fa(用于LCA)。 - 对于每次查询: a. 读入 $k$ 个关键节点。 b. 将关键节点按
dfn排序。 c. 使用栈式算法构建虚树。在vt_add_edge(u, v)时,这条边的权值就是原树中 $u$ 到 $v$ 的路径长度,即 $dep[v] - dep[u]$。 d. 在虚树上进行一次DFS。从虚树的某个(虚拟)根出发(通常是dfn最小的那个关键点,或者是所有关键点LCA最浅的那个,栈顶stk[1]就是这样的一个节点)。DFS过程中累加所有边的权值。
核心代码示例 (计算最小连通子图总边权):
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 250005, LOGN = 19; // 节点数和log N
struct Edge {
int to;
ll w;
};
vector<Edge> g[N]; // 原树邻接表
ll dep_w[N]; // 带权深度,到根的路径权值和
int dep_n[N], dfn[N], ti; // 节点深度(层数),dfs序, 时间戳
int fa[N][LOGN];
vector<pair<int, ll>> vt_g[N]; // 虚树邻接表, 存 {v, weight}
bool is_key_node[N]; // 标记是否为关键节点
void dfs1(int u, int p, ll current_w_sum, int current_d_n) {
dfn[u] = ++ti;
dep_w[u] = current_w_sum;
dep_n[u] = current_d_n;
fa[u][0] = p;
for (int i = 1; i < LOGN; ++i) {
fa[u][i] = fa[fa[u][i - 1]][i - 1];
}
for (const auto& edge : g[u]) {
int v = edge.to;
ll w = edge.w;
if (v == p) continue;
dfs1(v, u, current_w_sum + w, current_d_n + 1);
}
}
int lca(int u, int v) {
if (dep_n[u] < dep_n[v]) swap(u, v);
for (int i = LOGN - 1; i >= 0; --i) {
if (dep_n[fa[u][i]] >= dep_n[v]) { // dep_n[0] 需设为0或-1
u = fa[u][i];
}
}
if (u == v) return u;
for (int i = LOGN - 1; i >= 0; --i) {
if (fa[u][i] != fa[v][i]) {
u = fa[u][i];
v = fa[v][i];
}
}
return fa[u][0];
}
int stk[N], top;
vector<int> vt_nodes_curr_query; // 存储当前查询虚树中的所有节点,用于清理
void vt_add_edge(int u, int v) {
ll weight = dep_w[v] - dep_w[u];
vt_g[u].push_back({v, weight});
// 如果是无向图的应用,可以考虑 vt_g[v].push_back({u, weight});
// 但通常建单向的从父到子,方便DFS
vt_nodes_curr_query.push_back(u); // 记录用到的节点
vt_nodes_curr_query.push_back(v);
}
void build_vt(vector<int>& kns) { // kns 必须按 dfn 排序
if (kns.empty()) return;
for(int node : vt_nodes_curr_query) vt_g[node].clear();
vt_nodes_curr_query.clear();
top = 0;
stk[++top] = kns[0];
vt_nodes_curr_query.push_back(kns[0]);
for (size_t i = 1; i < kns.size(); ++i) {
int u = kns[i];
if (u == stk[top]) continue; // 关键点可能重复,排序后去重是个好习惯
// 或者在这里跳过相同的,如果kns未去重
int l = lca(u, stk[top]);
while (dep_n[stk[top-1]] >= dep_n[l]) { // stk[0]的dep_n应为0或-1
// 确保 stk[top-1] != 0 (真实节点)
vt_add_edge(stk[top-1], stk[top]);
top--;
}
if (stk[top] != l) {
vt_add_edge(l, stk[top]);
stk[top] = l;
// l 可能是新加入的点,也要记录
// vt_nodes_curr_query.push_back(l); // vt_add_edge里会加
}
stk[++top] = u;
// vt_nodes_curr_query.push_back(u); // vt_add_edge里会加
}
while (top > 1) {
vt_add_edge(stk[top-1], stk[top]);
top--;
}
}
ll total_edge_sum;
void dfs_on_vt(int u) {
// is_key_node[u] 可以用来区分关键节点和LCA中继点
// 对于本题 "最小连通子图总边权和",我们只需累加所有虚树边的权值
for (const auto& edge : vt_g[u]) {
int v = edge.first;
ll w = edge.second;
total_edge_sum += w;
dfs_on_vt(v);
}
}
int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n_nodes;
cin >> n_nodes;
// fa[0][..]应指向自己或一个不存在的节点0,dep_n[0] = 0
// dep_w[0] = 0
for(int i=0; i<n_nodes-1; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
g[u].push_back({v, w});
g[v].push_back({u, w});
}
dfs1(1, 0, 0, 1); // 假设1是根, 父节点0, 初始权和0, 深度1
// dep_n[0]应小于任何真实节点深度,如0。fa[1][0]是0。
int q_queries;
cin >> q_queries;
while (q_queries--) {
int k_cnt;
cin >> k_cnt;
vector<int> key_nds(k_cnt);
for (int i = 0; i < k_cnt; ++i) {
cin >> key_nds[i];
is_key_node[key_nds[i]] = true; // 标记关键节点 (本题不直接用,但DP时常用)
}
sort(key_nds.begin(), key_nds.end(), [&](int a, int b) {
return dfn[a] < dfn[b];
});
// 去重,如果题目保证关键点不重复,或重复不影响逻辑则可省略
key_nds.erase(unique(key_nds.begin(), key_nds.end()), key_nds.end());
build_vt(key_nds);
total_edge_sum = 0;
if (!key_nds.empty()) { // 虚树的根是 stk[1]
dfs_on_vt(stk[1]); // 栈底是虚树的根
}
cout << total_edge_sum << "\n";
// 清理 is_key_node 标记 (如果使用了)
for (int node_val : key_nds) is_key_node[node_val] = false;
// 对于LCA节点,如果也标记了,也要清理
// 更稳妥的是在build_vt中,凡是加入vt_nodes_curr_query的点,都记录下来然后统一清is_key_node
}
return 0;
}代码说明与分析:
- 预处理:
dfs1计算 DFS 序dfn,节点在树中的层数dep_n(用于LCA比较),到根的路径权值和dep_w(用于计算虚树边权),以及LCA所需的fa数组。复杂度 $O(N \log N)$。 - LCA: 标准倍增LCA。复杂度 $O(\log N)$。
build_vt函数:- 接收按
dfn排序好的关键节点kns。 vt_nodes_curr_query: 用于存储本次虚树构建实际涉及到的所有节点(关键节点+LCA节点)。在函数开始时,遍历这个vector,清空其中每个节点在vt_g中的邻接表。然后清空vt_nodes_curr_query本身。- 栈
stk用于构建。stk[0]可以看作一个虚拟节点,dep_n[stk[0]]极小 (例如0),dfn[stk[0]]极小。这样while(dep_n[stk[top-1]] >= dep_n[l])在top=1时(即stk[top-1]是stk[0])会自动停止。 vt_add_edge(u, v): 连接虚树中的边,权值为dep_w[v] - dep_w[u]。同时将u和v加入vt_nodes_curr_query。- 核心栈操作逻辑如前所述。注意
stk[top] = l这一步,是将新找到的LCA节点l替换掉原栈顶(该原栈顶已作为l的孩子连接),使l成为链上的一部分。 - 最后处理栈中剩余边。
- 复杂度 $O(k \log k + k \log N)$。
- 接收按
dfs_on_vt函数:- 一个简单的DFS,遍历虚树,累加所有边的权值到
total_edge_sum。 - 虚树的根是构建完毕后
stk[1](栈中唯一剩下的元素)。 - 复杂度 $O(k')$,其中 $k'$ 是虚树中的节点数($k' \le 2k$)。
- 一个简单的DFS,遍历虚树,累加所有边的权值到
main函数:- 读入树结构,调用
dfs1预处理。 - 对于每个查询:
- 读入关键节点,存入
key_nds。 - 按
dfn排序。重要:排序后要去重unique,否则相同的节点会导致LCA计算和栈操作异常。 - 调用
build_vt构建虚树。 - 调用
dfs_on_vt在虚树上计算答案。 - 输出答案。
- (可选) 清理
is_key_node标记,如果DP中需要区分关键节点和LCA中继点。
- 读入关键节点,存入
- 读入树结构,调用
- 总复杂度: $O(N \log N + \sum (k \log k + k \log N))$。如果 $\sum k$ 不是很大,这是可以接受的。
这个例子展示了虚树的基本用法:将原树问题转化为在规模小得多的虚树上的问题。这里的 "计算总边权" 是一个非常简单的DP(其实就是个DFS求和)。更复杂的问题可能需要在虚树上进行复杂的树形DP。
5. 在虚树上进行动态规划 (DP on Virtual Tree)
虚树的威力很大程度上体现在它能够将原树上针对特定点集的复杂DP问题,简化为在规模小得多的虚树上的DP。由于虚树保留了关键节点间的核心拓扑关系和路径信息,许多原树上的DP思想可以平移过来。
5.1. DP设计要点
- 状态定义:DP状态通常定义在虚树的节点上。这个状态需要蕴含原树中与该虚树节点相关联的子问题的信息。例如,$dp[u]$ 可能表示在以 $u$ 为根的虚树子树中,满足某种条件下的最优值或方案数。
- 边权利用:虚树的边 $(u, v)$ 代表原树中的一条路径。这条路径的属性(如长度、路径上边权最小值/最大值、路径上特定节点数等)往往是DP转移的关键。务必正确计算和使用这些“压缩路径”的信息。
- 关键节点与LCA节点的区分:在DP时,原始的关键节点和因LCA而加入虚树的辅助节点,它们的处理方式可能不同。通常会用一个
isk[u]标记来区分。 - DFS序/拓扑序:在虚树上进行DP通常也是通过DFS(自底向上更新)或按拓扑序进行。
5.2. 经典实例:SDOI2011 消耗战 / BZOJ2286 消耗战
这是一个非常经典的虚树DP题目,能很好地体现上述要点。
题意概括: 给定一棵 $N$ 个节点的树,根为1,每条边有正边权(可以理解为“割断”这条边的代价)。有 $M$ 次询问,每次询问给出 $k$ 个关键节点。要求对于每次询问,计算使得这 $k$ 个关键节点都与根节点1不连通的最小总代价。一个节点与根节点1不连通,指的是从根节点1到该节点的路径上至少有一条边被割断。
解题思路:
预处理:
- 对原树进行DFS,计算
dep(节点深度/层数,根为1层),dfn(DFS序),fa[u][i](倍增LCA)。 - 额外预处理
mc[u][i]:表示原树中节点 $u$ 到其第 $2^i$ 个祖先 $fa[u][i]$ 的路径上,所有边权中的最小值。mc[u][0]就是 $u$ 与其父节点 $fa[u][0]$ 之间边的权值。mc[u][i] = min(mc[u][i-1], mc[fa[u][i-1]][i-1])。
- 这个
mc数组用于快速查询原树中两点 $u,v$ ( $u$ 是 $v$ 的祖先) 路径 $(u,v]$ 上的最小边权。我们将编写一个函数gme(u, v)(get min edge) 来实现这个查询。
- 对原树进行DFS,计算
对于每次查询: a. 读入 $k$ 个关键节点。 b. 将这 $k$ 个节点按
dfn排序并去重。 c. 构建虚树。虚树的边 $(u,v)$ (设 $u$ 是 $v$ 在虚树中的父亲) 的权值,应该是原树中路径 $u \leadsto v$ 上的最小边权,这个权值用gme(u, v)计算。 d. 在虚树上进行树形DP。设 $dp[u]$ 表示:在以 $u$ 为根的虚树子树中,割断一些边使得该子树中所有(原始的)关键节点都与 $u$ 不连通(最终目标是与根1不连通,DP状态通常定义为与当前子树根 $u$ 不连通,再结合 $u$ 与其父节点的边)的最小代价。 * DP状态 $dp[u]$: 使得 $u$ 的虚树子树中所有原始关键节点与根节点1不连通,并且 $u$ 与其在虚树中的父亲之间的连接状态也已确定的最小代价。更准确地说,对于 "消耗战" 这类问题,$dp[u]$ 通常定义为:确保 $u$ 的虚树子树内所有关键节点与 $u$ (或者说,与 $u$ 的原树父亲,间接与根1)断开的最小代价。 * DP转移 (在虚树上DFS,自底向上): 对于虚树节点 $u$ 和它在虚树中的一个孩子 $v$: 令 $w_{uv} = \text{gme}(u,v)$,即原树中路径 $u \leadsto v$ 的最小边权。 从孩子 $v$ 处贡献到 $u$ 的代价是 $\min(dp[v], w_{uv})$。这表示要么在 $v$ 的子树内部解决(代价 $dp[v]$),要么割断连接 $u,v$ 的这条路径(代价 $w_{uv}$)。 $S_u = \sum_{v \text{ child of } u \text{ in VT}} \min(dp[v], w_{uv})$。 如果 $u$ 是一个原始关键节点 (isk[u]为真):$dp[u] = S_u$。因为它自己必须与根1断开,这依赖于其子树的贡献或者它与虚树父亲的边被切断。 如果 $u$ 不是原始关键节点 (它是一个LCA节点,或者是根节点1且1不是原始关键点): $dp[u] = \min(S_u, \text{mc}[u][0])$。其中 $\text{mc}[u][0]$ 是原树中 $u$ 与其父节点 $fa[u][0]$ 之间的边权 (如果是根节点1,则此代价为 $\infty$)。这表示 $u$ 作为一个中转点,可以选择让其子树内的关键点通过上述方式与 $u$ 断开,或者直接切断 $u$ 与它在原树中的父亲的连接(如果这条边代价更小)。 e. 最终答案是 $dp[root\_of\_VT]$。虚树的根是栈底元素stk[1]。
核心代码示例 (消耗战):
#include <bits/stdc++.h>
using namespace std;
using ll = long long; // 定义 long long 别名
const int N = 250005; // 最大节点数
const ll LINF = 4e18; // long long 类型的无穷大 (原inf过大,调整)
// const int MOD = 1000000007; // 如果需要取模
struct Ed { // 边结构 (原edge)
int v, nxt; // v: 边的终点, nxt: 下一条边的索引
ll w; // w: 边权
} e[N << 1]; // 邻接表存储边,双向边所以是 N*2
int head[N], ecnt; // head: 邻接表头指针, ecnt: 边的计数器
int n, q_cnt; // n: 节点数, q_cnt: 查询次数
int dfn[N], dfn_clk; // dfn: DFS序, dfn_clk: DFS序时间戳
ll min_w[N]; // min_w[u]: 节点u到其原树根节点路径上的最小边权 (原mi数组)
// 注意:原代码mi[v] = min(mi[u], e[i].w)的语义是u到v路径上的最小边权
// 如果题目是“消耗战”类型,通常mi[u]是u到其父节点的边权
// 这里根据原代码逻辑,mi[u]似乎是继承自父节点的路径最小值,加上当前边的比较
// 对于“消耗战”,mi[u]通常是u到fa[u]的边权,或者dp时用特定路径查询
// 根据原dp(u) { if(v[u].size()==0) return mi[u]; }
// mi[u]似乎是节点u自身的一个属性值,而不是到根的。
// 如果是消耗战,mi[u]应该是割断u与其父节点连接的代价。
// 假设mi[u]是题目定义的某种与节点u相关的代价下限
// 树链剖分相关数组
int sz[N], fa[N], top[N], son[N], dep[N];
// 虚树构建用的栈和栈顶指针
int stk[N], st_top;
vector<int> vt_g[N]; // 虚树邻接表 (原v数组)
int q_nodes[N]; // 存储单次查询的关键节点 (原is数组)
// 添加原树的边 (双向)
void add_edge(int u, int v, ll w) {
e[++ecnt] = {v, head[u], w};
head[u] = ecnt;
e[++ecnt] = {u, head[v], w};
head[v] = ecnt;
}
// 比较函数,用于按DFS序排序
bool cmp_dfn(int a, int b) {
return dfn[a] < dfn[b];
}
// DFS1: 计算sz, fa, dep, son,并预处理min_w
// min_w[u] 在原代码中 dfs1(1,0), mi[1]=inf, mi[v]=min(mi[u], e[i].w)
// 这表示 mi[u] 是从根到 u 路径上所有边权的最小值
// 这与 "消耗战" 中的 mnc[u][0] (u到父节点的边权) 不同。
// 需要根据题目具体含义确定 min_w 的正确计算方式。
// 假设 min_w[u] 是题目定义的每个节点的固定“基础代价”
void dfs1(int u, int p, ll cur_min_edge_to_u) {
sz[u] = 1;
fa[u] = p;
dep[u] = dep[p] + 1;
min_w[u] = cur_min_edge_to_u; // 如果min_w是u到父节点的边权,则直接是这条边的w
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
ll w = e[i].w;
if (v == p) continue;
// 如果 min_w[v] 是 v 到其父节点 u 的边权:
// dfs1(v, u, w);
// 如果 min_w[v] 是根到 v 路径上的最小边权 (如原代码的mi):
dfs1(v, u, min(cur_min_edge_to_u, w));
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
}
}
// 针对 “消耗战” 类型,min_w[u] 应该是 u 与其原树父亲的边权
// 那么 dfs1 调用应为 dfs1(1, 0, LINF); (根的父边代价无穷)
// 内部 dfs1(v, u, w);
// 我们先按原代码的 mi 含义(根到u路径最小边权)来调整,但指出这可能不是消耗战标准做法。
// 如果 min_w[u] 是节点u的固定代价(与路径无关),则应在读入时或特定逻辑中赋值。
// 鉴于 dp 叶子返回 mi[u],mi[u] 很可能就是与节点u绑定的一个基础成本。
// 我们将 min_w[u] 理解为节点 u 的一个固有属性值,在 dfs1 中不修改它,假设它被其他方式初始化。
// 或者,如果它是u到父节点的边权,那么:
void dfs1_alt(int u, int p) { // p是u的父亲
sz[u] = 1;
fa[u] = p;
dep[u] = dep[p] + 1;
// min_w[u] 在这里不通过dfs1传递和计算,假设它预先设定或题目直接给出
// 或者 min_w[u] = cost_edge_to_parent(u);
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
ll w = e[i].w; // 边 (u,v) 的权值
if (v == p) continue;
min_w[v] = w; // min_w[v] 是 v 到其父节点 u 的边权
dfs1_alt(v, u);
sz[u] += sz[v];
if (sz[son[u]] < sz[v]) son[u] = v;
}
}
// DFS2: 计算top (重链顶点) 和 dfn (DFS序)
void dfs2(int u, int t_node) { // t_node: u所在重链的顶端节点
top[u] = t_node;
dfn[u] = ++dfn_clk;
if (!son[u]) return; // 叶子节点
dfs2(son[u], t_node); // 优先处理重儿子
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].v;
if (v != fa[u] && v != son[u]) {
dfs2(v, v); // 轻儿子开始一条新的重链
}
}
}
// LCA查询 (基于树链剖分)
int lca(int u, int v) {
while (top[u] != top[v]) {
if (dep[top[u]] > dep[top[v]]) {
u = fa[top[u]];
} else {
v = fa[top[v]];
}
}
return dep[u] < dep[v] ? u : v;
}
// 虚树构建:将节点x加入栈中维护的链
void vt_push(int x) {
if (st_top == 1 && stk[st_top] == 1 && x == 1) return; // 避免根节点重复处理 (如果根节点总是入栈)
// 原代码是 s[t=1]=1,即根节点1强制入栈。
// 如果x就是栈顶,不处理 (原代码 l==s[t] return)
if (st_top > 0 && stk[st_top] == x) return; // x 已经是栈顶
if (st_top == 0) { // 栈空,直接入栈 (原代码 t=1, s[1]=1 已处理第一个,这是后续的)
stk[++st_top] = x;
return;
}
int l = lca(x, stk[st_top]); // 当前节点与栈顶的LCA
// 如果lca就是栈顶,说明x是栈顶的子孙,x可以安全地压入栈,等待后续连接
// (原代码 if(l == s[t]) return; -> 这里改为不return,而是让x入栈,在最后处理栈内剩余边)
// 这一句 return 的原意可能是:如果x的lca是栈顶,那么x和栈顶在一条直链上,不需要lca作为拐点。
// 但x本身还是关键点,需要入栈。
// 正确的栈式构建,l == stk[st_top]时,x应该入栈,stk[st_top]是x在虚树中的父亲。
// 当lca不是当前栈顶stk[st_top]时,需要弹出一些节点并连接虚树边
// 直到stk[st_top-1]是lca的祖先(或lca本身)
while (st_top > 1 && dfn[stk[st_top - 1]] >= dfn[l]) {
// dfn[stk[st_top-1]] >= dfn[l] 意味着 stk[st_top-1] 在 l 的子树中,
// 或者 stk[st_top-1] 就是 l (如果l在栈内)
// 这也意味着 stk[st_top-1] 是 stk[st_top] 在虚树中的父亲
vt_g[stk[st_top - 1]].push_back(stk[st_top]);
st_top--;
}
// 此时 stk[st_top] 是 lca 的孩子,或者 stk[st_top] == lca
if (stk[st_top] != l) { // 如果栈顶还不是lca, 说明lca是一个新的拐点
vt_g[l].push_back(stk[st_top]); // 原栈顶成为lca的孩子
stk[st_top] = l; // lca取代原栈顶,成为链的一部分
// (如果l不在vns中,需要加入vns。但这里只建图,不收集节点)
}
stk[++st_top] = x; // 当前节点x入栈
}
// 在虚树上进行DP (根据原代码逻辑)
ll dp_on_vt(int u) {
// min_w[u] 被视为节点u的基础代价或某种必须付出的成本的下限
if (vt_g[u].empty()) { // 如果u是虚树中的叶子节点
return min_w[u]; // 直接返回其基础代价
}
ll children_sum_cost = 0; // 从孩子们dp结果累加的代价
for (int v_node : vt_g[u]) {
children_sum_cost += dp_on_vt(v_node);
if (children_sum_cost >= LINF) children_sum_cost = LINF; // 防止溢出
}
vt_g[u].clear(); // 清理虚树边,为下次查询做准备
// 节点u的总代价是其基础代价与其所有孩子代价和的较小值
return min(min_w[u], children_sum_cost);
}
int main() {
ios::sync_with_stdio(0); // IO优化
cin.tie(0);
cout.tie(0);
// freopen("input.txt", "r", stdin); // 本地测试用文件输入
// freopen("output.txt", "w", stdout); // 本地测试用文件输出
cin >> n;
for (int i = 1; i < n; ++i) {
int u, v;
ll w;
cin >> u >> v >> w;
add_edge(u, v, w);
}
// 初始化 min_w 数组,根据题目语义
// 如果 min_w[u] 是 u 到其父节点的边权 (消耗战模型)
// dfs1_alt(1, 0); min_w[1] = LINF;
// 如果 min_w[u] 是根到u路径上的最小边权 (如原代码 mi 数组的计算方式)
dfs1(1, 0, LINF); // 根的 "父边" 认为是无穷大
// 如果 min_w[u] 是节点u的固有属性,应在读图后或dfs1前单独赋值。
// 假设题目是类似"消耗战",min_w[u] 是割断 (fa[u], u) 这条边的代价
// 那么dfs1应该调整为dfs1_alt版本,并且在main中调用dfs1_alt(1,0), 之后min_w[1]要设为LINF。
// 为了保持与原代码dp逻辑的一致性,这里假设min_w[u]是节点u的固有最小成本,且在dfs1中被某种方式确定了。
// 如果原代码的 mi[u] = min(mi[u_parent], weight(u_parent, u)) 是对的,那么dfs1(1,0,LINF)是对的。
// 且这个 mi[u] 在叶子节点时作为返回值,在非叶子节点时与子树代价比较。
dfs2(1, 1); // 构建树链剖分信息
cin >> q_cnt;
while (q_cnt--) {
int k; // 本次查询的关键节点数量
cin >> k;
for (int i = 1; i <= k; ++i) {
cin >> q_nodes[i];
}
sort(q_nodes + 1, q_nodes + k + 1, cmp_dfn); // 按DFS序排序关键节点
st_top = 0; // 清空栈
// 虚树构建的根节点处理:原代码强制将节点1入栈 s[t=1]=1;
// 如果节点1不一定是关键点,但必须是虚树的一部分(比如作为参照点),则需要加入
// 否则,虚树的根应该是dfn最小的关键点,或所有关键点LCA中深度最浅的
// 标准建法通常不强制1入栈,除非1是关键点。
// 这里我们模拟原代码行为,如果1不在关键点中,也可能需要考虑把它加入处理。
// 然而,如果1不是关键节点,且也不是任何两个关键节点的LCA,它不应该出现在虚树中。
// 所以,更标准的做法是:如果关键点列表 `q_nodes` 不包含1,但DP逻辑需要1作为虚树根,
// 则可能需要手动将1加入`q_nodes`(排序前),并确保`min_w[1]`的设定合理。
// 或者,虚树的根就是stk[1] после построения.
// 原代码的`s[t=1]=1`可能简化了栈的初始状态处理。
// 让我们先不强制1入栈,看看`vt_push`的逻辑。
// `vt_push`中 `st_top == 0` 会处理第一个节点。
// 第一个关键节点 q_nodes[1] (按dfn排序后) 入栈
if (k > 0) {
stk[++st_top] = q_nodes[1]; // 第一个排序后的关键点入栈
}
// 如果题目保证1始终是虚树的一部分或者dp的起点,且1不是关键点时也需要:
// bool one_is_key = false; for(int i=1; i<=k; ++i) if(q_nodes[i]==1) one_is_key=true;
// if (!one_is_key && k > 0) {
// // 如果1不是关键点,但逻辑需要1,则可能需要特殊处理1入栈
// // 或者将1加入q_nodes列表并重新排序。
// // 鉴于原代码 s[t=1]=1,说明1有特殊地位。
// // 如果1总是作为dp起点,那它必须是虚树的一部分。
// // 一个简单的做法:将1也加入到q_nodes中,然后排序去重。
// // (此处为了贴近原代码的dp(1)调用,我们假设1如果不在关键点中,但仍作为dp起点,
// // 它需要被正确地加入虚树结构中,通常是通过成为某个LCA或者就是第一个入栈节点)
// // 原代码s[t=1]=1后,再push(is[i]),这里is[i]是关键点。
// 如果1是必须的根,正确的做法是将1也加入到q_nodes(如果不在的话),再排序。
// 然后第一个q_nodes[1]入栈。
// 原代码的实现方式:
// stk[st_top=1] = 1; // 强制1为栈底(也即虚树最终dfs的起点)
// for (int i = 1; i <= k; ++i) vt_push(q_nodes[i]);
// 这种做法下,1即使不是关键点,也会成为虚树的一个节点。
// 如果k=0,则不应执行下面的循环。
// 我们这里修改为:如果1是关键点,它会被正常处理。如果1不是关键点,但DP从1开始,
// 那么1必须是虚树的一部分。最简单的方法是将1加入关键点列表。
// 为了简化,先按标准虚树构建:只用q_nodes中的点。
// DP的起点将是stk[1] (构建完后栈内唯一的元素,即虚树的根)。
// 如果题目就是钦定DP从原树的1号节点开始,即便1不是关键点,那1必须作为虚树的一个节点。
// 那么可以:
// if (k > 0) {
// vector<int> current_keys;
// current_keys.push_back(1); // 总是包含1
// for(int i=1; i<=k; ++i) current_keys.push_back(q_nodes[i]);
// sort(current_keys.begin(), current_keys.end(), cmp_dfn);
// current_keys.erase(unique(current_keys.begin(), current_keys.end()), current_keys.end());
// stk[++st_top] = current_keys[0];
// for(size_t i = 1; i < current_keys.size(); ++i) vt_push(current_keys[i]);
// } else { // k=0, 但如果仍需dp(1)
// // 答案可能是 min_w[1] 或 0,取决于题意
// }
// 这里我们采用原题的逻辑,dp(1)是固定的,所以1必须在虚树中。
// 先将1入栈,然后处理关键节点。
stk[st_top=1] = 1; // 1号节点作为虚树DFS的起点,强制入栈
for (int i = 1; i <= k; ++i) {
if (q_nodes[i] == 1 && st_top == 1 && stk[st_top] == 1) continue; // 1已在栈底,且当前关键点是1,跳过
vt_push(q_nodes[i]);
}
// 处理栈中剩余的节点,形成虚树最右侧的链
while (st_top > 1) { // 原代码是 t > 0,且用 s[t-1] 和 s[t],所以是 st_top > 1
vt_g[stk[st_top - 1]].push_back(stk[st_top]);
st_top--;
}
if (k == 0 && n > 0) { // 没有关键节点,但题目可能仍要求dp(1)
cout << min_w[1] << "\n"; // 假设此时答案是节点1的固有代价
} else if (n > 0) { // n=0是无效输入
cout << dp_on_vt(1) << "\n"; // 从节点1开始在虚树上DP
} else {
cout << 0 << "\n"; // 或者其他对于空树/无查询的定义
}
// dp_on_vt内部已经clear了vt_g[u],这里不需要额外清理。
// 如果dp_on_vt不清理,则需要在这里清理:
// for(int node_in_stk = 1; node_in_stk <=n; ++node_in_stk){
// if(!vt_g[node_in_stk].empty()) vt_g[node_in_stk].clear();
// }
// 或者更精确地,只清理本次虚树涉及的节点。
// 可以用一个vector<int> vt_nodes_this_query 记录所有虚树节点,然后清理。
// 由于dp_on_vt中已经清理,这里省略。
}
return 0;
}代码关键点与复杂度:
dfs0(预处理): 计算dep,dfn,fa,mc。 复杂度 $O(N \log N)$。mc[u][0](边 $fa[u][0] \to u$ 的权值) 对根节点1,设为INF。lca: 标准倍增LCA, $O(\log N)$。gme(u, vo): 查询 $u$ (祖先) 到 $vo$ (后代) 路径 $(u,vo]$ 上的最小边权。利用mc数组倍增查询。复杂度 $O(\log N)$。bvt(虚树构建): 使用栈构建。addg时计算边权。复杂度 $O(k \log k + k \log N)$($k$为某次查询的关键点数)。vns用于记录虚树节点,方便清理vg。dpf(虚树DP): 在虚树上DFS。- $dp[u]$ 定义为:确保 $u$ 的虚树子树内所有原始关键节点与 $u$ (间接与根1)断开的最小代价,同时考虑 $u$ 是否直接切断与原树父亲的连接。
- 转移逻辑已在代码注释和思路中详述。
- 复杂度 $O(k')$,其中 $k'$ 是虚树中的节点数($k' \le 2k$)。
main函数:- 读入、预处理、处理查询。
- 排序去重:
kns必须排序去重。 isk清理: 使用q_kns_orig存储原始输入关键点,用于准确清理isk标记。
- 总复杂度: $O(N \log N + \sum (k \log k + k \log N))$。
这个DP示例 ("消耗战") 的核心在于正确定义DP状态,并巧妙利用虚树边权(即原树路径最小边权 gme)和节点自身与原树父节点的连接代价 (mc[u][0])进行决策。
6. 实现细节、常见陷阱与调试技巧
虚树的实现虽然不算特别复杂,但有不少细节容易出错,导致WA或者TLE。
DFS序与LCA是基石:
- 确保DFS序 (
dfn)、深度 (dep)、祖先信息 (fa) 计算无误。 - LCA算法(如倍增)必须正确。一个常见的错误是LCA对于根节点或不存在的父节点(如0号节点)处理不当。
dep[0]应为0或-1,fa[root][0]应为0。
- 确保DFS序 (
关键节点处理 (
kns):- 排序: 关键节点列表
kns必须在构建虚树前按dfn严格升序排序。 - 去重: 排序后必须对
kns进行去重 (unique+erase)。重复的关键节点会扰乱栈式构建逻辑。 - 空集/单点: 如果
kns为空,直接返回。如果kns只有一个节点,虚树就只包含该节点。代码应能优雅处理。
- 排序: 关键节点列表
栈式构建算法的细微之处 (
stk,top):- 栈顶与LCA的关系判断 (
dep[stk[top-1]] >= dep[l]) 要准确。注意栈中至少要有2个元素才能比较stk[top-1]。通常栈底放一个虚拟节点(如0号节点,dep[0]极小)或显式检查top > 1。我的代码中fa[1][0]=0, dep[0]=0配合top > 1可以工作。 - LCA节点
l的入栈时机:当l != stk[top]时,意味着l是新的“拐点”,需要将原栈顶作为l的孩子连接,然后l替换原栈顶成为新的stk[top]。 - 所有加入虚树的节点(原始关键点和LCA们)都应记录在
vns中,用于后续清理虚树邻接表vg。
- 栈顶与LCA的关系判断 (
虚树边的权值:
- 边 $(u,v)$ ( $u$ 是 $v$ 在虚树中的父节点) 的权值通常是原树中 $u \leadsto v$ 路径的信息。例如,路径长度 ($dep\_w[v] - dep\_w[u]$,如果预处理了带权深度
dep_w),路径最小/最大边权 (如 "消耗战" 中的gme(u,v))。这个计算必须准确。
- 边 $(u,v)$ ( $u$ 是 $v$ 在虚树中的父节点) 的权值通常是原树中 $u \leadsto v$ 路径的信息。例如,路径长度 ($dep\_w[v] - dep\_w[u]$,如果预处理了带权深度
状态清理:
vg(虚树邻接表): 每次查询构建新的虚树前,必须清空上次查询构建的虚树边。通过遍历vns中记录的上次虚树节点,清空其vg[node]。然后清空vns。isk(关键节点标记): 每次查询处理完毕后,将本次查询涉及的原始关键节点的isk标记复位为false。使用一个临时列表(如q_kns_orig)保存原始输入关键点是好方法。- DP数组 (
dp): 如果DP数组是全局的,且DP值依赖于上次状态(不太常见于虚树DP,通常是自底向上重新算),则需初始化。大多数虚树DP是无后效性的,每次在新的虚树上算。
根节点1的特殊处理 (如 "消耗战"):
- 问题常涉及与特定节点(如根节点1)的关系。要仔细分析该特定节点是否应强制加入关键节点集,以及它在DP中的角色。
- "消耗战"中,
mc[1][0](根节点与其父节点的边权)应为INF,因为它没有父边。
数值范围与INF:
- 路径权值和、DP值可能很大,注意使用
long long(ll)。 - INF的取值要足够大,以避免在加法或比较中出错,但又不能大到溢出
ll。如代码中4e18。
- 路径权值和、DP值可能很大,注意使用
调试技巧:
- 打印虚树: 对于小数据,手动模拟虚树构建,并打印程序构建的虚树结构(节点、父子关系、边权),进行比对。例如:
for (int u_ : vns) { if (!vg[u_].empty()) { cout << u_ << ": "; for(auto edge : vg[u_]) cout << "(" << edge.first << "," << edge.second << ") "; cout << endl; } } - 检查LCA和
gme: 单独测试这些辅助函数。 - 单步跟踪DP: 在虚树DFS DP的过程中,打印关键节点的 $dp$ 值和中间计算。
- 从简单情况入手: 先用 $k=1,2,3$ 的简单例子测试。
- 打印虚树: 对于小数据,手动模拟虚树构建,并打印程序构建的虚树结构(节点、父子关系、边权),进行比对。例如:
遵循这些细节,能大大提高虚树代码的正确率和鲁棒性。
7. 虚树与其他算法
虚树作为一种优化技巧,常常与其他树上算法一起出现在我们的工具箱中。
虚树 vs. 直接在原树上操作:
- 当查询涉及的节点数 $k \ll N$,且操作主要与这些关键节点及其路径相关时,虚树通过降低问题规模(从 $N$ 到 $k$)来优化。若 $k \approx N$,虚树开销可能不划算。
虚树 vs. 点分治/边分治:
- 点分治等通常用于离线处理所有(或满足特定条件的)点对/路径问题,复杂度多为 $O(N \log N)$ 或 $O(N \log^2 N)$。虚树则针对每次查询动态构建,处理特定少数点。两者解决的问题和方法不同。
虚树 vs. DSU on Tree (启发式合并):
- DSU on Tree 优化的是对 所有子树 的某种信息维护(如子树颜色种类),常用于离线。虚树关注 特定稀疏点集 的结构。
它们是不同场景下的工具。虚树的独特之处在于其动态性和对稀疏关键点集的高效处理。
8. 更多练习与进阶思考
掌握虚树的最好方法是通过练习。可以关注以下类型的问题:
- 最小连通子图/Steiner树变种: 如我们第一个例子,求包含所有关键点的最小权值连通子图的总边权和。
- 路径查询与统计: 询问 $k$ 个关键点之间两两路径的某些性质总和/最值。
- 树上DP优化: 许多树形DP问题,如果每次只涉及少数几个节点状态的改变或查询,可以考虑虚树。
- 特定限制下的连通性问题。
进阶思考:
- $\sum k$ 很大,但单次 $k$ 较小: 此时 $O(N \log N)$ 的预处理是值得的。总复杂度可能形如 $O(N \log N + (\sum k) \log N)$。
- $k$ 很大 ($k \approx N$): 虚树优势不明显。
- 在线构建/动态维护: 标准虚树是为静态查询设计的。若关键点集动态变化,维护虚树会更复杂。
9. 写在最后
虚树,其核心在于提炼与聚焦。它为我们动态构建一个只包含核心信息的小规模等价结构,不仅大幅降低了计算复杂度,也使得许多在原树上难以进行的DP等操作成为可能。
掌握虚树,你需要:
- 扎实的图论基础:DFS、LCA。
- 清晰的算法思路:理解栈式构建的原理。
- 细致的实现能力:注意各种边界条件和状态清理。
- 灵活的应用技巧:能够将问题转化为虚树上的DP或其他操作。
算法的魅力在于化繁为简,虚树正是这种魅力的完美体现。
