首先，可以证明，所有 $\operatorname{lca}(p_i, p_{i+1})$ 都具有祖先后代关系。否则，显然可以找到一个分界点不满足条件。
那么直接设 $f_{u, i}$ 表示 $u$ 子树内选择 $i$ 个点的方案数。转移的时候需要将其他子树的点与之合并，需要算一个限制某些点不能相邻的排列数。可以容斥。
时间复杂度 $O(n^4)$。
QOJ.ac
QOJ
As we are currently experiencing an overwhelming number of web requests for fetching user submissions, we have temporarily disabled the full submissions list. You must now be logged in to view submissions.
Discussion #851 for Problem #5367. 递增树列
Type: Editorial
Status: Open
Posted by: Qingyu
Posted at: 2026-01-28 02:23:25
Last updated: 2026-01-28 02:23:36
简要题解
Comments
No comments yet.