树形dp
作者：
asukaqaqzz
,
2022-03-10 22:21:27
,
所有人可见
,
阅读 269
基础树上问题
树形dp
| 题目 |
题意 |
关键字/分析 |
题解 |
| 285.没有上司的舞会 |
每个人都有一个快乐值,已知直接上司来了,自己不来,求最大快乐值之和 |
最大独立集问题,状态机 |
题解 |
| 323.战略游戏 |
有n条道路,每条道路都要有人看守,在一个点放置一个士兵可以看到周围所有边,求最小放置数目 |
最小权覆盖集,边权覆盖 |
题解 |
| 1077.皇宫看守 |
有n个点,每个点放上士兵可以看到与他相邻的点,求最少安防士兵数 |
点权覆盖,最小权覆盖集 |
题解 |
树上背包
| 题目 |
题意 |
关键字/分析 |
题解 |
| 10.有依赖的背包问题 |
树上背包模板题(???) |
模板题 |
题解 |
| 1074.二叉苹果树 |
有n个结点,n-1条树枝,在树上选择m个树枝,求出最多能留住苹果数 |
阅读理解,无向图,边权 |
题解 |
| P2014.选课 |
有n门课,要从其中选出m个课出来,每个课有他的前驱先修课,求最多学分数 |
树上背包,多棵树,点权 |
题解 |
| P1273 有线电视网 |
有n-m个转播站,m个用户,他们呈现一棵树,用户一定是叶子节点,用户有点权(+),转播线路有边权(-),求不亏本的情况下,最多用户数 |
点权,边权,转换 |
题解 |
