一道很有价值的容斥题

有必要记录一下今天模拟赛的 C 题。题目链接。本文同步作为“对树边容斥”一类技巧的解释及例题分析。

给定一棵 $n$ 个节点的树，你需要用 $m$ 种颜色去给每个节点染色，要求相邻点颜色不同。再给出一些关键点，一个染色方案 $c$ 的价值 $F(c)$ 为所有关键点的颜色集合的大小，求所有合法染色方案的 $F(c)^k$ 之和。对 $998244353$ 取模。$n,m\le10^5,k\le400$，关键点个数与 $n$ 同级。

容斥，即 $S=U-U\backslash S$，用无意见减去反对意见。

考虑相邻点颜色不同这个限制，如果我们只要求合法染色方案数，应该怎么做呢？从上往下考虑，答案显然是 $m(m-1)^{n-1}$。如果有一些额外的限制，使得这个公式用不了，那么我们可以考虑对边及其相邻的点进行容斥，将二者颜色不同容斥成二者之间无限制减去二者颜色相等，颜色相等的话可以缩成一个连通块一起考虑颜色，无限制则相当于断边，各自考虑。可以设 $f_u$ 表示以 $u$ 为根的子树的方案数，且暂时不考虑 $u$ 所在连通块的颜色（因为还可能继续拓展），考虑转移一个子树 $v$，则有：

$\bullet$ 断边，无意见：$f_u*mf_v\to f_u$
$\bullet$ 加入连通块，反对意见：$f_u*f_v*(-1)\to f_u$

最终 $mf_{root}$ 即为答案。

这道题有两种转化，但殊途同归。对于贡献形式为某种元素的次幂，可以考虑以下两种方式。

考虑使用斯特林数，将次幂转化成下降幂或者组合数，公式为：$x^k=\sum_{i=0}^ki!\binom{x}{i}S(k,i)$。其中 $S(k,i)$ 为第二类斯特林数，意为将 $k$ 个有标号的小球放入 $i$ 个无标号的盒子中的方案数。

那么题目即求：

那么就转化成了钦定 $i$ 种颜色必须在关键点集中各出现至少一次的方案数 $f_i$。上式中的 $\sum_c\binom{F(c)}{i}$ 可以写成 $\binom{m}{i}f_i$。则 $ans=\sum_{i=0}^ki!S(k,i)\binom{m}{i}f_i$。

考虑 $F(c)^k$ 的组合意义，我们将 $F(c)$ 中出现过的颜色都拿出来，那么其组合意义为：从这些出现过的颜色中，有顺序可重复地选出 $k$ 个颜色。那么我们枚举选完 $k$ 次之后的选出来的颜色集合，设大小为 $i$，这一步方案是 $\binom{F(c)}{i}$，考虑这个集合能被数到多少次（因为是有顺序可重复，所以一种集合会被多次数到），由于这 $i$ 个元素必须至少出现一次，那么我们考虑容斥，设这 $i$ 个颜色中有 $j$ 中颜色没有出现，剩下 $i-j$ 中颜色无限制，那么该集合会被数到 $\sum_{j=0}^i\binom{i}{j}(-1)^j(i-j)^k$(其实这个过程就相当于将 $k$ 个小球放进 $i$ 个有标号盒子中，这个式子就等于 $i!S(k,i)$。)。那么有：

那么我们用两种不同的方式将题意转化成了：求钦定 $i$ 种颜色必须在关键点集中各出现至少一次的方案数 $f_i$。

我们考虑求解所有的 $f_i,i\in[0,k]$。这需要我们在最外层枚举 $i$。

跟刚刚组合意义推导类似，我们无法记录哪些元素出现过。考虑容斥，某元素至少出现过一次的方案数，等于无限制方案数减去该元素不出现的方案数。考虑设 $g_j$ 表示钦定的 $i$ 种颜色中，容斥了 $j$ 种颜色不出现在关键点集中的方案数（可能有其他的元素未出现，但根据容斥，那些是被我们判定成无限制的一部分，所以不是恰好 $j$ 个未出现）。那么 $f_i=\sum_{j=0}^i(-1)^j\binom{i}{j}g_j$。

那么我们需要求解 $g_j$。现在的限制有：关键点集有 $j$ 种元素不能选，其他点任选，相邻点颜色要求不同。

沿用我们在初步思考时的思路。由于有关键点的存在，一个连通块的染色方案数取决于连通块中是否含有关键点，因此我们设 $t_{i,0/1}$ 表示 $i$ 所在连通块中是/否含有关键点的染色方案数。当在点 $u$ 时，考虑从 $v$ 子树的转移，仍然是分当前边的是无限制还是反对，也即考虑断边还是加入连通块。注意我们断边时，要注意给 $v$ 所在连通块分配颜色，因为我们的状态中时尚未考虑 $u$ 处的染色情况的。这一步复杂度 $O(n)$。

求出了最底层的 $g_j$ 后，我们便可以一路倒退，$O(k^2)$ 求出 $f_i$，再 $O(k^2)$ 求出我们的最终答案。其中斯特林数和组合数都是可以预处理的。总复杂度 $O(nk+k^2)$。

从这一题获得的收获很多。包括：

$\bullet$ 相邻点染色不同的容斥套路。
$\bullet$ 容斥的基本思路与原理。
$\bullet$ “值的次幂”贡献形式的组合意义套路及斯特林数将次幂转化为组合数、斯特林数的套路。
$\bullet$ 加强了对第二类斯特林数的理解。

感觉我对于容斥的理解更深了，也能更熟练地使用容斥这个工具。感谢 lrz 在这道题上对我的教导。