CF1010F 与 ABC269H：有多少个包含根的连通块？

CF 传送门

AT 传送门

两题主要 Trick 相同。CF 的还多了一个小 trick。

给定一棵根节点为 \(1\) 的二叉树 \(T\)，你需要先保留一个包含 \(1\) 号节点的连通块，然后给每个点确定一个权值 \(a_i\)，使得对于每个点 \(u\) 都有其权值 \(a_u\) 大于等于其所有儿子的权值和 \(\sum a_v[(u,v)\in T]\)。

最后，你需要使得根节点权值为 \(x\)，求方案数，答案对 \(998244353\) 取模。

\(n\le 10^5,x\le 10^{18}\).

即 \(a_u-\sum_{v\in son(u)}a_v\ge 0\)，令 \(b_u=a_u-\sum_{v\in son(u)}a_v\)，即 \(b_u\ge 0\)。注意到 \(\sum b_u=x\)，且 \(\{a_i\}\) 与 \(\{b_i\}\) 一一对应，所以分配 \(a_i\) 相当于分配 \(b_i\)。而如果选了固定 \(k\) 个点，分配 \(b_i\) 就是把 \(x\) 分给 \(k\) 个数，每个数 \(\ge 0\)。这是经典结论，有 \(\binom{x+k-1}{k}\) 种分配方式。

于是下面的问题就是对于每个 \(k=1\sim n\)，求出有多少个 \(k\) 大小的包含 \(1\) 的连通块。

法一：普通树形 DP。\(dp[i][j]\) 表示在 \(i\) 的子树内选 \(j\) 个点的方案数。转移方程 \(dp[i][j]\leftarrow dp[i][j]+\sum_{v\in son(i),k<j}dp[i][k]\cdot dp[v][j-k]\)。因为每一对点的复杂度在其 LCA 处贡献 \(O(1)\) 次，复杂度是 \(O(n^2)\) 的。

法二：dfs 序 DP。\(dp[i][j]\) 表示考虑 dfs 序 \(<i\) 的结点选不选，共选了 \(j\) 个的方案数。转移方程 \(dp[i][j]\rightarrow dp[i+1][j+1]\)，\(dp[i][j]\rightarrow dp[mx_i+1][j]\)。复杂度 \(O(n^2)\)。

法三：FFT + 树剖优化法一。注意到法一 \(\sum dp[i][k]\cdot dp[v][j-k]\) 的形式是卷积，考虑使用 FFT 优化。转移方程为 \(F(u)=x\cdot F(son_1)\cdot F(son_2)+1\)。

但是直接上复杂度是 \(O(n^2\log n)\) 的，因为两个式子卷积 \(O(len\log len)\)，所以每一对点贡献的复杂度变成 \(O(\log n)\) 了。

难道这个做法没有用吗？不，我们还有办法！上面做法的问题在于每个点会被使用太多次了。有什么办法是让一个点出现次数变少的？

树剖！我们进行重链剖分，仅在重链链顶处统计重链上所有的点和轻儿子的贡献。

如图。在重链链顶 \(u_1\) 处计算 \(F(u_1)\)，可以一路分解下去到轻儿子。记相关的多项式为 \(a_1\sim a_4\)，要求的形式即为 \(1+a_1+a_1a_2+a_1a_2a_3+a_1a_2a_3a_4\)，而 \(a_i\) 的大小之和是 \(O(n)\) 的。这种形式可以用分治 FFT 计算。

具体而言，我们在计算 \(a_1+\cdots +a_1\cdots a_n\) 时，先递归计算 \(a_1+\cdots+a_1\cdots a_{n/2}\) 和 \(a_{n/2+1}+\cdots+a_{n/2+1}\cdots a_n\) 部分。同时让这两部分额外返回 \(a_1\cdots a_{n/2}\) 和 \(a_{n/2+1}\cdots a_n\) 的值，则当前结果即为 \(a_1+\cdots+a_1\cdots a_{n/2} + a_1\cdots a_{n/2}(a_{n/2+1}+\cdots+a_{n/2+1}\cdots a_n)\)，用一次多项式加法和一次多项式乘法可以 \(O(n\log n)\) 做到。

分治 \(O(\log n)\) 层，每层 \(O(n\log n)\) 合并。所以计算重链链顶多项式的复杂度是 \(O(nlog^2n)\) 的。（这里的 \(n\) 是所在重链轻子树大小之和）

所以一个结点在作为轻儿子时会贡献 \(O(log^2)\) 的复杂度，每个结点贡献 \(O(\log n)\) 次，总复杂度 \(O(n\log^3 n)\)。