题意
树形结构n个点（n<=3000），给每个节点分配权值，子节点不能超过父亲节点的权值，问有多少种分配方案。每个节点工资上限为d（d<=1e9）.
题解
先考虑暴力dp
设f[i][j]表示钦定第i个点工资为j第i个点子树的方案树
得到转移方程$f[i][j]=\prod_{son} \sum_{k=1}^j f[son][k]$
进一步优化，设g[i][j]为f[i][j]在j这一维的前缀和。
则$f[i][j]=\prod_{son} g[son][k]$
考虑优化方法。
看起来无法改变枚举顺序，故无法使用矩阵快速幂优化。
对于第二维极大的，看看能否能用拉格朗日插值优化。
即，我们假设g[i]存储的不再是一个数组，而是一个关于j的多项式，这个多项式的功能就是把任意一个j带入多项式中，得到的值就是原来的g[i][j]。（请注意把这个多项式和生成函数区别开来）
我们现在需要知道该多项式项数至多是多少。
考虑对于每一个叶子结点，无论j是多少，它的f[i][j]始终是1，则g[i][j]=j。即g[i]线性递增，是一个一次函数。
观察
$g[i][j]=\sum_{k=1}^jf[i[j]=\sum_{k=1}^j\prod_{son} g[son][k]$
那么g[i][j]的次数至多等于g[son][k]的次数之和+1（连乘之后还有一个包含j项的求和，j是多项式的主元，所以要加1），也就是一个size[i]次多项式。
然后我们先dp出g[1][1~n]，再插值求出g[1][d]即可。
然而一般而言插值时证明最高次数不需要如此严谨，考场一般靠猜（逃