CF1481F AB Tree

The main idea of the topic

Given a tree $n$ Tree of nodes , Root is $1$ , Each node is assigned a character a or b.
Require characters in the whole tree a The quantity of is $x$ , character b The quantity of is $n-x$ .
Define the node $v$ String on ：

• if $v$ Root node , be $v$ The string on is the character assigned to the root node .
• otherwise ,$v$ The string on is the end of the string on the parent node plus $v$ Characters assigned to .

Please assign characters to each node , After meeting the characters a ,b Quantity requirements , Minimize the types of strings on all nodes .

solution

Fairy structure
Let the maximum depth be $d$, It is easy to find that the lower bound of the answer must be $d$, As long as each layer is dyed with one color , Let's analyze the upper bound again , Based on hand play and guessing , It can be found that the upper bound should be $d+1$ Of , Consider that the answer is $d+1$ What should be the situation , First, make sure that the color of non leaf nodes in the same layer must be the same , And only the color of some leaf nodes in one layer is different from that of non leaf nodes , Because non leaf nodes have at least one son , So the number of non leaf nodes in a layer must be $\le \lfloor \frac{m}{2}\rfloor$ Of （$m$ Denotes the number of undyed knots remaining ）, That is to say, there must be a way to make the non leaf nodes of each layer the same , Then the leaf nodes should be dyed to the same color as the non leaf nodes , If it's not enough, dye it and paint something else
It is not difficult to find that at most one layer of leaves is different in color , So the upper bound of the answer is $n+1$
The rest can be judged by the backpack , The maximum number of different stratification points is $O(\sqrt{n})$ Kind of , Direct binary optimization of multiple knapsacks , Time complexity $O(\sqrt{n})$
Code mo de