Codeforces Round #547 (Div. 3)G. Privatization of Roads in Treeland
問題概要
頂点の木が与えられ, この木の辺を様々な色で塗っていきたい.
ある頂点について同じ色で塗られている頂点があるとき, その頂点は悪い頂点である.
悪い頂点を 個以下にするには, 最低で何色必要か？（構築せよ. ）
制約
解法
まず, の場合を考えましょう. この時, 条件を満たすように色を塗るには何色必要でしょうか？
これは, 木の全ての頂点におけつ最大次数と一致します. 根から順番に親とつながっている辺の色以外で塗るアルゴリズムを考えれば, この妥当性がわかります.考え方的には,これが近いと思います.
一般の についても同様です. 悪い頂点は次数が多い順に割り当てていけばよいので,
番目に次数が多い頂点が悪い頂点にならないだけの色さえ確保してしまえば先ほどのアルゴリズムで条件を満たすように色を塗ることができます.
