日记 - 伊埃斯的博客站

今天实在是智商不在线。

暗号↗

其实正常。

设 $dp_{i,0/1,j,k}$ 表示 $i$ 染色成 $0/1$ ， $i$ 到根的路径上还要 $j$ 次两端都为 $0$ 的边， $k$ 条两端都为 $1$ 的边， $i$ 子树内的最大士气值。

初始化有 $dp_{i,0,j,k} = a_i(j + 1),dp_{i,1,j,k} = a_i(k + 1)$ 。

考虑如何转移。我们考虑 $u \to v$ 的一条边应当是染成什么颜色。

染成 $0$ ： $dp_{u,0,j,k} \gets \max(dp_{v,0,j + 1,k},dp_{v,1,j,k})$ 。
染成 $1$ ： $dp_{u,1,j,k} \gets \max(dp_{v,0,j,k},dp_{v,1,j,k + 1})$ 。

最后的答案就是 $\max(dp_{1,0,0,0},dp_{1,1,0,0})$ 。

聪聪与可可↗

以后还是该多做一点这种图上 dp。

我们发现这个猫往哪里走十分的恶心。于是我们预处理一个 $nxt_{i,j}$ 表示猫在 $i$ ，老鼠在 $j$ 的时候，猫往哪里走。可以用 dijkstra $O(n^2 \log n)$ 预处理。

然后考虑 dp。设 $dp_{i,j}$ 表示猫在 $i$ ，老鼠在 $j$ 的时候的期望步数。边界就是当 $i$ 能在两步之内走到 $j$ 时 $dp_{i,j} = 0$ 。

考虑如何转移。我们发现在一步走不到老鼠所在地时猫一定会走两步，设 $se$ 表示猫走两步的地方。所以有 $dp_{i,j} = \sum_{k}\frac{dp_{se,k}}{deg_j + 1}$ 。最后还要把它加上 $\frac{dp_{se,j}}{deg_j + 1}$ 表示老鼠不动的情况。