2023/10/6 发现找不到题做了，决定学习新算法。经过在一些题单中的翻找，决定学习虚树。
Part1. 引入
以一道例题来引入虚树吧。
[HEOI2014] 大工程
给定一棵有 \(n\) 个点的树，边权均为 \(1\)。
现在有 \(q\) 次询问。每次询问取 \(k\) 个点出来建立完全图。定义连接两个点的代价为在树上 \(a, b\) 的最短路径的长度。求：
- 建立完全图的代价和。
- 代价最小的边的代价。
- 代价最大的边的代价。
对于 \(100\%\) 的数据，\(1\le n\le 10^6,1\le q\le 5\times 10^4,\sum k\le 2\times n\)。
以第一问为例。考虑树形 dp。设 \(sz_i\) 为以 \(i\) 为根的子树中被标记的点的个数，\(g_i\) 为以 \(i\) 为根的子树中所有被标记的节点到根节点的距离和。
将子树合并，考虑每条边的贡献即可，两个子树合并时的贡献和状态转移方程为：
\[ans \leftarrow ans + (g_u + sz_u) \times sz_v + g_v \times sz_u \]\[g_u = g_u + g_v + sz_v \]\[sz_u = sz_v + sz_u \]但是对于每次询问都要遍历整棵树，单词询问是 \(O(n)\) 的，不可接受。
那么有什么办法解决呢？我们发现有 \(\sum k\le 2\times n\)，那么是否可以将每次询问的时间复杂度压缩到仅与 \(k\) 有关呢？
显然是有的，虚树可以方便的解决「多次询问，每次询问给定一个特殊点集，求在这一点集上某一问题的答案」这样的问题。
Part2. 虚树的概念
我们发现在上面的树形 dp 中，有很多点其实没什么作用。具体而言，我们可以只保留点集中的点和点集中的点的 lca，而其它的点和边可以忽视，为新树分配边权为原树两点的距离。
借一下 OI-Wiki 的图捏。
如图所示，点集为 \({4, 6, 7}\)。我们不关心 \(2\) 号节点和 \(5\) 号节点，因为它们与点集无关，然后令 \((1, 4)\) 边的边权为 \(2\)。
而另一边，为了保留 \(6, 7\) 节点的信息，我们还需要保存它们的 lca 节点 \(3\) 的信息，以及这些点的共同 lca 节点 \(1\) 的信息。
虚树大概就是这个样子，然后我们发现在虚树上压缩边权进行如上树形 DP，还能得到正确答案，因为 保存着信息的重要节点 都被保留了，而虚树的点数被压缩到了 \(O(k)\) 级别的。
剩下的明天补了。
标签：sz,le,询问,笔记,节点,学习,times,虚树 From： https://www.cnblogs.com/AzusidNya/p/17745184.html