問題 解法1 クエリ平方分割 もしクエリが1つしかない場合、以下の方法で求められる。 森の連結成分ごとに適当に根を取り、DFSで各頂点の親を求めると、各クエリについて、 と の親のいずれかが候補になるため、親を とすると、辺 と辺 が存在するかを、辺集…

問題 解法 現在時刻を とすると、ダイクストラ法で各遷移において となる最小の を求めることができれば良いので線形合同式が解ければ良い。 しかしこれを解くのは意外と難しく、法が素数ではないときに逆元がないが が解を持つという場合がある。（例： に…

問題のリンク 解法1（LowLink） LowLinkのアルゴリズムをベースに少し改良を行い実装する。 ところで、LowLinkを改良するアルゴリズムを考えるときには、（実際にはまとめて行っているが）まずDFS Treeをとり、そのDFS Tree上にある辺かそうでない辺（後退辺…