拉插优化 dp 在卷怪们眼里已经变成套路了吗，害怕。
考虑一个 dp 的推。设 \(f_{u,i}\) 表示 \(u\) 子树中填 \([1,i]\) 符合题目条件的方案数，此时不强制 \(u\) 选 \(i\)，所以有：
\[f_{u,i}=f_{u,i-1}+\prod\limits_{v\in \text{son}(u)}f_{v,i}
\]
直接做是 \(O(nd)\) 的。考虑奇技淫巧优化。
考虑到边界情况，就是 \(u\) 为叶子时，\(f_{u,i}=i\)，这是个关于 \(i\) 的一次函数。
同时这个转移形式比较诡异，是儿子的值全部乘积然后求和。那么如果设 \(u\) 的 \(f_{u,i}\) 是关于 \(i\) 的 \(g_u\) 次函数的话，对于树上任意一个非叶节点：
\[\begin{aligned}g_u&=1+\deg \left(\prod\limits_{v\in \text{son}(u)}f_{v,i}\right)\\&=1+\sum\limits_{v\in \text{son(u)}}g_v\end{aligned}
\]
由于 \(v\) 是叶子时 \(g_v=1\)，我们容易归纳出 \(g_u=\text{sz}_u\)，即 \(u\) 的子树大小。于是 \(f_{u,i}\) 是关于 \(i\) 的 \(\text{sz}_u\) 次函数。
如果 \(d\le n+1\)，直接暴力 dp；否则处理出 \(f_{n,1}\) 到 \(f_{n,n+1}\) 的值，用拉格朗日插值把 \(f_{n,d}\) 插出来即可。
复杂度 \(O(n^2)\)。