CodeForces #196(Div. 2) 337D Book of Evil （树形dp）

本文出自 http://blog.csdn.net/shuangde800

题目：点击打开链接

题意

给一棵n个结点的树，任意两个节点的距离是指连接两点的最短的边数
在树上的某个结点有一个“恶魔之书”，这本书会让距离它d以内的节点都受到影响
已知有m个节点收到了影响，问最多有几个结点可能放着“恶魔之书”？

思路

要判断某个点是不是放着书，就要判断这个点的周围d距离以内是否包含所有受影响的m节点
而如果某个节点距离最远的那个受影响节点的距离是L,如果L <= d，那么说明所有受影响的m节点都在d以内，就可判断这个点可能放着书

那么，我们只要能够求出每个节点距离最远的影响节点是多少，就可以O(n)的时间求出答案了。

所以可以用树形dp求解：

f(u, 0): 表示u为顶点的子树中，距u最远的“受影响节点”的距离
f(u, 1): 表示整个树删去u为顶点的子树,但是依旧保留u点为顶点，这个树中距离u最远的“受影响节点”的距离

所有的f(u, 0)可以一次dfs搞定, O(n)
f(u, 1)可以由顶节点一直推下去

f(v, 1) = max{f[brother1][0], f[brother2][0]..., f[brother3][0], f[father][1] | brother是v的兄弟节点，fa是v的父节点} + 1

这一步可以再一次dfs解决，同样是O(n)

代码

<script src="https://code.csdn.net/snippets/614.js" type="text/javascript"></script>