ABC144-F Fork in the Road

道を消さないときの期待値は頂点番号$ iの大きい方から計算していけば求まる。

道を消したときの期待値の最小が欲しいものなので、同じ頂点から出ている辺の中では期待値が最大の頂点への辺を消すのが最善である。よって、消さないときのDPの結果を見れば全ての頂点について消す必要がある辺が適当に定まるので、その都度DPをやり直せばよい。$ O(NM)となり解ける。