問題
辺に距離の付いた無向グラフがある。このうち、K個の頂点で祭が開かれている。
グラフと祭の頂点が与えられる。Q個の質問に答えよ。
- 質問 (s, t) : s から t へのパスで、最も祭の頂点に近づくときの距離を最大化し、その距離を出力せよ
解法
想定解では
- 祭の頂点を始点として、多始点 Dijkstra 法で各頂点の距離 dist(v) を求める
- 頂点の重みを dist(v) とする。辺 (u, v) について、重み min(dist(u), dist(v)) が大きい物だけで s-t パスが存在すればよいので、大きい物から繋いで全域木を作る。
- 次のいずれかで解くと実行時間に間に合う
- 全域木から LCA をつくり、s-t パス上の最大のdist(v) が答え。 クエリ毎O(log N)
- 部分永続 Union Find Tree で全域木を作り、s-t がつながった時間を二分法で求める。その時につなげた辺の重みが答え。クエリ毎O((log N)^2)
- 並列二分探索で Union Find Tree 上で s-t が繋がる時間を求める。全てのクエリを同時に解いて O( (Q + N a(N) ) log N)
解説のスライドの解法で計算量が速いのがクエリ毎O(log log N)。
これは元の全域木ではなく、パスを圧縮しない Union Find Tree で全域木を作り、この全域木から LCA を求める。Union Find Tree の高さは O(log N) で LCAのクエリは O(log 高さ) なので O(log log N)。
