JOI '09 春合宿４：１- Distribution 冊子の配布
問題
https://www.ioi-jp.org/camp/2009/2009-sp-tasks/2009-sp_tr-day4_23.pdf
解法
根から頂点 i までのやる気度の合計を costSum_i とする．min(n, m) 回ある頂点を選び，その頂点の costSum を足したものが答えとなる．
ここで，頂点 k を選んだ時，他の頂点の costSum がどう変化するか考える．頂点 k が選ばれたとき，頂点 i と頂点 k の共通するパスの部分のやる気度の合計が costSum_i から引かれることになる（costSum_k は当然 0 になる）．この更新を愚直にしてしまうと，costSum から重複してやる気度を引いてしまうケースが出てくるため，各頂点についてどれだけやる気度が引かれたかをメモしておく．そうすることで，既にやる気度を引かれた区間について重複して引かれる心配が無くなる．更新した後の costSum を降順にソートし，また新しい頂点 k を選ぶ処理をすればよい．O(MN + MNlogN)．
解答
重複してやる気度を引いてしまうケースを考えていなかった．
