题解

思路推导

从根出发的一条路径由边权序列唯一确定，因此问题等价于统计和为 $n$、每项位于 $1$ 到 $k$、并且至少有一项不小于 $d$ 的有序序列。

设 $f_{i,0}$ 表示总和为 $i$ 且尚未使用大边的序列数，$f_{i,1}$ 表示总和为 $i$ 且已经使用过大边的序列数。空序列满足 $f_{0,0}=1$。从状态 $i$ 追加权值 $x$ 后转移到 $i+x$；若 $x\ge d$，新状态已经使用大边，否则保持原状态。

做法

按总和从小到大枚举 $i$，再枚举下一条边权 $x=1,2,\ldots,k$，执行上述转移。最终答案是 $f_{n,1}$。

当 $n\le 15$ 时，可以深度优先枚举所有有序拆分并逐条检查。特殊地，当 $d=1$ 时，每条边都满足要求，问题退化为普通的有序组成计数，只需一维状态。另一种独立核验方式是用所有权值不超过 $k$ 的序列数，减去所有权值严格小于 $d$ 的序列数。

正确性证明

对任意总和不超过 $n$ 的边权序列，状态第二维准确记录其中是否已经出现权值不小于 $d$ 的边。追加一条边时，转移按照新边是否达到阈值更新该标记，所以每条合法序列沿其前缀产生唯一的状态转移路径。

反之，每条从 $f_{0,0}$ 出发的转移路径对应一个边权均在 $1$ 到 $k$ 的有序序列。到达 $f_{n,1}$ 当且仅当序列总和为 $n$ 且至少含一条大边。因此 $f_{n,1}$ 与题目要求的路径一一对应，算法正确。

复杂度分析

时间复杂度为 $O(nk)$，空间复杂度为 $O(n)$。