[LOJ 6285] 花朵（树链剖分+分治ntt)

题意

给出一棵 $n$ 个点的树，每个点有点权 $v_i$，选出 $m$ 个不相邻的点，代价为这 $m$ 个点的权值之积。求所有合法方案的代价和，对 $998244353$ 取模。
$n,m\le 8\times 10^4,v_i<998244353$。

分析

令 $d{p}_{0,u,j}$ 表示来到节点 $u$，不选节点 $u$，总共选了 $j$ 个点的代价和；$d{p}_{1,u,j}$ 表示来到节点 $u$，选了节点 $u$，总共选了 $j$ 个点的代价和。容易看出转移是个树形背包，可以在 $O(n^2)$ 内转移。
进一步的，我们发现转移是个卷积操作，于是令 $d{p}_{0,u}$ 表示来到节点 $u$，不选节点 $u$ 的生成函数，$d{p}_{1,u}$ 表示来到节点 $u$，选了节点 $u$ 的生成函数，于是有以下转移：
$$\begin{gathered} d{p}_{0,u}=\prod _{(u,v)}(d{p}_{0,v}+d{p}_{1,v}) \\ d{p}_{1,u}=(v_{u}x)(\underset{(u,v)}{} \end{gathered}$$