7K12 blog

猫でも分かるアルゴリズム解説

ABC133 E - Virus Tree 2

f:id:tkr987:20200303155520p:plain

https://atcoder.jp/contests/abc133/submissions/10504611

今回も地頭力なさすぎて解説ACになってしまった…知識的に足りないものはないのに。

f:id:tkr987:20200303155732p:plain

根はK色で塗れる。根に隣接する頂点数をcとすると{}_{K-1}P_{c}色で塗れる。孫の頂点をcとすると親と親の親の2色引いて{}_{K-2}P_{c}色になる。よく見ると親と親の親は1頂点ずつしかないことに留意する。以下、同様に{}_{K-2}P_{c}色で塗る。親の親の子同士は実は距離が2を超えるので同じ色で良いため、何も考えなくて良い。

f:id:tkr987:20200303161221p:plain

最初に文章を読んだ時このような図を書いて悩んでいた…。

木なので綺麗な木構造でグラフを書いたほうが良い。