T6 虚树 题目大意 现在有一颗树，树上有一些节点，我们可以待在某个节点一段时间tit_iti ，最终赚得一定的钱数pip_ipi ，同时在一条边上移动会花费1个单位时间，求在一个定时间 wiw_iwi 最多会赚多少钱。 题解思路 问题一 当树的节点比较小的时候，我们可以通过什么方法来解决这个问题。 很明显我们可以通过一个背包来解决这个问题。 在树上我们根据花费多少模拟背包操作，之后将背包中的信息整合，对父节点进行背包操作。 但是节点数似乎很多，直接背包容易tle， 优化 现在树上一共有 nnn 个点,在这 nnn 个节点上进行背包 dpdpdp ,维护会发生超时，那么我们可以怎么做呢？首先，我们发现可以赚钱的节点很少 mmm，我们沿着这些节点往上走，我们发现，最多会有 mmm 次相遇，也就意味着，不同的背包最多合并 mmm 次。那么我们是否只要在这些需要合并的点上进行记录就可以了？ 我们叫这些合并的点叫做虚点。 这些虚点我们可以通过 lcalcalca 求得。 关于求 lcalcalca 可以实现树剖或者倍增预处理并实现，之后在新树上进行dp 复杂度分析 O(n+mlog⁡n+m×W2n + m\log n + m\times W^2n+mlogn+m×W2) 参考代码 > 本题可以在分组背包中进行一定的剪枝通过，如过深的节点忽略，将原理数组背包转换为离散化背包，可以大量优化计算的过程，