CF1481F AB Tree

题目大意

给定一棵 $n$ 个节点的树，根为 $1$ ，每个节点会分配到一个字符 a 或 b。
要求整棵树中字符 a 的数量为 $x$ ，字符 b 的数量为 $n-x$ 。
定义节点 $v$ 上的字符串：

• 若 $v$ 是根节点，则 $v$ 的上的字符串为根节点分配到的字符。
• 否则，$v$ 上的字符串为父节点上的字符串的末尾加上 $v$ 分配到的字符。

请为每个节点分配字符，在满足字符 a ，b 数量要求的前提下，使得所有节点上的字符串的种类最少。

solution

神仙构造
设最大深度为$d$，容易发现答案的下界肯定为$d$，具体只要每一层都染成一个颜色就行了，我们再分析一下上界，根据手玩和猜测，可以发现上界应该就是$d+1$的，考虑答案是$d+1$时应该是个什么情况，首先肯定同层非叶结点颜色必须相同，并且只有一层的部分叶子结点颜色和非叶子颜色不同，由于非叶结点至少有一个儿子，所以一层的非叶结点数一定是$\le \lfloor \frac{m}{2}\rfloor$的（$m$表示是剩下的未染色结点数），也就是说一定有办法使得每层的非叶结点都相同，然后叶子结点就先考虑染成与非叶子相同的颜色，如果不够就染完再涂别的
不难发现这样做最多有一层的叶子颜色不同，所以答案上界就是$n+1$
剩下的就用背包来判断即可，不同层结点数种类最多只有$O(\sqrt{n})$种，直接二进制优化多重背包即可，时间复杂度$O(\sqrt{n})$
代码莫得