君よ いっそいっそ いなくなれ

変わらない このままなら

显然题中生成的BST就是笛卡尔树，但是如果因此就往子树合并类的DP想的话就寄了（比如我）。

正确的做法是，将点的深度转化为祖先的个数，进而转化为每个点成为它祖先的方案数。即

$$Ans_u=\sum_v{\sum_{BST} [v\in anc(u) ]}$$

而 $ [v\in anc(u) ]$ 的充要条件是 $v$ 是 $u,v$ 间的最小值。

如果不考虑 $(u,v)$ 的限制，计算恰有 $k$ 个逆序对的排列数是经典的。令 $f_{i,j}$ 表示 $i$ 个数的排列，已有 $j$ 个逆序对的方案数，枚举 $p_i$ 与前 $i-1$ 位的相对大小，有

$$f_{i,j}=\sum_{k=0}^{i-1} f_{i-1,j-k}$$

这是可以写作生成函数的，令 $F_i=\sum f_{i,j}x^j$，有

$$F_n=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n}$$

这允许我们 $O(n^3)$ 的计算总方案数。

现在有了 $(u,v)$ 的限制，先考虑 $u>v$ 的情况。

注意到上面的DP实际上是在往排列中一个一个塞数，而往最前端塞和最后端塞实际上是等价的。

那我们可以先将 $u,v$ 间的数先塞完，那么其它数就跟正常一样的。而增加的限制无非就是在塞 $v$ 的时候令 $k=0$，因为 $v$ 最小，无法产生逆序对。记 $L=u-v+1$，那么我们只用撤销第 $L$ 次转移，即

$$G=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n} \frac{1-x}{1-x^L}$$

那么当前的贡献就是 $[x^k]G$。

上面的式子直接算的话是 $O(n^4)$ 的。

我们可以先预处理 $\prod_{i=1}^n(1-x^i)$，并递推求出 $(1-x)^{n-1}G$，然后计算 $[x^k]G$，就可以做到 $O(n^3)$了。

对于 $u<v$ 的情况，无非就是在塞 $v$ 的时候令 $k=L-1$，做法是类似的，不再赘述。

注意到还有 $u=v$ 的贡献，其实就是没有限制的方案数。

于是总时间复杂度 $O(n^3)$。