ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ARC083-E - Bichrome Tree

問題
提出コード
ほとんど自力で解けたのでなかなかではないかなーと思ってます!
問題の制限より、頂点の番号が大きい方から順番に見ていくと、そのとき見ている頂点は必ず木の根になっています。
なので、番号が大きい方から順番に、そこを根とする部分木がつくれるかどうかを調べていきます。
では、i番目の部分木を作成します。
キーとなるのは、ある部分木についての白、黒の総和のペアになります。
まずは、iにつながっている、その他もろもろの部分木(i以降ということになります)の、黒と白の総和のペアをすべて集めます。集めたペアは、その時点では黒と白をひっくり返すことが可能になっているので、その中でできるだけ無駄のない組み合わせ方をしたいです。交換可能なので、白<黒とします。
交換可能だとこれ以降の処理ができなくなるので、黒と白の組み合わせを決めます。 これは、以下のようにして組み合わせると、無駄が一番少なくなります。
初めに、すべてのペアについて、集めたペアそれぞれの、黒と白の差をすべて記録しておき降順でソートしておきます。次に、現時点での白の総和、黒の総和をそれぞれ出します。最後に、先ほどソートした差を順番にみていき、その差を白にプラス、黒にマイナスしてもなお白がX_i以下であるならその処理を行う、ということを繰り返していけば良いです。 この処理が全て終わった段階で、一度白<黒になるように、もし逆であれば交換をします。
次に、今決めた新しい黒と白の総和のどちらかが、X_iを満たすように、根自身の色と数を決めます。
新たな黒白のペアを作成したときの、処理の手順は3通りあります。それによって、新しい部分木についての、黒と白の総和の完成形を求めます。

  1. 黒、白ともに条件をオーバーしているとき
    もちろん作ることができないのでこの時点で答えはIMPOSSIBLEになります。

  2. 黒、白ともに条件を満たしているとき
    黒のほうが大きいと仮定しているので、根の色を黒にしてあげると、より効率がいい部分木をつくることができます。そして、黒の総和は、X_iにおきかわります。白の総和はそのままになります。

  3. 片方のみ条件を満たしているとき
    黒の総和はそのまま、白の総和が、X_iそのものになります。

そして、完成した部分木の新しい黒と白のペアを、P_iにわたします。親は、その値をもとに、同様の作業を繰り返します。
これを繰り返し、1番を根とする木まで完成させることができれば、答えはPOSSIBLEになります。