- 非常好的一道树形 dp 题
- 起初我看错题了 QwQ ，以为第一个选的必须为根
- 首先我们发现假设我们选的第一个灯泡为 \(u\) ，他的行走过程是：\(u \rightarrow u\) 子树 \(\rightarrow fa_u \rightarrow u\) 兄弟子树 \(\rightarrow fa_{fa_u} \rightarrow \dots\)
- 因此我们考虑设 \(g_{u,i}\) 表示从 \(u\) 点开始，便利完 \(u\) 子树后走到第 \(i\) 层需要的最小花费。
- 当 \(u\) 没有儿子时，显然 \(g_{u,i} = (dis_{fa_{u,i}} - dis_u) \times a_{fa_{u,i}}\) ，其中 \(dis_{u}\) 表示 \(u \rightarrow 1\) 的路径和，\(fa_{u,i}\) 表示 \(u\) 一直向上跳直到到达第 \(i\) 层的节点编号
- 当 \(u\) 有一个儿子时，容易得到 \(g_{u,i} = g_{ls, i} + w_{ls} \times a_{ls}\)
- 当 \(u\) 有两个儿子时就比较难办了，因为我们不知道从一个子树跳跃到另一个子树的代价。为此，我们可以记 \(f_{u,i}\) 表示从 \(u\) 访问其子树并走到第 \(j\) 层的兄弟节点的最小花费，则可以得到 \(g_{u,i} = \min(a_{ls} \times w_{ls} + f_{ls,dep_{rs}} + g_{rs,j}, a_{rs} \times w_{rs} + f_{rs,dep{ls}} + g_{ls,j})\)
- 然后考虑 \(f_{u,i}\) 的转移，同理
- 最终复杂度 \(O(n \log n)\)
P4253 [SCOI2015] 小凸玩密室
发布时间 2023-10-23 18:02:54作者: FOX_konata