upd 2025.4.21：已更新线性做法。

考虑 DP。设 $f_{u,i}$ 表示 $u$ 子树的划分，且 $u$ 所在的连通块大小为 $i$。

然后你发现如果 $sz_u

对于剩下的点，记 $s_u=1+\sum_{v\in \text{son}(u)} [sz_v

然后所以一个 $sz_u\ge k$ 的点，只需要考虑同样 $sz_v\ge k$ 的儿子的 DP 值，因为剩下的儿子和自己在一个连通块里，所以合并完儿子后把自己的 DP 值偏移 $s_u$ 即可。可以用 deque 存储 DP 数组来方便偏移。

现在我们可以认为树上只剩下 $sz_u\ge k$ 的点要考虑。这是经典问题：儿子个数不为 $1$ 的点的儿子个数之和为 $O(n/k)$，所以我们可以直接用 NTT 将这些点的儿子的 DP 数组进行合并。剩下的点恰好有一个儿子，显然可以转移为 $f_{u,i}=f_{v,i}$，$f_{u,0}=f_{v,k}+f_{v,k+1}$，然后偏移 $s_u$ 的距离。所以 DP 数组只会从儿子更改一个位置，直接把儿子的 DP 继承过来即可。

总的复杂度为 $O(n/k\times k\log k)=O(n\log n)$。

以下做法来自 LHF。

其实我们还可以更进一步：不使用 NTT，我们直接将两个数组里有值的位置暴力乘起来就就可以做到 $O(n)$。

证明：注意到 $f_u$ 只有 $O(sz_u/k+1)$ 个值。因为 $u$ 子树内的连通块个数必然为 $O(sz_u/k)$，每个连通块可以选 $k$ 或 $k+1$，于是剩余的点集大小的可能性也只有这么多种。

然后其实这个东西可以被视为 $O(sz_u/k)$，因为在上面的 DP 中我们是不考虑那些 $sz_u < k $ 的点的。

所以子树大小分别为 $x,y$ 的两个点背包合并可以把复杂度视为 $O(\min(x/k,k)\times\min(y/k,k))$。

这个形式很像树上背包，考虑用类似的分析方式。

• $x/k,y/k\ge k$：显然有 $x,y$ 都是 $\Omega(k^2)$，所以这样的合并只会发生 $O(n/k^2)$ 次，每次复杂度 $O(k^2)$，乘起来就是 $O(n)$。
• $x/k< k\le (x+y)/k$：合并的复杂度为 $O(x)$，且每个点从 $sz_u/k < k$ 跳到 $sz_u/k\ge k$ 只会发生一次，在此次合并中共有 $\Theta(x)$ 个点发生了这样的转变，所以总复杂度用势能分析就是 $O(n)$。
• $(x+y)/k < k$：每次合并的复杂度为 $xy/k^2$。显然总复杂度根据朴素树上背包的分析是，每个极大的子树大小的平方和除以 $k^2$，写成 $\sum z^2/k^2$，$z$ 是 $z / k < k$ 的极大子树。显然有 $z< k^2$，所以这个式子就是 $\sum z(z/k^2)=\sum z\times O(1)=O(n)$。

于是我们成功把复杂度分析到了线性。

目前为止我是高贵的最优解。