Codeforces 70E Information Reform 题解

Codeforces 70E Information Reform 题解

这道题给人的直觉是树形dp，但采用传统的 dp 状态设计是不行的，难以处理点的覆盖与建立基站的关系。

改变思路，考虑到每个点都要依赖恰好一个基站，干脆把当前点依赖的基站记进状态

设 (dp_{i,j}) 为子树 (i) 都被覆盖，点 (i) 依赖的是 (j) 时的最小代价

首先，假设 (j) 基站是新建的，再加上距离的代价，那么初始代价为 (k + d_{dis_{i,j}})。从 (i) 的每一个子结点 (son) 转移。我们想到有两种转移方式：

1.(son) 以前就依赖自己的基站，那么其实不用新建了，要减一个 (k)，代价为 (dp_{son,j} - k)。

2.让 (son) 依赖对于它最优的基站，代价为 (dp_{son,opt_{son}}) （(opt[i]) 表示使子树 (i) 被覆盖费用最小时选的基站，顺便维护一下即可）。

这就是最直观的转移方式，它确实是对的，但有一个问题：如果多个子结点的 (opt) 等于 (j)，那不会把代价算少了吗？

转移 (1) 里减掉的 (k) ，第一次是对 (i) 减的，后面几次都是对上一个 (opt = j) 的结点减的，所以正好不重不漏。

至于输出路径，枚举每个子结点，如果转移 1 费用小，就走转移 1，否则走转移 2。也没有那么恐怖。