若不区分左右子树，则通过前序遍历和后序遍历已经可以确定出树的形态。那么只需要数对于只有单个子树的点规定其子树的方向，有多少种方式合法。

设 DP $f_{x,i}$ 表示以 $x$ 为根的子树，如果从 $C$ 的第 $i$ 个位置开始匹配，有多少种合法的方式。

直接转移是 $O(N^2)$ 的。

设 $p_x$ 表示 $x$ 在 $C$ 中的位置。

对于 $p_x$ 都为 $0$ 的子树，我们只需要记录有多少个单子树的点即可。对于有 $p_x$ 的子树，我们用若干组点对 $(s,v)$ 表示有值的状态。以下简称这两种情况为“有”，“无”。可以发现“有”的子树状态数是 $O(size_x)$ 的。

然后是一些分类讨论。

• 对于 $x$ 有两棵子树的情况

  • $p_x\neq 0$：最多只有一个合法状态。
  • $p_x = 0$：需要枚举子树的状态进行转移。

• 对于 $x$ 有一棵子树的情况

  • $p_x\neq 0$：最多只有两个合法状态。
  • $p_x = 0$：对于子树内的所有状态，分根放在前面还是放在后面转移。

首先我们可以简单地通过打偏移量标记的方法处理 $x$ 有两棵子树且 $p_x=0$ 时两棵子树中只有一个“有”时的转移。如果两个子树都“有”则是启发式合并。

这样我们几乎可以处理所有转移，除了“$x$ 有一棵子树且 $p_x=0$”的情况。

考虑仍然通过打标记的方式解决这种情况。用一个标记 $cnt$ 表示“连续进行了多少次这样的转移”。

这样有一个问题：我们没法在打着标记的情况下快速的得到实际的 DP 值。那么在有这个需求的时候只能下放标记。

接下来就只剩两个问题了：如何下放标记；复杂度是否正确。

对于原本的状态 $(s,v)$，在 $cnt$ 标记的作用下会贡献到 $[s-cnt,s]$ 的状态。具体的，枚举 $cnt$ 次转移中有 $i$ 次根被放在了前面，那么会以 $\binom{cnt}{i}$ 的系数贡献到 $s-i$。这个过程可以使用 NTT 优化。

接下来分析时间复杂度。这里用合法状态极差来表示一个点的状态数（也就是看作一个区间）。

考虑什么时候需要得到子树的 DP 值进行转移：$x$ 有两棵子树且 $p_x\neq0$；$x$ 有两棵子树 $p_x=0$ 且两棵子树都“有”；$x$ 有一棵子树且 $p_x\neq 0$。

对于第一种情况，最后只会剩下长度为 $1$ 的区间，可以看作把子树的状态“消耗”掉了。

对于第二种情况，最后只会剩下长度为两个子树中长度较小的区间，因此可以看作花了较小方的复杂度转移，把较大方“消耗”掉了。

一个区间如果打上了 $cnt$ 的标记，则只会向两端扩展 $cnt$ 个。因此由 $cnt$ 标记产生的新状态是 $O(N)$ 的。由启发式合并产生的新状态就是 $O(N\log N)$ 的，因此上诉两种情况被“消耗”掉的状态就是 $O(N\log N)$ 的。

第三种情况会有一些问题，因为虽然只会剩下两个状态，但这两个状态形成的区间还是 $O(size_x)$ 的，因此不能看作“消耗”掉了子树的状态。

但是我们可以将其看作“继承”了子树的状态。这种情况我们只需要知道子树中两个位置的 DP 值。考虑不进行 NTT 而是直接暴力计算。单次计算是 $O(cnt)$ 的，因此“继承”的复杂度总消耗是 $O(N)$ 的。

但其实也可以不这么处理。发现如果子树“有”的话 $x$ 最多只有一个状态，因此仍然可以用“消耗”的方式分析。

用略暴力的方式转移大概可以过所有特殊性质。

时间复杂度： $O(N\log^2 N)$。