[Matrix-Tree][插值][容斥][prufer序列][DP]夕张的改造

2024-03-12 12:12:38

Statement

树有两种常用的计数工具：Matrix-Tree 定理和 prufer 序列
标解的做法是 Matrix-Tree 矩阵树定理
易得我们要求的就是有多少棵树和原树的不同的边数 \(\le k\)
考虑矩阵树定理的本质：求所有生成树的边权积之和
于是我们考虑一个完全图，把每条边定权，如果这条边在原树上则权值为 \(1\)，否则为 \(x\)
这样对这个图求一遍 Matrix-Tree 之后得到的答案是一个多项式，\(x^i\) 表示不同的边数恰好为 \(i\) 的生成树个数
这样有一个问题：高斯消元求行列式的复杂度为 \(O(n^3)\)，多项式运算的复杂度为 \(O(n^2)\)~~（用 FFT 可能在常数上还比不过平方）~~，总复杂度 \(O(n^5)\)，不太能过
不过最终答案的多项式次数只有 \(n-1\)，我们考虑插值，把每条边的权值改为 \(n\) 个点值，可以取 \(1\) 到 \(n\)
这样高斯消元时，多项式乘法就变成了点乘，可以 \(O(n)\) 计算，复杂度为 \(O(n^4)\)，可以通过此题

如果你做过「WC2019」数树的话，你会发现这是数树的 \(op=1\) 弱化版
考虑如何计算不同的边数恰好为 \(k\) 的方案数
考虑容斥：
\[\sum_{m=0}^{k}(-1)^{k-m}\binom{n-1-m}{k-m}f(m)\]
\(f(m)\) 表示选出一个大小为 \(n-1-m\) 的边集并让它们和原树相同的方案数，\(\binom{n-1-m}{k-m}\) 的含义是枚举这个 \(f(m)\) 所在的大小为 \(k\) 的集合是哪个
显然 \(f(m)\) 也可以看成原树删掉 \(m\) 条边分成 \(m\) 个连通块之后再连 \(m\) 条边组成一个新树的方案数
可以使用 prufer 序列或 Matrix-Tree 矩阵树定理推出一个结论：
\(n=\sum_{i=1}^ma_i\)，\(m\) 个连通块，大小分别为 \(a_{1\dots m}\)，再加 \(m-1\) 条边形成树的方案数为：
\[n^{m-2}\prod_{i=1}^ma_i\]
显然对于所有把原树划分成 \(m\) 个连通块的方案，\(n^{m-2}\) 是确定的，于是我们只需关注 \(\prod_{i=1}^ma_i\)
于是对这个东西进行树形 DP：\(f[u][i][j]\) 表示 \(u\) 的子树选出了 \(i\) 个连通块，其中根所在的连通块大小为 \(j\)，除根所在之外的所有连通块大小积之和
大力转移，还是 \(O(n^4)\)
和数树那题一样，如果利用 \(\prod_{i=1}^ma_i\) 的组合意义（每个连通块里选一个点的方案数）可以设计一个新的状态 \(f[u][i][0/1]\) 表示 \(u\) 的子树选出了 \(i\) 个连通块，第三维表示是否已经选出了一个点，这样的复杂度 \(O(n^2)\)