考察弱化限制以此来解决问题。
设 \(f_{i, j, k}\) 表示经过了 \(i\) 步从 \(j \to k\) 的路径数量，按照 \(i\) 从小往大转移，这一部分复杂度 \(O(n^3d)\)。
但是并未限制 \(j, k\) 只能够经过一次，我们一步一步限制，不妨先限制 \(k\) 只经过一次，那么设 \(g_{i, j, k}\) 表示一定经过 \(k\) 一次的方案，那么考虑容斥，枚举第一次出现的位置，有：
\[g_{i, j, k} = f_{i, j, k} - \sum_{l = 1}^{i - 1}g_{l, k, k} f_{i - l, k, k}
\]
限制起点比较麻烦，不妨我们强行让路径不经过点 \(v\) 回到 \(u\)，这才符合我们上述容斥的步骤，然而这个也是好求的，同样使用容斥解决即可。