#树形DP
2 entries01
CF1988D The Omnipotent Monster Killer
CF1988D The Omnipotent Monster Killer Problem怪物们在一棵有 个顶点的树上，编号为 的怪物位于编号为 的顶点上，攻击力为 。你需要与怪物战斗 个回合。在每个回合中，会依次发生以下两步： 所有活着的怪物攻击你。你的生命值会按照所有活体怪物攻击点的总和减少。 您选择一些（可以选全部，也可以不选）怪物并杀死它们。被杀死的怪物将不会再进行攻击。 限制条件：在一个回合内不能杀死相邻的两只怪物。 如果您以最佳选择方式攻击的怪物，那么在所有回合后，您的健康值减少的最小值是多少？
02
CF1928G Vlad and Trouble at MIT
Vlad and Trouble at MIT ProblemMIT的学生宿舍可以用一棵有 个顶点的树来表示，每个顶点代表一个房间，每个房间一个学生。 今晚，有三种类型的学生： 想参加派对和玩音乐的学生(标记为 ) 想睡觉和享受安静的学生(标记为 ) 无所谓的学生(标记为 )。 开始时所有的边缘都是薄墙，允许音乐通过，因此当参加派对的学生放音乐时，每个房间都能听到。但是，我们可以在任何边缘放置一些厚墙—厚墙不允许音乐通过。 学校希望安装一些厚墙，这样每个参加派对的学生都可以播放音乐，而睡觉的学生却听不到。 最少需要多少厚墙？