给你一棵 个点的无根树,有 个点初始为黑色,其余点初始为灰色,你可以在一开始将一些灰色点染成白色。染完后,现在进行如下操作,直到树上不存在灰色点。
每一轮对所有灰色点同时进行如下操作:
- 检查与该灰色点 直接相连的点有没有黑色或白色点,如果没有,则 保持灰色。
- 如果与 直接相连的点有白色点,则 变为白色。
- 如果与 直接相连的点有黑色点,则 变为黑色。
这个顺序说明同时与白色和黑色相邻时会被染成白色。
注意此处对所有灰色点同时进行操作,也就是说在这一轮被染上颜色的点不能作为其它点改变颜色的根据。
现在求一开始最少染几个点为白色,可以使树最终黑色点不超过 个。