ABC294 G - Distance Queries on a Tree (600)

解説の解法

オイラーツアーで解く

クエリを配列の連続する範囲に対するクエリにできるのでセグ木とかが使えるようになる

根から見ていって各辺の入る順番と出る順番を記録する

辺のコストを和を取れるセグ木に乗せる

コストは上に戻るタイミングでは反転して入れる

点の深さとインデックスを最小値を取れるセグ木に乗せる

各クエリで以下を行う

コストの変更の場合、対象の辺のコストを和のセグ木上で変更

最短経路を求める場合、LCAを求め、根から各辺のコストを求め、そこからLCAへのコストの2倍を引く