思路 考虑构建二叉搜索树的过程。对于一个元素 x 和它在初始树上的任一祖先 fa，如果 x 先于 fa 被放入，那么 x 会顶替祖先 fa 的位置。因此「生成相同的二叉搜索树」等价于「任意元素 x 不能先于其祖先加入」。 这相当于求初始二叉搜索树的拓扑序数量。假设结点 x 的子树大小为 sz_x，拓扑序数为 f_x，那么两个子树 x,y 合并后的拓扑序数为 f_x \times f_y \times \binom{sz_x+sz_y}{sz_x}。模拟建树过程后做上述 DP 可以 O(n^2) 通过本题。…