题解：CF1781G Diverse Coloring

鬼题。

我们猜测答案是 $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$ 所以必然有解。据此不难构造。