虚树
算法简介
一种用于加速树上 $\text{dp}$ 算法，时间复杂度 $O(k\log k)$，其中 $k$ 为树上的关键节点数。
算法思想
树上关键点数量较少时很多节点不需要进行 $\text{dp}$，考虑重建一棵树，只保留必要的节点。
发现所有关键节点的 $\text{LCA}$ 必须保留，但如果暴力枚举每对关键节点的 $\text{LCA}$ 显然会超时。
事实上只需要将关键点序列$\text{dfs}$ 序排序，然后枚举序列中相邻节点的 $\text{LCA}$。
可以证明该方法枚举得到的 $\text{LCA}$ 不会有遗漏。假设 $p=\text{LCA}(u,v)$，且 $u,v$ 不是序列中相邻的节点。
于是必有 $u,v$ 属于 $p$ 的不同子树，考虑取序列中与 $v$ 相邻且 $\text{dfs}$ 序小于 $v$ 的节点，记为 $v_2$。
首先易知 $v_2$ 也位于 $p$ 的子树。于是如果 $v_2$ 与 $v$ 不在同一棵子树，那么 $\text{LCA}(v_2,v)=p$。
否则把 $v$ 换成 $v_2$，继续重复上述操作，最后总有 $v_{k-1},v_k$ 不在同一棵子树(最差的情况是 $v_k=u$)，证毕。
然后为了保证最终选取的点一定会构成树而不是森林，考虑强制将根节点加入虚树或者构造一个虚根。
接下来是建边过程，考虑用单调栈维护从根节点出发的一条树链。
每新加入一个节点时，先计算新节点与栈顶节点(事实上栈顶节点一定是上一次加入的节点，即与新元素相邻的节点)的 $\text{LCA}$，记为 $p$。
如果 $p$ 恰好为栈顶节点，则直接将新节点入栈。
否则，将栈顶节点弹出直到栈顶栈顶节点的下一个节点的 $\text{dfs}$ 序不大于 $p$ 的$\text{dfs}$ 序。
注意到每当栈顶节点被弹出时他在虚树中的位置已经确定，可以直接将他与下一个栈顶节点连一条边。
然后如果 $p$ 恰为栈顶栈顶节点的下一个节点，则将栈顶节点弹出并将他与下一个栈顶节点连一条边。
否则将栈顶节点弹出并将他与 $p$ 连一条边，再将 $p$ 加入栈。这一系列操作结束后再将新节点入栈。
所有关键节点都访问结束后将栈的剩余元素出栈并连边。
算法模板
题意
给定一棵以 $1$ 为根的边权树，设切断一条边的费用为这条边的边权。接下来 $q$ 次询问。
每次询问给定 $k_i$ 个关键节点(保证不含根节点)，要求切断若干条边使得所有关键节点节点与根节点不连通，问该操作的最小费用为多少。
题解
首先考虑 $\text{dp}$ 过程，有状态转移方程
\begin{equation}v \text{ 是 }u \text{的儿子节点且} v \text{ 不是关键节点，}\text{dp}(u)\gets\min(\text{dp}(v),w(u,v))\end{equation} \begin{equation}v \text{ 是 }u \text{的儿子节点且} v \text{ 是关键节点，}\text{dp}(u)\gets w(u,v)\end{equation}
接下来建立虚树，并令 $w(u,v)$ 为 $u\to v$ 路径上的最短边。事实上令 $w(u,v)$ 为 $1\to v$ 的最短边不影响最终答案。
最后暴力 $\text{dp}$ 即可，时间复杂度 $O(\sum_{i=1}^q k_i\log k_i)$。注意每次新建树时不能暴力清零 $\text{head}$ 数组，需要在建树过程中清零。
算法练习
习题一
题意
给定一棵 $n$ 个节点的无根树，$q$ 次询问。
每次询问给定 $k_i$ 个关键点。树上每个节点属于离它最近的关键点(如果有多个距离最近点则选择编号最小的)。
每次询问要求输出 $k_i$ 个数，代表属于每个给定关键点的节点数。
题解
强制以 $1$ 为根，转化为有根树。先考虑暴力 $\text{dp}$ 的做法。
在原树上，先一次 $\text{dfs}$ 找到每个节点子树方向上距离最小的关键节点，同时记录最小节点的距离和编号。
然后再一次 $\text{dfs}$ 更新每个节点祖先方向的距离最小的关键节点，即可得到答案。
暴力 $\text{dp}$ 对每次询问时间复杂度 $O(n)$。接下来考虑虚树优化 $\text{dp}$。
对虚树上的点，直接使用上述暴力 $\text{dp}$ 即可。关键在于如何计算不在虚树上的点对关键节点答案的贡献。
对于不在虚树上的点，要么位于虚树上的某个节点在原树上的儿子节点的子树中且该子树中没有关键节点，记为第一类点。
要么位于虚树上的某两个节点在原树上的路径上的某个节点的非路径方向的子树中，记为第二类点。
先考虑第一类点的贡献，发现第一类点可以全部计入它的第一个属于虚树的祖先节点的贡献中。
对于第二类点的贡献。取虚树上两相邻点在原树上的路径，可以根据到哪个关键节点近将路径分成两段。
每段路径上的节点及其非路径方向的子树对距离该节点近的关键节点做贡献。
具体实现过程与上述讨论存在少量差异，详细见代码。
