test20190814

$T2$ 被常数卡到暴力分了.

$tree$

原题.直接树形 $dp$ .

$dance$

从前往后枚举右端点,依次加入每个点,用单调栈维护后缀最大/最小值,线段树维护答案.

$seq$

打表或者分析,把递推式子搞出来, $f_i=f_{i-1}+(i-1)\cdot (i-2)$ .

然后用特征方程那一套理论把通项找出来, $f_n=2^{n+1}-n^2-n-2$ ,就可以直接算了.