简要题意.
给定一棵 $n$ 个点的树，求点分树方案数。
$n \le 5000$。
考虑连一条边 $(u, v)$ 导致点分树合并的过程，事实上与一般的数据结构合并是一致的：传入两个根结点，并考虑选择一个成为最后的根结点，将剩下的部分沿着 $u, v$ 所在的链递归。
因此，我们只需要记状态 $f_{u, i}$ 表示 $u$ 子树内的点分树，$u$ 的深度为 $i$ 的方案数。
转移时先对儿子的 DP 数组做后缀和，再合并。时间复杂度 $O(n^2)$。
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 #850 for Problem #5357. 芒果冰加了空气
Type: Editorial
Status: Open
Posted by: Qingyu
Posted at: 2026-01-28 02:23:06
Last updated: 2026-01-28 02:23:18
题解
Comments
No comments yet.