主要结合两道例题讲，复杂度的计算很重要。

LOJ6290 花朵

非常容易可以考虑到树上背包的做法，但是过不了。

怎么将这个 \(\text{dp}\) 优化呢？考虑背包实际上就是一个卷积的形式，所以我们可以用多项式科技优化卷积过程。

可以想到的，我们不能将背包直接卷积，因为复杂度由 \(O(nm)\) 变成 \(O((n+m)\log(n+m))\) ，在 \(n=1\) 的时候复杂度反而会变慢。

具体的，我们将原树轻重链剖分，对于一个点，我们先通过类曼哈顿的贪心，每一次将最小的两个轻子树合并，等到一条重链上的点的所有节点的轻子树都合并完成了，我们再在这条重链上做分治 \(\text{fft}\) 。

复杂度是 \(O(n\log^3n)\) ，具体证明的话应该是考虑重链和轻链分开算。

对于重链来说，考虑每个点会向上跳 \(\log n\) 次，每次链上做合并的时候贡献 \(\log n\) 次，每次是 \(\log n\) ，所以复杂度是 \(O(n\log^3 n)\) 的。

对于轻链来说，考虑每一个点的贡献，由于每一个点在一次合并操作中的均摊复杂度可以近似看成 \(O(\log n)\) ，所以我们只需要计算出每一个点的操作次数即可。考虑一个点在进行轻子树合并的时候大小一定翻倍，所以其从自己位置一直合并到根的合并次数是一定小于 \(\log n\) 的，所以这里的复杂度是 \(O(n\log^2n)\) 的。

卧槽发现有个直接套距阵的老哥，也太帅了吧。

我顿悟了，距阵掌握度 +1 。

关于矩阵实现的细节很重要。对于矩阵的优化，一定需要写出对应的状态转移方程，然后根据转移前的矩阵和转移后的矩阵写出转移矩阵。

#include
using namespace std;
const int N=131072;
const int MOD=998244353,G=3;
int ADD(int x,int y){return x+y>=MOD?x+y-MOD:x+y;}
int TIME(int x,int y){return (int)(1ll*x*y%MOD);}
int ksm(int x,int k=MOD-2){int res=1;for(;k;k>>=1,x=TIME(x,x))if(k&1)res=TIME(res,x);return res;}
int rev[N],lst=0;
void get_rev(int lg){
	if(lst==lg) return ;else lst=lg;
	for(int i=0;i<(1<>1]>>1)|((i&1)<<(lg-1)));
}
struct Polynomial{
	vector f;
	int &operator [] (int x){return assert(x<(int)f.size()),f[x];}
	int len(){return (int)f.size();}void clear(){return f.clear();}
	void resize(int n){
		while((int)f.size()>n) f.pop_back();
		while((int)f.size()>1),g=ksm(G,(MOD-1)/len);if(tag) g=ksm(g);
			for(int i=0;i