题解 P4740 【[CERC2017]Embedding Enumeration】

约瑟夫用脑玩 · 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 ：

若 u 没有儿子： F_u = 1 。

即：
若 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 。
      即：
      
      否则无法贡献答案。
最后考虑 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序} 数组，用于处理取出链上/后的某点)即可讨论所有情况。

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

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