题解：P13804 [SWERC 2023] In-order

bsdsdb · 2025-11-20 16:38:24 · 题解

题意：给你一个二叉树的前序遍历，后序遍历，以及中序遍历的一个区间，问有多少二叉树与之匹配。n\le10^6。

解：首先只看前序遍历 \{p_i\} 和后序遍历 \{s_i\}，发现 p_1=s_n 是根，然后 p_2 是左子，s_{n-1} 是右子，如果二者一样说明根只有一个子节点；更一般化地讲，如果一个子树对应前序遍历区间 [l_1,r_1] 和后序遍历区间 [l_2,r_2]，那么 p_{l_1}=s_{r_2} 是根，p_{l_1+1} 是左子，s_{r_2-1} 是右子，如果二者相同说明只有一个子节点，此时将子树根称为非确定点。所以我们可以得出树的大致结构，只有有一个子节点的点在左边还是右边我们不知道。

接下来就看中序遍历了。如果中序遍历没指定，那么直接输出 2^{\mathrm{cnt}}。否则，我们先认定所有非确定点都只有左子，将一个点在中序遍历中的位置称为排名，类似平衡树。如果中序遍历只给了一个点，那么我们需要调整这个点的排名以适配。有两种调整方式：

• 选择他到根路径上的某个非确定点（不能是他自身），将左子调成右子，使排名加 1；
• 如果他是非确定点，将他的左子变到右子可以是排名减少子树大小；

所以组合数就能解决。

如果中序遍历给了不止一个数，那么需要调整树的给定的点在中序遍历中的相邻关系以及第一个给定点的排名。先来看相邻关系。中序遍历上 u 在 v 紧挨着的前面，只能是 v 在走一次左子再走若干次右子之后能走到 u 且 u 无右子，或者 u 在走一次右子再走若干次左子后能走到 v 且 v 无左子。根据上述要求将一些非确定点的左子 / 右子选定，然后再根据上一段的方法调整第一个给定点的排名即可，暴力也是 \Omicron(n) 的。