都市を頂点、高速道路を辺とした木グラフを考えます。

DFS 等で適切に頂点番号を入れ替えることで、上りを根へ向かう方向、下りをその逆方向とすることができます。以下この処理を行った後に問題を解くことにします。

問い合わせクエリにおいて、頂点 \(x,y\) の LCA (Lowest Common Ancestor) を頂点 \(z\) とします。LCA はダブリング等により前計算 \(\mathrm{O}(N \log N)\) クエリ \(\mathrm{O}(\log N)\) で求められます。このとき、クエリで答える値は頂点 \(x\) から \(z\) の上りの所要時間の合計と頂点 \(z\) から頂点 \(y\) の下りの所要時間の合計の和です。これは以下のようなクエリを高速に処理できれば解くことができます。

• 辺を選択し、重みを変更する
• \(2\) 頂点を選択し、その間の辺の重みの総和を求める

HL 分解 (Heavy-Light Decomposition) というテクニックを用いることで、クエリをそれぞれ \(\mathrm{O}(\log N), \ \mathrm{O}(\log^2 N)\) の時間で処理することができます。よって、全体で \(\mathrm{O}(N \log N + Q \log^2 N)\) 等でこの問題を解くことができます。(LCA の求め方によっては一部改善できますがボトルネック部分は変わりません) 十分高速です。

別解として、クエリがオフラインなことを利用して重心分解を用いて解く解法があると思います。(未検証です)