HBC19914[CQOI2009]叶子的染色题解

云中君算法基础篇 2023-11-16 07:32:02 40 0

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点着以黑色或白色，你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点，对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色，给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。

给一棵m个结点的无根树，你可以选择一个度数大于1的结点作为根，然后给一些结点（根、内部结点和叶子均可）着以黑色或白色。你的着色方案应该保证根结点到每个叶子的简单路径上都至少包含一个有色结点（哪怕是这个叶子本身）。对于每个叶结点u，定义c[u]为从根结点从U的简单路径上最后一个有色结点的颜色。给出每个c[u]的值，设计着色方案，使得着色结点的个数尽量少。