给一棵有 m 个节点的无根树,你可以选择一个度数大于 1 的节点作为根,然后给一些节点着以黑色或白色,你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身,对于每个叶子节点 u,定义 cu 为从根节点到 u 的简单路径上最后一个有色节点的颜色,给出每个 cu 的值,设计着色方案使得着色节点的个数尽量少。
原题来自:CQOI 2009 给一棵有 m 个节点的无根树,你可以选择一个度数大于 1 的节点作为根,然后给一些节点(根、内部节点、叶子均可)着以黑色或白色。你的着色方案应保证根节点到各叶子节点的简单路径上都包含一个有色节点,哪怕是叶子本身。 对于每个叶子节点 u,定义 cu 为从根节点到 u 的简单路径上最后一个有色节点的颜色。给出每个 cu 的值,设计着色方案使得着色节点的个数尽量少。
(图片来源网络,侵删)