SRM644 div.2 1000 TreeCutting

問題*1

• V頂点の木が与えられる
• 各頂点vにはnum[v]が与えられる(正の数もしくは-1)
• いくつかの枝を切断して以下のような木のみが存在する森をつくることはできるか
  • 正のnumをもつ頂点はただ1つのみ
  • その正の数字は木の頂点数と一致する
• 作れる場合はPOSSIBLE、作れない場合はIMPOSSIBLEという文字列を返す

解法

ここで説明する解法のアイデアは、「根付き木で葉から順番にnumを足していって、0になったとき枝を切断する」というものである

• まず、適当な頂点を根(ここでは頂点0)とした根付き木を作る
  • また、各num[i]について、num[i] > 0のときは、num[i]--しておく
• 頂点vからDFSし、返り値を合計した値とnum[v]の値の和をDFSの値として返す
  • ただし、以下の場合はIMPOSSIBLEとして、INFを返す
    • 子をDFSした値とnum[v]のうち、0以上のものが2個以上ある場合
    • 子をDFSした値とnum[v]のうち、0以上のものが1個で、かつ、返り値とnum[v]の合計が0より小さくなる場合はIMPOSSIBLEとしてDFSの返り値をINFにする
• 0からDFSした値が0のときはPOSSIBLEで、それ以外のときはIMPOSSIBLEである

計算量

O(|V|)

コード

感想

枝を全部切っていって、シミュレーションする解法が出来そうだけど実装厳しそうだなあと思っていたところ、この解法をid:Tawaraさんから聞いて感動したので書いた*2

最後に

一昨日は体調を崩して、昨日は眠かったから書けなかった

*1:UnratedになったからかProblem Archiveに問題がなかったが、Arenaにはあった

*2:まあまだ証明ができていないけれど、反例が思いつかないし、Run System Testも通ったのでとりあえずはOK