C 問題「山登り(Mountain Climbing)」解説

部分点（1 点）解法

$1$ 点分の部分点では $N \leqq 1000$ が成立する. $Q \leqq N-1$が成り立つことに気をつけよ．

クエリ毎に，愚直に全ての葉への最短経路を探索すれば，時間計算量 $O(NQ)$ となり間に合う．

満点解法

まず，辺が通行禁止になっていない状態で，適当に探索を行い，$葉番号とその葉の(最短)距離のペア$ をノードにして平衡二分木に格納しておく． このとき，平衡二分木内で距離が小さいもの順にソートされるようにしておく．

ある辺を通行禁止にするときに以下のことを行う．

• その辺によって分断される部分木(根が含まれない方)の頂点はもう辿ることは無いため，それら全ての頂点を削除する．
• 葉の削除を行うときは，それを平衡二分木から削除しておく．
• 削除された頂点を含む辺通行禁止クエリが来ても無視する．

この操作を行った後に，平衡二分木から最小ノードを取り出し，その距離を出力すればよい．

最初に全ての葉を平衡二分木に追加する操作の時間計算量は $O(N log N)$である．

また，各頂点は高々 $1$ 回しか削除されず，頂点削除の時間計算量は節 $O(1)$ or 葉 $O(log N)$ なので，クエリ処理のならし時間計算量は $O(Q + N log N)$ である．

よって全体の計算量は， $Q ≦ N$ であることを考慮すれば， $O(N log N)$ と表せる．