引入

给你 $n$ 个点的一棵树，每条边有边权。从中选取一些关键结点，你需要切断一些边，使得没有任何关键节点与 $1$ 号点联通，最小化切断边的总边权。

$O(n)$ 做法是显然的。考虑树形 DP。我们设 $f_u$ 为以 $u$ 为根的子树内（不包括 $u$）切断一些边使得没有任何关键结点与 $u$ 联通的边权和最小值。容易得到转移方程。

设 $v$ 是 $u$ 的一个儿子，$w$ 为 $u$ 到 $v$ 的边权。

若 $v$ 是关键结点，$f_u=f_u+w$，否则 $f_u=f_u+\min\{f_v,w\}$。

现在把问题升级一下。$q$ 组询问，每次给定一些关键结点，求答案。所有询问中关键结点个数的和与 $n$ 同阶。

我们把上面的算法跑 $q$ 次，就得到了一个 $O(nq)$ 的算法，这是远远不够的。

但是所有询问中关键结点个数的和与 $n$ 同阶，在关键点数量比较少的时候，总会有一些其他结点是无用的。我们有没有一种方法把这棵树的信息浓缩呢？答案是有的。

虚树

不要被名字吓到。所谓虚树，不过是一个重构树，在这个重构树上进行 DP 和在原树上 DP 是等价的。这个重构树上当然结点数量越少越好。

那么这个重构树上最少需要有哪些结点呢？先抛出结论：任意两个关键结点的 LCA 都是必须的。

为什么呢？我们在树上 DP 的过程其实是把一个个子树的信息合并。为了不错过任何子树合并的结点，自然是任意两个关键结点的 LCA。

当然，我们 $O(n^2\log n)$ 枚举任意两个关键结点的 LCA 肯定是不行的。所以我们需要一个快速构建虚树的算法。

我们先把原树的 dfn 求出来。考虑维护一个结点 dfn 值单调递增的单调栈。单调栈中每一个结点都是虚树上的点。

初始时，单调栈中有根节点 $1$，dfn 为 $1$。我们把关键结点按照 dfn 升序排序，依次考虑把每一个结点加入到虚树中。

假设当前考虑点 $u$，栈顶结点为 $t$，栈顶下面的一个结点是 $r$，我们求出 $p=\operatorname{LCA}(u,t)$。则一定有 $dfn_u>dfn_p$。

若 $t=p$，则我们直接把 $u$ 加入到栈中（也就是虚树中）。
否则，我们做如下处理：
- 若 $dfn_r>dfn_p$，则弹出栈顶直到 $dfn_r\leq dfn_p$。
- 此时，若 $r=p$，直接把 $t$ 弹掉然后加入 $u$ 即可。
- 否则，把 $t$ 弹出后，把 $p$ 和 $u$ 加入栈即可。

算法结束后，加入过栈的结点就是虚树中的结点。

下面我们来讨论这个算法的正确性。

当 $t=p$ 时，因为 dfn 递增，所以 $p$ 到 $u$ 的路径上没有其他关键结点，直接加入 $u$ 是正确的。

否则，我们要讨论两种情况：$p$ 加入过栈中，$p$ 没加入过栈中。

弹栈的过程，是为了寻找栈中相邻的两个点 $t$ 和 $r$，这两个点把 $p$ 夹在中间。

如果 $r=p$，也就是说 $p$ 加入过栈中，把 $r$ 弹掉后就变成了 $t=p$ 的情况。

如果，$r\neq p$，说明 $p$ 没加入过栈中，则我们需要把 $p$ 加入到栈中，也就是加入到 $r$ 和 $t$ 之间，然后把 $r$ 删除，就变成了 $t=p$ 的情况。

综上所述，这个算法是正确的。

分析时间复杂度。遍历每个点 $O(n)$，求 LCA 要 $O(\log n)$，单调栈均摊 $O(1)$，所以这个算法的时间复杂度是 $O(n\log n)$。

分析结点个数。通过算法，我们可以直观地发现，每两个 dfn 相邻的关键点最多可能会让一个 LCA 加入到虚树中，所以结点个数是 $O(n)$ 的。

我们在弹栈的时候，把次栈顶向栈顶连边即可得到虚树的图。

回到原来的问题。我们建立好虚树，虚树中每条边的边权是原来树上两个点之间所有边的边权最小值，这是显然的，因为如果想要断边，只需要断最小的那条边就行。这可以轻松地用倍增维护。

每次询问在虚树上跑 DP，就 $O(n)$ 解决了这个问题。