题解

思路

把完全图的边按权值从小到大加入，并用 Kruskal 重构树记录每次两个连通块的合并。若一个点集能作为合法组，则在加入它的最大内部边之后、加入它的最小出边之前，它恰好是一个连通块，所以它必对应重构树上的某个节点。

对重构树节点 $v$，记 $M_v$ 为其叶子集合中所有点对的最大边权。若 $v$ 不是根，它的最小出边正是父节点的合并边权 $W_{fa(v)}$。因此

根节点和叶子节点总是合法。

如何求全部 $M_v$？重构树建好后，对原完全图的每条边 $(x,y,w)$，求叶子 $x,y$ 的 LCA，并令该 LCA 记录 $w$；再自底向上取最大值。每个点对恰在其 LCA 处进入对应子树。

合法组构成层次集合。令多项式 $dp_v[k]$ 表示把节点 $v$ 的叶子划分成 $k$ 个合法组的方案数。若 $v$ 的两个儿子为 $l,r$，不整体选择 $v$ 时有

若 $v$ 合法，再令 $dp_v[1]$ 加一。叶子的多项式为 $x$。

做法

子任务 1：枚举集合划分

用限制增长序列枚举所有集合划分，逐组扫描内部边和出边验证。复杂度为 Bell 数量级。

子任务 2：直接扫描每个重构树节点

建立重构树后，显式保存每个节点的叶子集合，逐节点扫描所有内部点对求 $M_v$，最坏复杂度为 $O(n^3)$。

子任务 3：LCA 归属点对

用倍增预处理 LCA，把每条完全图边只归属到一个 LCA，再做树上最大值汇总。最后进行多项式 DP。复杂度为 $O(n^2\log n)$。

正确性证明

引理 1

任意合法组都对应 Kruskal 重构树中的一个节点。

证明。 合法组的全部内部边都早于任意出边。加入到最大内部边时，该组内部已经连通且尚未连接外部，因此正是一个 Kruskal 连通块。$\square$

引理 2

重构树节点 $v$ 合法当且仅当 $M_v<W_{fa(v)}$，根与叶子合法。

证明。 父节点合并边是该连通块第一次连接外部的边，即最小出边；$M_v$ 是最大内部边，条件恰与题意等价。根没有出边，叶子没有内部边。$\square$

引理 3

多项式转移正确统计每个组数的方案。

证明。 一个合法划分要么整体选择 $v$ 作为一组，要么不跨越两个儿子，分别划分两棵子树。引理 1 保证不存在第三类合法组；卷积枚举两侧组数之和。$\square$

定理

根节点多项式的第 $k$ 项等于恰分成 $k$ 组的合法方案数。

证明。 由引理 2准确识别所有可选组，由引理 3自底向上无重无漏地组合全部划分，故根多项式即所求。$\square$

复杂度

时间复杂度为 $O(n^2\log n+n^2)$，空间复杂度为 $O(n^2)$。