Java教程

虚树学习笔记（待填坑）

本文主要是介绍虚树学习笔记（待填坑），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

虚树学习笔记

问题的引入

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

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

虚树的概念

待填坑。

这篇关于虚树学习笔记（待填坑）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航