CodeForces 1118F2. Tree Cutting (Hard Version)

题目简述：给定$n \leq 3 \times 10^5$个节点的树，其中一部分节点被染色，一共有$k$种不同的颜色。求将树划分成 $k$ 个不相交的部分的方案数，使得每个部分中除了未染色的节点以外的所有节点颜色相同，答案模$998244353$（质数）。

解：code

Step 1. 缩点

Step 2. 动态规划

我们在缩点之后，只需要解决转化后的问题。

设$f[x][s]$表示以$x$为根的子树有多少种划分方式，使得$x$所在的部分【未包含$s=0$ / 包含$s=1$】一个被标记的节点。于是答案为$f[r][1]$，其中$r$是根节点。

1. 若$x$未被标记，则

1.1. 若$x$所在部分未包含被标记的节点，则对每个$x$的儿子节点$y$，若$y$所在部分包含了被标记的节点，则必然不与$x$在同一部分；若$y$所在部分未包含被标记节点，则必然与$x$在同一部分，因此有$f[y][0]+f[y][1]$种可能。由乘法原理，有

$$ f[x][0] = \prod_{y \in \text{son}(x)} (f[y][0]+f[y][1]). $$

1.2. 若$x$所在部分包含被标记的节点，则枚举$x$的儿子节点$y$，其所在部分包含被标记节点，有$f[y][1]$种可能；对其他儿子节点$z \neq y$，若$z$所在部分包含了被标记的节点，则必然不与$x$在同一部分；若$z$所在部分未包含被标记节点，则必然与$x$在同一部分，因此有$f[z][0]+f[z][1]$种可能。由乘法原理和加法原理，有

$$ f[x][1] = \sum_{y \in \text{son}(x)} f[y][1] \prod_{y \neq z \in \text{son}(x)} (f[z][0]+f[z][1]). $$

2. 若$x$被标记，则

2.1. $x$所在部分不可能未包含被标记节点，即

$$ f[x][0] = 0, $$

2.2. 若$x$所在部分包含被标记的节点，则对每个$x$的儿子节点$y$，若$y$所在部分包含了被标记的节点，则必然不与$x$在同一部分；若$y$所在部分未包含被标记节点，则必然与$x$在同一部分，因此有$f[y][0]+f[y][1]$种可能。（这与1.1.的讨论相同）由乘法原理，有

$$ f[x][1] = \prod_{y \in \text{son}(x)} (f[y][0]+f[y][1]). $$

总时间复杂度为$O(n)$。

巴特西

CodeForces 1118F2. Tree Cutting (Hard Version)

Step 1. 缩点

Step 2. 动态规划

最新文章

热门文章