先容斥一下转为计算任意同色点对距离不超过 $k$ 的方案数减去 $k+1$ 的。

恰好 $m$ 个非空集合是难的，因此我们不妨先放宽成 $m$ 个可空集合，接下来只需要对每个 $m'\leq m$ 计算答案再进行二项式反演即可。

手玩下可以发现对于链的情况，你从左往右扫这条链，对于一个点当前已经填过的 k-邻域内也一定是颜色两两不同的，这样就可以发现答案一定是形如 $\prod(m-ai)$ 状物，因此你希望对于树的情况也能如此。

那你再手玩下，你让深度低的先选，这样一个点 $u$ 已经填过的 k-邻域内最深的点深度也不超过 $u$ 的深度，而且任取邻域中两个点 $v_1,v_2$ 的 lca 一定是 $u,v_1$ 的 lca 与 $u,v_2$ 的 lca 中较浅的那个，由于它们和 $u$ 的距离都不超过 $k$，因此两两距离也不超过 $k$。

对于这部分也可以理解为我将所有树上距离不超过 $k$ 的点两两连边再定向为一个 DAG 使得每个点的前驱集合的导出子图是一张竞赛图，有人告诉我说初始图构成弦图所以有什么特别的道理。

直接用点分树模拟这个过程就能做到 $\mathcal{O}(n\log^2n)$，但是发现这里只关心树上距离，因此不妨考察长剖，对于点 $u$ 到某个 $u$ 的祖先的不同方向儿子 $v$ 的子树的贡献是形如对于某个深度区间（区间也只与 $u$ 的深度和 $k$ 相关）内的点全部加一，而反过来被贡献也是构成一个深度区间（也只与 $u$ 深度和 $k$ 相关），因此类似于树上邻域数点，你先用长剖正着算出每个子树内不同深度的点数，再做换根状物一点点贡献过来，贡献到长子树是枚举一个深度（不超过次长子树）贡献过去（区间加可以通过差分实现，因为你不需要随机访问），贡献到短子树的话直接枚举深度计算贡献（区间和可以先做前缀和，这里几乎是静态问题，容斥下减掉自己就行，动态的部分只是对每个深度要减去前面同深度的，因为一个点对只能算一次，这里开桶就行）即可，精细实现下就是 $\mathcal{O}(n)$ 了。

因此对于一个 $m$ 的答案是 $f(m)=\prod(m-a_i)$，由二项式反演可知我们所求即为 $\sum_{i=1}^m(-1)^{m-i}\binom{m}{i}f(i)$。

显然 $m>n$ 答案是 $0$，因此 $m=\mathcal{O}(n)$，直接做分治乘然后多点求值就能做到 $\mathcal{O}(n\log^2n)$，但是这也太菜了。

接下来做法来自 le0n：

考虑先去计算 $\log f(m)$，注意这里 $m$ 是数而非形式元。

有

$$ \log f(m)=\sum\log (m-a_i)=[t^x]\left(\sum x^{a_i}\right)\left(\sum_{i=1}^{\infty} \log(i) x^i\right) $$

因此只需计算后面那个幂级数 $\bmod t^{m+1}$ 的结果就可以得到每个 $f(m')$，只需先计算出 $\log 1,\log 2,\cdots,\log m$ 即可然后卷积，离散对数以后只需要 $\mathcal{O}(n\log n)$。