虚树学习笔记

问题的引入

在树上 DP 的问题中，可能有多次询问，每次询问包括的总点数规模较小（例如 \(10^5\)）。我们记节点数为 \(n\)，询问次数为 \(m\)，询问中总点数为 \(\sum k\)，那么直接在整棵树上暴力 DP 的复杂度为 \(\mathcal{O}(nm)\)，不可接受。能不能发明一种 DP 的方法，不需要访问所有节点，只访问 \(\mathcal{O}(k)\) 个节点呢？这样时间复杂度就优化成了 \(\mathcal{O}(m+\sum k)\)。

这种方法当然是有的，就是虚树。

虚树的概念

待填坑。