本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-09-02 21:03:46

题单

T1

考虑贪心的去做，从子树向上合并，每次肯定把子树内耗时最长的先拨打，排序向上合并即可

设 $f_{u,i,0/1}$ 表示以 $u$ 为根的子树，走过 $i$ 个点，最后是否会回到 $u$，所需要的最小步数。

树形背包，考虑如何转移，首先 $f_{u,i,0}$ 如果最后走到 $v$ 的子树内，则

$f_{u,i,0} = \min f_{u,i - j,1} + f_{v,j,0} + w$。

如果从 $v$ 子树内绕一圈，最终停留在其他子树，则

$f_{u,i,0} = \min f_{u,i - j,0} + f_{v,j,1} + 2 \times w$。

转移 $f_{u,i,1}$，有

$f_{u,i,1} = \min f_{u,i - j,1} + f_{v,j,1} + 2 \times w$。

最终答案，二分 $i$，判断 $f_{1,i,0/1}$ 是否 $\le x$ 即可。

感觉有点难写，还不会。

消防局的设立加强版，考虑设 $f_{u,i}$ 表示从 $u$ 点向上额外覆盖完 $i$ 层需要选的最少点的数量，考虑如何转移。

记 $sum_{u,i}$ 表示 $\sum_{v \in son_u} f_{v,i}$，转移分三种。

当 $i < 0$ 时，$u$ 向下覆盖 $i$ 层，相当于所有儿子都向下覆盖 $i - 1$ 层，所以从 $\min sum_{u,i + 1(i < 0)}$ 转移。

当 $i > 0$ 时，此时相当于 $u$ 的一个儿子向上覆盖了 $i + 1$ 层，那么其他儿子就只需要向下覆盖 $i - 1$ 层即可，注意正负号细节。

使用 $w_u$ 转移，此时相当于所有儿子只需要向下覆盖 $u$ 层即可。

注意如果向上覆盖更大层数更有，则可以转移给下面的层数。

最后输出答案即可。

发现商品很少，考虑状压。

设 $f_S$ 表示购买了 $S$ 集合内的商品需要的最小代价，每次枚举商店，先将所有新的 $f_S = f_S + d_i$，随后枚举购买了哪个商品，即可从同一层转移，具体的

$f_S = \min(f_S,f_{S - (1 << (j - 1))} + c_{i,j})$

最后将没有转移的重新赋值为上一层，这样是避免多加了到达这个商店的花费，最后输出 $f_{(1 << n) - 1}$ 即可。