题解 P3267 【[JLOI2016/SHOI2016]侦察守卫】

· · 个人记录

这里提供一种与题解中状态不同的树形dp

首先设fu[x][i]表示节点x被与它距离为i的节点所覆盖，并且这条路径经过x的父亲节点。

再设fd[x][i]表示节点x被与它距离为i的节点所覆盖，并且这条路径不经过x的父亲节点。

我们先考虑fu的状态转移。假设x的其中一个节点v被不经过x的路径长度为k的节点所覆盖，则应该满足如下条件：

i+1>=k

且

k+1>=i

因为如果k+1<i，则