题解：P14991 战略游戏

Rain_chr · 2026-01-20 09:02:19 · 题解

感觉和 P14510 夜里亦始终想念着你 miss 是很像的题，都是对于复杂的判定进行计数，非常喜欢这种类型的计数题。

场上想到了一个很简单的做法，但是看着高水平选手都没过，我也知道这个做法大概率是错的，但是死活没看出来假在哪，晚上看题解才发现确实是有问题的。

首先考虑判定，这个是简单的：

设 c_x 表示新树中 x 的颜色，a_x 为新树中 x 当前的颜色，一开始有 a_x=0。

首先根据题意，必然有 y=c_x 在 x 的子树里。

从上到下考虑新树中的每一个点，若已经有 a_x=c_x，那么不需要更改；

否则，拉出 y=c_x，将 y\to x 路径上的所有点全部染成 a_i=y，并且将边的流量 -1。

如果操作过程中流量被减成负数了，那么一定不合法，否则一定合法。

对着判定，我们考虑如何计数。

不难想到每个点会有一个颜色序列，表示这个点过程中的颜色变化。

那么这个队列每次做的就是，任意归并所有儿子处的队列，选择在开头加入或者不加入 x，并且在上传的时候考虑删除或者不删除末尾的颜色。

这三个操作应该是好理解的，任意归并是因为儿子处颜色传上来没有顺序，在开头加入或者不加入 x 意味着 x 是直接被儿子覆盖掉还是先将自己的颜色传上去，删除或者不删除意味着队尾这个颜色是传上去还是在 x 这个位置停留。

所以我们先应该求出上传颜色序列任意归并长度为 k 的方案数 g_k，其中 k\le w_x+1，然后再考虑 x 加入和末尾删除的事情。

如果直接对着这个 DP 是非常好 DP 的，也是我场上的做法，但是我想不明白是哪里有问题，看了题解才发现：

事实上，我们需要定义三种颜色序列（其实也可以是两种，不过三种更严谨）

点颜色序列：每个点在染色过程中的颜色变化，并且队首一定是 x，队尾一定是 c_x。为了方便，我们约定将 x 去掉。

上传点颜色序列：每个点上传到父亲的颜色所形成的队列。

边颜色序列：x 处的边颜色序列定义为经过 (x,p_x) 这条边的颜色序列。

这三个序列事实上是有区别的，我们来说明一下这三种序列的生成方式：

点颜色序列通过任意归并所有儿子处的边颜色序列生成。

上传点颜色序列：通过在点颜色序列的基础上，队首加入或者不加入 x ，队尾颜色删除或者不删除生成。

边颜色序列：通过扩展上传点颜色序列生成，扩展定义为将一种颜色复制任意次并插回原来的位置。

考虑点/上传点颜色序列与边颜色序列最大的不同在于什么：

点颜色序列一定不会有相邻相同的颜色，但是边颜色序列可能有，因为可能重复染色。

回过头来看我在场上的方法，问题在于：点和边的颜色序列是不一样的，上述做法把点边颜色序列混为一谈了。

此时我们可以断言：任意一种 1 上传颜色序列为空的方案双射到一种染色方案。

这应该是可以理解的，因为根据判定，如果存在一个点颜色序列不同，那么到根链最终染色一定不同，同时一种染色方案一定也对应一种点颜色序列方案。

明确定义之后，我们再来考虑对于点染色序列计数，显然设 f_{i,j} 表示点 i 处的上传点颜色序列长度为 j。

我们先归并儿子得到点颜色序列长度为 k 的方案 g_k，再通过点颜色序列生成上传点颜色序列。

设每个儿子的上传点颜色序列长度为 a_i，并且边颜色序列是在其基础上扩展 b_i 次生成的，那么最终 x 的点颜色序列长度即为：

由于归并之后不能有相邻位置同色，所以我们考虑容斥。注意这里容斥不能是容斥全局，而必须是对于每个儿子单独容斥！

设 t_i 表示钦定第 i 个儿子有 t_i 次扩展最终处在相邻的位置，那么一个儿子的方案数即为：

最后还要任意归并，所以总方案数为：

在 DP 的过程中记录一下 a_i+b_i 之和（也就是序列长度）和 a_i+b_i-t_i 之和（也就是容斥系数），可以做到 O(nk^5)。

不过注意特判 a_i=0 的情况，此时因为不能扩展所以直接乘上这种方案即可。

优化是容易的，我们提前用 O(k^3) 的时间预处理每个 a,b,t 对对于 a_i+b_i，a_i+b_i-t_i 的贡献系数，直接做二维卷积即为 O(nk^4)。

当然，最后如果上个 NTT 优化二维卷积可以变成 k^3+k^2\log k，但是我猜跑不过 k^4。

最后根据点颜色序列生成上传点颜色序列是简单的，不过注意特判长度为点颜色序列为空的情况。