Codeforces Round #660 (Div. 2) - D. Captain Flint and Treasure
解説
制約に森と書いています。ということでトポロジカル順にみていきましょう。
現在持っている値が正なら後に足していった方が得なのでつなげます。
負ならこれを足すと損なので、後回しにします。
復元はこの順番の管理をみればいいのでトポロジカルソートをすればいいです。
計算量はです。
制約に森と書いています。ということでトポロジカル順にみていきましょう。
現在持っている値が正なら後に足していった方が得なのでつなげます。
負ならこれを足すと損なので、後回しにします。
復元はこの順番の管理をみればいいのでトポロジカルソートをすればいいです。
計算量はです。