2024/05/29(#45)：就等待吧 春归时希望鸣响

—— COP《雪来临时》

今天做一点杂题。

55 CF843D Dynamic Shortest Path

你看，因为值域是有限的，因此直接每次 BFS 更新一下即可。

56 ARC125F Tree Degree Subset Sum

首先可以将所有的 $d$ 都减去 $1$。然后我们能证明，对于一个 $y$，合法的 $x$ 是一个连续段。因为叶子在树中至少有 $\frac n 2$ 个，我们可以根据选择叶子的数量来调整。

现在要对于每个 $y$，求出最少、最多用多少个物品凑出。由于 $\sum d$ 的保证，直接二进制拆分优化多重背包。

57 AGC028B Removing Blocks

考虑一个删除的时间序列，如何计算其贡献？建立小根笛卡尔树，代价为 $\sum dep_i\times a_i$。

如果 $x$ 是 $i$ 的祖先，可以考虑：

• $x<i$ 时，$x,x+1,\cdots,i-1$ 应该比 $i$ 后删除，概率是 $\frac 1 {i-x+1}$；
• $x>i$ 时，为 $\frac 1 {x-i+1}$。

不难计算出答案。

VP CEOI2019 Day1。

58 B. Dynamic Diameter

考虑使用线段树维护答案，每次可以将集合的两半合并成当前集合的答案（只需要考虑 $4$ 个可能的直径），链上距离使用树状数组维护即可。

59 C. Cubeword

发现只有字符串的头尾会影响答案，用四个四个点的平面来限制答案，平面的答案可以直接 $O(V^4)$ 枚举。

* 60 A. Building Skyscrapers

别急。