木上のパスが含む辺の中で、その重みの最大値(最小値)を対数時間で求めるライブラリです。よく知られたダブリングというテクニックを使っています。ダブリングについてはここでは書きませんが、parmax[k][u] というのは、頂点 $u$ から根に向かってパスを $2…

二重頂点連結成分分解木のライブラリです。誰も使わないと思います。これの続きです。任意の無向グラフから二重頂点連結成分と関節点を頂点とする木を構築できます。それをやってくれるライブラリです。 //e2i[edge] -> index of the edge //tree index : [0…

二重頂点連結成分分解の実装です。追記：誤りがあったので大幅に変更しました。名前が似ていますが、二重辺連結成分分解とは異なります。そちらについてはこの記事をご覧ください。任意の無向グラフを、その部分グラフであって「その部分グラフにおける関節…

二重辺連結成分分解の実装です。二重頂点連結成分分解についてはこちらの記事をご覧ください。無向グラフ上で、橋が存在しない部分グラフを一つの頂点につぶすと、橋を辺とする木ができます。以下は、それをそのまま実装しています。 struct LowLink { set<pair<int, int>> </pair<int,>…