首先把树上最大独立集的 dp 抽象一下，可以得到如下做法：对于每个点求出 \(b_i=\max(0,a_i-\sum\limits_{j\in son_i} b_j)\)，则所有 \(b\) 之和就是最大独立集。
则我们设 \(dp_{i,j}\) 表示第 \(i\) 个点的 \(b_i=j\) 时的方案数，直接朴素的 dp 时 \(O(nm^2)\) 的。
一个猜想是 \(dp_i\) 可以用很简单的形式表示出来。实际上，\(dp_{i,j}(0<j\leq m)\) 是一个次数不超过 \(siz_i\) 的多项式在 \(j\) 处的点值。
先考虑怎么把子树的 \(dp_i\) 乘起来，比如现在需要合并两个大小分别为 \(siz_i\) 和 \(siz_j\) 的子树，则合并后可以用一个 大小为 \(siz_i+siz_j\) 的多项式刻画。因此我们将两棵子树都插值到 \(siz_i+siz_j\)，然后将这两部分进行一个卷积就行了。
然后现在我们有了这个多项式的点值，需要取反以及前缀和，这同样需要插出 \(siz_i\) 个点值，对于连续点值的插值，可以用 NTT 做到 \(O(n\log n)\)，因此总复杂度 \(O(n^2\log n)\)。
最后一个问题就是对于 \(j\leq m\) 的位置是对的，但是更大的是不对的。对于这样的情况，因为更大的会和 \(0\) 取 \(\max\)，所以只需要用总和减去所有最终卷积出来 \(\leq m\) 的位置的值之和，然后增加到 \(0\) 即可。
标签：log,siz,独立,leq,8670,QOJ,dp From： https://www.cnblogs.com/275307894a/p/18407114