AOJ2636 Distance Sum

ブログ書くのめんどくさい.
問題文はとても読みやすいので読んでください.

解説:

普通に順番に1からNまで追加してシミュレーションします.

まず, i番目を追加した時, i-1番目の時和を最小化する頂点(vとする)とのパス上に新しい候補点がありそう.

vからそっち方向に辺を1つ移動した点に変えた時のcostの変化を考えると, それよりこっち側の部分木の頂点数と向こう側の頂点数(今まで追加された分)(それぞれnum1, num2とする)とcost * (num2 - num1 + 1)減る(1は新しい頂点の分) costは全体にかかるので難しい計算はしなくてよい. i-1番目まででの最小性より num2 - num1 <= 0になっている. num1 + num2 = i - 1 また, 今までの点かlcaっぽいところでnum2 - num1が減少し, 1回変化すると最小となる.

この辺の操作は行き掛け順で管理してsegtreeとかBITとかでサポートするとなんとかなる. (こっちは慣れっぽい)