AtCoder Regular Contest 108 C - Keep Graph Connected
メモ
連結グラフについて、何か性質を満たすものを考えろという問題の時に
全域木を取って、それについて考えるのは頻出
感覚的には、連結グラフにおいて、辺が多くあることが何かしら問題において選択肢を増やすことにつながっていて、辺が多ければ多いほどその問題が解ける確率が上がりそうに見える、実際はどのような連結グラフでも解ける問題の時に使う事が多い
例えばこれとかもそう
技術室奥プログラミングコンテストとかにもそういう問題があった気がするが見つけられなかった。
今回は木の上で、根の色を決めるとそこから広がるように埋めていく事が出来たが
考察に詰まってしまった
葉から決めようとしてうまくいかなかった。
根から決めると上手くいく理由
まずすべての辺の色が異なる場合、根を適当に決め、すべての辺と同じ数字は
下でそろえればいいので出来る
辺の色が同じものがある場合、実は上にくっつくのでらく
根から決めると、今選ぶ選択に影響するものが、直前の選択だけになり今までの選択と独立になるため決めやすかったが
葉から埋めていくと、今までの選択すべてを満たすように（子の条件すべてを満たすように）しないといけないという点で複雑にしてしまっていたかもしれない
