自动搬运

查看原文

来自洛谷，原作者为

	约瑟夫用脑玩 AFO

搬运于2025-08-24 22:03:08，当前版本为作者最后更新于2021-01-09 17:37:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：

输入一棵树，求把这棵树放入 $\text{2*n}$ 的网格图中的方案数，对 $\text{1e9+7}$ 取模。

要求： $\text{1}$ 在左上角，有边连接的节点必须相邻。

题解：

有点小妙的 $\texttt{DP}$ (其实就是我没想到)。

其实情况不算太多(吧)。

先把 $\text{1}$ 当做根。

设 $F_x$ 表示以 $x$ 为左上角，它本身以及子树全部放进去了的方案数。

可以看做 $x$ 左边暂时为墙，不能放，答案即为 $F_1$ 。

首先注意到每个点最多只有两个儿子，即度数不超过三。

考虑转移，设当前节点为 $u$ ：

1. 若 $u$ 没有儿子： $F_u = 1$ 。

   即：

2. 若 $u$ 只有一个儿子：

   • 先考虑将其儿子，设为 $v$ ，放在其下面。

     • 若 $v$ 没有儿子， $F_u = F_u + 1$ 。

     • 若 $v$ 只有一个儿子 $w$ ， $F_u = F_u + F_w$ 。

       即：

     • 若 $v$ 有两个儿子，不能贡献方案。

   • 再考虑将其儿子放在其右边，考虑 $u$ 下方是否放点。

     • 若不放，设其儿子为 $v$ ，则显然有 $F_u = F_u + F_{v}$ 。

       即：

     • 若放，考虑如下情况：

       • 若 $u$ 及其子树为一条长度大于 $\text{2}$ 的偶链，则 $F_u = F_u + 1$ 。

         即：

         否则，设 $x$ 第一个有两个儿子的节点为 $nxt_x$ ，叫做 $x$ 的分叉节点。

         • 若 $nxt_u$ (设为 $v$ )的一个儿子为链。

           由于必须在 $u$ 下放点，则需满足将链折过去后恰好在 $u$ 底下，有两种情况： $dist(u,v) = len_\texttt{链}$ 或 $dist(u,v) - 1 = len_\texttt{链} + 1$ ，设 $v$ 的另一个儿子为 $w$ ，此时 $F_u = F_u + F_w$ 。

           即：

           或

           注：将左下与左上翻折后是一样的，故方案数相同，均为 $F_w$ 。

         否则设 $nxt_u$ (设为 $p_1$ )的一个儿子为 $p_2$ ，同理，要满足折一条链到 $u$ 的底下，需 $p_2$ 的一个儿子为链且满足： $dist(u,p_1) = len_\texttt{链} + 1$ 。

         此时设 $p_1$ 的另一个儿子为 $v$ ， $p_2$ 的另一个儿子为 $w$ 。

         • 若 $v$ 与 $w$ 恰为长度相同的链，则 $F_u = F_u + 1$ 。

           即：

         • 若 $v$ 与 $w$ 一个为较短的链，另一个在较短链的长度内都为链，也即有一条满足 $len_\texttt{较短链} \le len_\texttt{较长链}$ 的链，设齐平后较长链的对应儿子为 $x$ ，则 $F_u = F_u + F_x$ 。

           即：

         否则无法贡献答案。

3. 最后考虑 $u$ 有两个儿子的情况：(好累啊qwq)

   需有一个儿子放在 $u$ 下面，所以那个儿子不能有两个儿子。(上面是 $u$ ，左边和下面是墙，只能有一个在右边)

   设 $u$ 另一个儿子为 $v$ 。

   • 若其(设为 $w$ )没有儿子，显然有 $F_u = F_u + F_v$ 。

   即：

   • 否则只有一个儿子，设其儿子为 $w$ ，发现与上文中：“ $p_1$ 的另一个儿子为 $v$ ， $p_2$ 的另一个儿子为 $w$ ”的情况相同。即考虑是否为等长的链或是 一个较短链，另一个有比它长的链。(如果你足够懒，像我一样，就可以封一个函数处理这种情况)

     还是放张图吧：

至于具体实现并不难，且只需 $O(n)$ 预处理出 $nxt[]$ 与 $dfn[]$ ( $\texttt{DFS序}$ 数组，用于处理取出链上/后的某点)即可讨论所有情况。

代码细节没有，只要将所有上述情况讨论完即可。

记得两个儿子中的一个要讨论，代码就不放了。