UCUP-ZJ

题意 给定一个位置x，求在$p_x$分别取1-n的所有情况下，对应笛卡尔树不同的排列个数。 题解 先不考虑$p_x$，列出转移式，发现是卡特兰数。 进一步地，可以把排列对应笛卡尔树意义下的不同构数，和二叉树不同构数等价联系起来：因为对于任何一个二叉树，按照中序遍历在上面填1-n，就可以唯一确定一个排 ......