[计数] [dp] P12059 [THUPC 2025 决赛] I'm Here

_Cheems · 2025-04-20 21:35:38 · 题解

题意：n 个点的树，1 为根。保证存在一种 dfs 序为 1\dots n。对每个 k\in [1,n]，求满足如下性质的数列 p 个数：

前两个限制为拓扑序计数，有平方的树上背包做法。但由于该做法是“插入计数”的，所以难以维护第三个限制，因为需要具体位置而非相对位置。

实际上插入的过程是很自由的，能否通过适当的插入顺序，来规避这个问题呢？

尝试简化限制三，注意到 i<j 且 p_i<p_j 则 i 受到的限制肯定比 j 更紧，因为非法后缀更小且位置更左。这启发我们从大到小插入元素。

记 f_{i,j} 为元素 \ge i 且最右一个位置在 j 的方案数。对于 i-1，假如插入在最右边，其祖先不可能被操作，易处理；否则无需考虑限制三，但是可能影响 i-1 子树内的元素，整体考虑该子树的方案再归并回去即可，因为该子树的元素整体偏小所以结论仍成立。

预处理 g_{i,j} 为子树内 j 个点拓扑序数量即可。转移是朴素的，简单前缀和优化为 O(n^4)。