题解：CF2040D Non Prime Tree

· · 题解

题目链接

CF2040D Non Prime Tree

解题思路

挺好的题啊，赛时 10min 胡了个正解，但是 ans 数组打成 a 虚空调试 15min，怎么回事呢。

解法一

赛时做法。

可以看出当前无论怎么填，只要状态合法，那么一定有至少一种方案可以将整棵树都被填满，但是我不会证明啊。

于是我们就有一个暴力做法，那就是直接钦定根节点的值为 1，然后直接暴力枚举最早的子节点的值使其合法，就行了。

感觉时间复杂度是 O(n^2)？我不会证啊。

发现上述算法的瓶颈只在于暴力枚举，我们又注意到 1 \sim n 的合数密度是很大的，因此直接从根到叶子结点依次随机出可行的权值就行了。

时间复杂度近似 O(n) 吧，我不会证啊。

解法二

应该是正经做法吧。

发现相邻节点结点填差为 1 时总是最优的。

尽量多构造这种东西，然后就下来形如构造 4,6,8 \dots 的差的形式即可。

容易证明上述构造的权值可以 \le 2n。

其他题解应该讲的挺清晰了吧，在此不再叙述代码细节。

时间复杂度 O(n)。

参考代码

解法一的代码，觉得有问题的可以来 hack。