树形计数背包-HDU|树形计数背包-HDU 6540 Neko and tree
传送门:http://acm.hdu.edu.cn/showproblem.php?pid=6540
题目大意：给一棵含有n个点的树，里面含有m个关键点。问你有多少种选关键点的方案使得选出的点中两两之间的距离 <= dist. (1 <= n , m , dist <= 5000)
题目思路:
重点考虑转移的时候如何表征出两点之间的距离:
【树形计数背包-HDU|树形计数背包-HDU 6540 Neko and tree】对于一颗子树，其实我们只需要知道它所选的最深关键点的深度，就可以进行dp的转移了。所以将深度放入状态中就可以直接判断子树之间是否能够转移了.所以自然我们想出以下转移方程:
之后，对于一个新增的子树,它可以向主树转移一种深度。接下来就是套树形背包的模板
1.我们设两层循环，外层循环为主树当前深度k,内层循环为子树的深度g。
2.g,k之间的组合向 max(g,k)转移.根据计数原理,新增的贡献就是方案数的乘积.
3.加上一个限制条件为:两者的距离 k + g - 2*dep[u] <= dist.(两个点的LCA就是当前的根).
4.所以转移方程为:
注意：temp为滚动数组.是上个阶段的dp[u]的值.
深度的组合是n^2的，那么整个树的复杂度为:O(n^3),所以接下来再考虑如何优化:
我们其实只需要关注那些关键点的深度。所以我们可以在dfs的过程中只保存那些关键点的深度。再一步步传给父亲节点。那么循环的时候就不是从 0 ~ n循环深度了。而是循环 树所拥有的关键点的深度(离散化的思想)。这样就等价于循环关键点的个数，而不是深度.
那么这样就保证每一对关键点只会在他们之间的LCA处计算一次答案.
复杂度为：
文章图片
关键代码 AC代码：https://paste.ubuntu.com/p/4s2NDzGPvC/
推荐阅读
- 数据库设计小知识
- 十二种排序（冒泡、插入、归并、快速排序等包含希尔和计数排序）
- #|算法设计与分析（Java实现）—— 动态规划 （0-1 背包问题）
- #新中式宠妈艺术#我的双肩背包
- Java数据结构和算法-动态规划算法解决背包问题
- 【golang】leetcode初级-Fizz|【golang】leetcode初级-Fizz Buzz&计数质数
- [Golang]力扣Leetcode—初级算法—数学—计数质数（厄拉多塞筛法）
- 冬季实战营 动手实战-云上多产品学习，使用ECS服务器部署MySQL数据库 领鼠标 云小宝 背包 无影
- 冬季实战营动手实战-上云必备环境准备，动手实操快速搭建LAMP环境 领鼠标 云小宝 背包 无影
- java返回树形结构数据工具类