CF2112E题解

PenguinJ · 2025-06-24 10:33:42 · 题解

题意

给一颗有根树染色，根节点为绿色，其他节点可染为绿色，黄色或蓝色。一种染色方案是好的需满足任意一对绿色点和蓝色点之间没有黄色点，且任意一对绿色点和黄色点之间没有蓝色点。求一棵恰好有 m 种好的染色方案的树的最少节点数，若不存满足的树则输出-1。

思路

考虑1棵确定的有 n 个点的树有多少种好的染色方案。 设 f[u] 表示以 u 为根的子树中好的染色方案数。发现，如果某一个点填了蓝色（黄色），那么以该点为根的子树中也都只能填蓝色（黄色）。所以就有：

考虑从 m 反推，分解 m 的质因子并递归求解即可。