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。也没有那么恐怖。