自动搬运

查看原文

来自洛谷，原作者为

	Monomial ?

搬运于2025-08-24 23:06:40，当前版本为作者最后更新于2025-08-12 10:24:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑在原来的网格图上我们的最优策略是什么。容易发现，我们一定有一种情况不会走回头路。但是在树上，我们一定要走回头路，我们就要考虑什么样的路径等价于在网格图上不走回头路。

我们考虑上图的情况。在网格图上，我们会走一个长方形的轮廓，但是在树上我们会多走一次下方的黑色线。在类似的情况，即同一行或同一列有 $\geq 2$ 条边时，树上的路径肯定是更劣的。可以证明，不含这种情况的 $S$ 必定是合法的。

思考如何计数，首先考虑比较简易的 $\mid S \mid = 2$。

这两个点之间的路径只有这两种情况，我们按两个方向做下前缀和即可，然后对同一行或同一列的情况去重。

接下来我们考虑如何做 $\mid S \mid = 3$，对比 $\mid S \mid = 2$ 只多了四种情况（下图旋转可以得到）。

我们在红点处计数即可，同样注意去重直接向三个方向延伸的情况。

最后我们考虑 $\mid S \mid \geq 4$ 的情况，对比 $\mid S \mid = 3$ 只多了两种情况（下图旋转可以得到）。

那么我们现在无法在红点直接计数这个东西，因为同时出现了两个红点。那么我们可以尝试记录右下角红点的信息，然后带到左上角的红点计数，依然要注意去重直接向四个方向延伸的情况。

最后说一下第一问具体如何实现，其他两问是类似的。我们对边进行分类，即区分不同方向来的边，同时设 $dp_{i,j,S}$ 为我们走到点 $(i,j)$，且经过的边类型集合为 $S$ 的方案数，那么可以 $\mathcal{O}(n^{2}2^{k})$ 转移并计算答案，其中 $k=4$。对于两个红点的情况，我们可以再设 $f_{i,j,S}$ 表示有红点，且经过的边类型集合为 $S$ 的方案数，这个和 $dp$ 一起算即可，总复杂度还是一样的。代码细节比较多，建议想好再写。