考虑转化为求 \(\ge i\) 的权值个数 \(\ge k\) 的联通块数量。
设 \(f(u,i,j)\) 表示 \(u\) 子树内含 \(u\) 联通块内权值 \(\ge i\) 的有 \(j\) 个的方案数，\(g(u,i,j)\) 维护子树的和，也就是最终答案。发现转移非常简单所以可以写成生成函数：
\[F(u,i) = x^{[d_u\ge i]} \prod_{(u,v)\in E} (F(v,i)+1)\\ G(u,i) = F(u,i) + \sum_{(u,v)\in E} G(v,i) \]因为模数非常 shaber 所以 NTT 卷积不行，那只能换个方法。这个东西已经是个多项式了，所以直接把 \(n+1\) 个值带到式子里，然后最后拉插一波就行。
然后你发现直接拉插仍然是低贱的 \(\mathcal O(nw^2)\) 和直接树形背包没区别，但是我们现在的转移形式非常简单！于是你考虑整体 dp，线段树合并，然后并没有什么突破。
考虑一个不太像是人类能想出来的变换。\((a,b,c,d)*(f,g)\to (af+b,cf+g+d)\)。这个操作可以理解成矩阵乘法的压缩，具有结合律。两个变换相乘需要自己手推一下，比较简单。一开始把 \(\langle f,g\rangle\) 分别放到 \(\langle b,d\rangle\) 的位置就行。
然后考虑我们现在需要的操作：
- 全局赋值 1。
- 区间乘。
- 全局 +1。
- 全局 \(G\gets G+F\)。
我们考虑对应形式的维护：
- \((0,1,0,0)\)。
- \((x,0,0,0)\)。
- \((1,1,0,0)\)。
- \((1,0,1,0)\)。
然后就完事了。用线段树合并均摊维护 \(\mathcal O(nw\log w)\)。
标签：考虑,然后,ge,九省,rangle,全局,联考,D1T3 From： https://www.cnblogs.com/663B/p/17657574.html