何も決まってないです。(path上の最大重みを求めるの一般的なテク)

はじめに

この記事はCompetitive Programming Advent Calendar 2015 - Adventarの7日目の記事です。
内容は決まってません。

内容

あなたは道を歩いていると、明後日がadvent calendarの自分の担当日であることに気づきました。そこでこの前あったICPCつくば大会(ACM-ICPC アジアつくば大会 2015 - sigma425のブログ)に出た問題に関する話題にしようと思いました。

～二日後～
担当日になりました。あなたはゆるゆりが最高だったこと以外に進捗を生んでいません。さっきの話題に関する論文を読みます。絶対間に合わねえ。うわあ、何だここ、え、これ自明か?・・・うーん・・・あ、そうだ、ここ記事にしちゃおう。

内容

根付き森があります.各頂点vには値x[v]が定まっています.クエリがいっぱい来ます.クエリは2種類あります.

LINK(x,y) : x,yが与えられて,xをyの親にする(yとしては現時点で親を持たないものしか来ない)
EVAL(v) : vが与えられて,min{x[u]|uからvへのpathがある} を求める
LINKにあるyの条件から,クエリがいくら来ても根付き森のままです.

例:次の図を見て.

これが初期状態です.まだ辺は一つもありません.丸の中の数字が頂点番号です.右下の緑色の数字がx[i]を表しています.
順にクエリを投げていきます.
LINK(4,7)
LINK(2,5)
LINK(0,2)
EVAL(7) = 1
EVAL(3) = 8
EVAL(5) = 7

LINK(2,6)
LINK(1,3)
LINK(1,4)
EVAL(4) = 1
EVAL(3) = 3
EVAL(6) = 7

LINK(0,1)
LINK(5,8)
EVAL(1) = 3
EVAL(3) = 3

最後の2つのLINKしてもEVALの結果が変わらないような悪い例になってて悲しい.でもまあこんな感じです.「pathがある」といっても根付き森なんだから,まあつまり先祖ってことです(つまり,今vが属している根付き木の根をrとして,rからvに下って行く途中の頂点uの中で最も小さいx[u]を返せばいいですね.)

解法

このことから,EVALクエリごとに,vの親を根に達するまで辿っていき,その中のx[]の最小値を求めることでEVALに答えられます.これは,最悪O(N*クエリ数)かかります(0→1→2→・・・→N-1のように長いpathみたいな例を考えるとわかる).これはちょっとだいぶかなりやばく遅いのでなんとかします.

ところで

UnionFindって知ってますか?僕は知ってます(ごめんなさい,初心者向けにしようと思ったんですがここまで解説する暇がありませんでした,蟻本を読もう!!)

つづき

UnionFindはvが属してる木の根を爆速で求める(find(v))ものでしたが,似たようにしてEVALクエリにも答えられないでしょうか?
ここで,各頂点についてmnを定義します.これはどういうものかというと,「UnionFindで縮約してる方のグラフ(以下UF森という.)上で,min{mn[u]|uからvへのpathがある}を求めると,それが元のEVAL(v)の値と一致している」というものです(これを以下†と書きます).いや定義になってないやんけ,はいそうですね,次に与えるアルゴリズムによりmnは変化していきますが,その時今言った条件†を保ったままだということを示します.
mn[v]の初期値はx[v]そのものです.

int find(int v){
	if(par[v]==v) return v;
	int r=find(par[v]);
	mn[v]=min(mn[v],mn[par[v]]);
	par[v]=r;
}
int EVAL(int v){
	find(v);
	return mn[v];
}
void LINK(int x,int y){
	par[y]=x;
}

証明の概略:
まず初期状態では求めたいものと式自体が一致するので†は成立します.
†が成立してる状態でLINKが来たとしましょう.これでも†が成立するのはなんとなくわかると思います.
くっつけられる方の木をA,くっつく方の木をBとします.Aの根をr,Bの根がくっつくAの頂点をxとおきます.
†に関して,Aには変更はなく,BのEVALはmin(これまでの,rからxのpath上でのxの最小)みたいになって,仮定から†は成立し続けます.
今度はEVALが来たとしましょう.
一般にunionfindのfindは次の図のようなつなぎ変えをします.

↓find(3)

三角形はなんか(部分)木です.
この図において,例えば頂点2の下にある部分木内の頂点xを考えます.この部分木の根をrとし,rからxへのpath上の頂点をr=v0,v1...vk=xとします.†から,今EVAL(v)=min{mn[0],mn[1],mn[2],mn[v0],..mn[vk]}です.

findでつなぎかえたあとの方のグラフについて,EVAL(v)={mn[0],mn[2],mn[v0],...mn[vk]}です.ということは縮約後のグラフでmn[2]=min(mn[1],mn[2])にすればよさそうですね.(mn[0]の方をこう設定するのはダメです.mnの定義を考えてください.)

つまり一般には,根につなぎかえられた頂点vに対して,「縮約前のvから根へのpath上のmnの最小値」を新たにmn[v]に設定すればよいです.(全頂点に対して†が保たれます)
オーダーの話ですが,vを根から順に見ていくと,見るべきpathというのは一頂点ずつ増えていきます.つまり上から再帰的にやっていくとはやいオーダーで(つまりunionfindと同じオーダーで)EVALすることができます.

実際にはmn[0]ともminをとっておいたほうが良いです.上のコードはそうなってます.(こうしても問題はなく,こうするとEVALがfindしたあとmnを見るだけで良くなる)
上の図の色付きの丸を見ると,どの頂点に対しても,vから根へのpathで通る丸の色の集合が一致してるのがわかるし,更新の仕方も理解できると思います.

おわりに

どうでしょうか,普段なにげなく使ってるunionfindが割と強い性質を持っているので自分は結構びっくりしました.でも言われたら簡単な話だと思います.この記事ではminをとりましたが,使った条件は結合法則だけなので,min,max,和,gcdなどなど色んな物が考えられます.これはほんとに一般的なテクなのでぜひ覚えておきましょう.

えっと,そんなん知っとるわという人,お前dominator treeの記事書くって言っとったやんけという人,すみません.12月中にdominator treeの記事を書きます!! その時にこのテクを使います.しばしお待ちを・・・.

明日はdata9824さんの「Web系ソフトウェアエンジニア学習コースへの競技プログラミングの導入事例」です.月刊競プロは役に立つ・・・のか!?楽しみです.