(x,y)与(y,x)等价。简单模拟可得，会先走完1~x+1，再到y-1，再到n,再到,y
两边方案数唯一，中间想到与从1走到k的方案数
简单递推可得\(f_x=f_{x-1}+f_{x-3}\)，分类讨论一下即可
可以拆分成两个问题：点x的子树有所有颜色，原树删掉x的一个儿子后仍有所有颜色
问题1：树上分治，根到\(a_x\)+1，根到\(lca(last_{a_x},a_x)\)-1
问题2：维护颜色\(i\)的所有点的\(lca\)，\(lca\)到根上所有点为根的子树都不能被删
遍历几遍树即可
首先考虑\(a_i\)互不相同
即\(Max-Min=r-l\)，移项得\(Max-Min+l=r\)
枚举r，用两个单调栈存最大最小值的位置，\(Max-Min>=r-l\)区间维护一下最小值与其个数即可
\(a_i\)一般时，式子变为了\(Max-Min=r-l-cnt\)，cnt为重复出现的数的个数
设\(last_{a_r}\)为上一个\(a_r\)的位置，考虑cnt的变化值，区间加一即可
在改了在改了(0%)
原文：https://www.cnblogs.com/namevastblog/p/13910172.html