题目给了一刻编号为搜索序的树,我们形式化限制,考察方案序列:
- 若 \(u\) 是 \(v\) 的祖先,则 \(u\) 在 \(v\) 后面。
- 第 \(i\) 个点只能出现在 \([1,n-i+1]\) 这些位置中。
显然限制一是一个树上拓扑序计数的东西,我们设 \(g(i,j)\) 表示子树 \(i\) 中选 \(j\) 个的方案数可以 \(\mathcal{O}(n^2)\) 合并求得。现在重点考虑限制二,我们发现越往后限制越紧,编号越大限制越紧,于是我们可以发现后缀最大值的限制是更严格的,于是我们可以不用关心其它位置的第二个限制,这么做的好处是使得我们需要考虑的东西是单调的,有利于我们进行 dp。
如果从大到小考虑,那么能成为后缀最大值的数只能是考虑到他时放在最后一个的数。
我们不妨设 \(f(i,j,k)\) 表示填完了前 \(i\) 大的数,填了 \(j\) 个,当前最后一个数在位置 \(k\)。转移有三种,第一种是直接不选,只有 \(i=1\) 时无法转移。第二种是选并成为后缀最大值,此时位置可以是 \([k+1,n-i+1]\),显然它是能够满足限制一的。
第三种有点麻烦,因为我们发现如果不是后缀最大值就可能不满足限制一。但是由于 \(i\) 子树内所有结点编号是一段区间且 \(i\) 最小,而 \(i\) 不在最后一个则子树内都不可能成为后缀最大值,这是我们希望看到的,于是我们直接插入就好了,枚举选的个数 \(l\),那么有
\[f(i,j+l,k)\leftarrow f(i+size_i,j,k)\times g(i,l)\times\binom{k-j}{l}
\]
于是做完了,时间复杂度 \(\mathcal{O}(n^4)\)。