题解：CF1781G Diverse Coloring

happybob · 2025-11-05 20:37:06 · 题解

鬼题。

我们猜测答案是 n \bmod 2，但是样例都过不去。这时不知道为什么有人能注意到样例是唯一的反例。

我们尝试归纳说明并给出构造。n\leq 8 时，通过爆搜，不难说明必有解。

对于一般的 n，只要我们能将二叉树划分为若干大小为 2 或 3 的连通块，则自然能构造出 n \bmod 2，原因是 2\mid n 时大小为 3 的连通块有偶数个可以直接构造，2 \nmid n 时有奇数个自然能取到下界。

我们接下来说明，对于 n>8，总存在将树划分成若干大小为 2 或 3 的连通块的方法。

若存在点 u，满足其两个儿子都是叶子，则划分出了一个大小为 3 的连通块。另一方面，若存在点 u 满足其只有一个儿子且其为叶子，则划分出了一个大小为 2 的连通块。这都可以归纳进子问题。我们声称上述情况之一必然成立。据此，我们也进行归纳。2 \leq n \leq 3 时显然。n>3 时，任取一个叶子，考虑其父亲，则当且仅当父亲有另一个儿子且儿子子树至少为 2 时这个点不能选为构造。而根据归纳假设这个儿子子树至少为 2 所以必然有解。据此不难构造。