ダイクストラ法で、各頂点からお祭りが開催される頂点への最短距離を求めておく。次に、空のグラフからスタートして、が大きい頂点から順に与えられたグラフを復元していく。このとき、がつながった瞬間のの値が、パスのお祭りからの最長距離である。構築の際に部分永続Union-Findを使っておけば、クエリに対してはがいつつながったかを二分探索で求められる。
最初、Dijkstra → Kruskal → ダブリングLCAの拡張っぽいやつでなんとかなるかもなどと妄想していたらそれが想定解だったらしい。実際には、Kruskalの正当性について考えているあいだに部分永続Union-Findでいけそうと思ったため、そちらを実装した。1 想定解のほうもそのうちやりたい。
ところで、多始点の場合、ダイクストラ法のキューのサイズはが上限ではないことに気づいた。始点の数をとするとき、あれば安全なはず。始点の数が不確定な時はで良さそう。
drkenさんのリストに載っていたから手を付けたので、純粋に思いついたというわけではない。 ↩︎
