16
2019
08

信息学一本通-1579:皇宫看守 树形dp

一棵树有 N 个节点,现在需要将所有节点都看守住,如果我们选择了节点 i,那么节点 i 本身,节点 i 的父亲和儿子都会被看守住,每个节点有一个选择代价,求完成任务所需要的最小的代价。显然这是一道树形DP。根据每个节点其实有只有三个状态:①被自己看守;②被儿子看守;③被父亲看守。我们设这三种状态分别为 F1,F2,F3。当然最终作为答案的根节点没有父亲就从 F1,F2 里面选小的。接下来我们要考虑怎么转移。首先看 F1,我们规定 F1[ i ] 代表的是 i 节点被自己看守且以 i 为根的子树都