最近の公的祖先LCA【特集@AbandonZHANG】
5689 ワード
参考:「アルゴリズム芸術と情報学コンテスト」---劉汝佳ブログ:
http://blog.163.com/kevinlee_2010/blog/static/16982082020120794613496/
最近の公的祖先(LCA)問題
最近の共通祖先(Least Common Ancestors、略称LCA)は、ツリーに関する基本的な問題であり、この問題の説明は以下の通りである.
T内の任意の2つのノードuおよびvに対して、ルートツリーTが与えられる.LCA(T,u,v)というルートから最も遠いノード(あるいはuとvに最も近いノード)rを求め,rがuとvの祖先であるようにする.この質問は「質問−回答」と見なすことができる.式の問題.2つの方法でこの問題を解決することができます.1つは、まず十分な前処理を行い、質問に答えるたびに、わずかな時間で済むことです.このアルゴリズムをオンラインアルゴリズム(online algorithm)といいます.もう1つは、すべての質問を収集(読み込み)してから、すべての回答を完了するアルゴリズムです.このアルゴリズムをオフラインアルゴリズム(Offline algorithm)と言います.
最も素朴なオンラインアルゴリズム:ノードuからルートノードへの経路(すべての通過ノード)を1つのチェーンテーブルに格納し、vからルートへ歩き始めると、発見された最初のチェーンテーブルのノードが最近の共通の祖先である.明らかにこの2つのステップが最悪の場合、O(n)が必要であり、アルゴリズム全体の最悪の時間複雑度はO(Q*n)、Qは問い合わせの回数である.△この方法でPOJ 1330を通過するのはストレスがない.その問題は一つの質問しかないからだ...
オンラインO(n 2)−O(1)繰返しの考え方:L(u)をノードuの深さ(根からの距離)とする.if L(u)2)、質問にはO(1)しか必要ありません.
★オフラインのTarjanアルゴリズム:O(n+Q)tarjanアルゴリズムは集合操作のためのデータ構造-並列調査セット(union-find set or disjoint set)を利用する.しかし,ここではこのデータ構造は補助的であり,理解アルゴリズムには影響を及ぼさず,アルゴリズムがどのようなものであるかを理解し,調べることができることを理解した.tarjanアルゴリズムは,現在のノードがrootであると仮定すると,rootノードには多くのサブツリーがあるに違いないが,最も左側のサブツリーから研究を開始し,クエリする2つのノードu,vが最も左のサブツリーであれば,より小規模な問題となる.uが一番左のサブツリーにあり、vが他のサブツリーにある場合、LCA(v,u)=father(u)になります.では、uが一番左のサブツリーの中にある場合、LCA(v,u)=father(father(u)).ここを見て、よく知っている人や、集まった人を調べてみると、集合のfather情報を探すようなものかもしれません.そう、これがtarjanアルゴリズムの核心思想です.上記の方法は扱いにくいように見えますが、どのようにしてfather(u)を保存しておき、LCA(u,v)=father(...father(...father(u)))をどのように知るのでしょうか.これがTarjanアルゴリズムの巧みさである:再帰的なLCA(プロセス)を利用する.疑似コード:
LCAタイトル:
POJ 1330 Nearest Common Ancestors(ベース)この水は素朴な方法で簡単で速いですが、LCAに入るといいですね.コード(
LCAテンプレート):
http://ideone.com/1pnjB7
POJ 3694 Network(好題)辺二連通成分+を調べ、縮点+素朴LCAを維持する.LCAに対する理解を深める.
http://www.abandonzhang.com/archives/649
POJ 1986 Distance Queries(ベース)は基本的なLCAより少し距離が多いが,本質はd[u,v]=dis[u]+dis[v]−dis[LCA(u,v)]という問いに対して同じである.現在のポイントからルートまでの距離をLCAで動的に変更できます.コード:
http://ideone.com/A0M7Ms
その他のテーマ:
POJ:
3728実は記録されているものが少し多い(1)子供から父親までの最大価格(2)子供から父親までの最小価格(3)自分から祖先までの最大収益(4)祖先から自分の最大収益まで、ここでの状況別討論は手動でスケッチを描くだけで、使用してセットを調べると同時に、更新操作をして、上記の4つの変数を維持して、1つのクエリーに対して、私たちは山の斜面を登る方法で最適値を保留して、この中で絵を描くともっと直観的になります.
3417 LCA+DP//新しく追加されたm辺について、その2つの端点のツリー上の経路を考えてみましょう.新しい辺を追加すると、明らかにツリーにリングが発生します.新しい辺を削除し、元の木から//いずれかを削除すると、図全体の連通性が破壊されます.この点から、最後にm辺を追加した後の図を見てみましょう.1本のツリー上の辺について、1つ以上のループに囲まれている場合、1つのエッジを削除すると図が連通しないため、問題は各ツリーエッジがどれだけのループに含まれているかを統計することに転化し、ここでの統計は//ツリーDPを使用し、dp[x]はxからヒールまでのエッジバックループが覆われた回数を表す.では、新たに追加されたエッジ(x,y)が統計結果に及ぼす影響はdp[x]+,dp[y]+,//dp[lca(x,y)]-2であり、最終結果を分析すると、被リングに0が含まれているエッジについては、明らかに図中でエッジが切断されている場合、それを削除し、mエッジから任意のエッジ//を選択して徒歩で連通することができ、被リングに1回含まれるエッジについては削除し、そしてリングの中でm本の辺の中の辺を削除して辺部を連通させることができて、最後の結果はこの2つの部分//ここで注意しなければならないのは、1つのx=yの辺に対して、直接それを無視して、私はこの死活をプラスしていません
3237 LCA+RMQ、地味なTarjanでもいいはずなので、すべてのクエリーを前処理しますが、書くのが面倒で、ちょうどこの機会にRMQの形式を勉強して、まずdfsで木をオラシーケンスに変えて、それからrmqを前処理して、逆を取って、クエリー操作に対して、同じように山の斜面を登る方式を採用して、このような問題はずっと簡単になりました
2763//具体的なやり方:まず0操作に対して、前の位置と形成されたクエリー対//と見なして記録し、次にLCAを行い、LCAをするときにdfsを利用してタイムスタンプを記録し、//これで私たちは1つの区間を得て、この区間の表示は1つのサブツリーを代表して、もちろん、ここでは1つのセグメントツリーでメンテナンスできます//1つのエッジを検索するたびに、このエッジの重み値をツリー配列に挿入し、ルートに加えて、サブノードからフォローまでの距離を表します.ルートの開始時間は必然的に1//であるため、現在のノードの終了時間を現在のエッジの重み値に追加する必要があるのは明らかです.またこの点の前の時間帯から削除して、このように実際の効果は//1辺の重み値を挿入して、ここで長い間考えて、それでは操作を修正して、同じ道理でここのタイムスタンプnの初めは根を代表して、どうして、毎回追加して調整するのは//サブツリーで、dfsのため、最後に更新するのは必ず1この木です
ZOJ 3195//問題の説明、1本の辺権の木を与えて、3つの点の照会を与えて、彼らをつなぐ最小の代価//2を求めて距離の和を求めて2を除いて、数軸の上の3つの点に連絡して、このように求めますか?
HDU 3078の標準的なやり方はLCA+treap+線分樹であるべきで、ここでは山の斜面を登る方法で水を使って、1つのスタックで記録することができます.
HDU 2586という問題は、1本の木を与え、各辺に一定の重み値があり、q回の質問で、ある2点間の距離を毎回尋ねることを意味している.これでLCAで解くことができ,まずu,vの2点のlcaを見つけ,距離値を計算すればよい.ここでの計算方法は,ルートノードから任意の点までの距離dis[]を記すことで,ans=dis[u]+dis[v]−2*dis[lca(v,v)]となり,この式は比較的容易に理解できる.
http://blog.163.com/kevinlee_2010/blog/static/16982082020120794613496/
最近の公的祖先(LCA)問題
最近の共通祖先(Least Common Ancestors、略称LCA)は、ツリーに関する基本的な問題であり、この問題の説明は以下の通りである.
T内の任意の2つのノードuおよびvに対して、ルートツリーTが与えられる.LCA(T,u,v)というルートから最も遠いノード(あるいはuとvに最も近いノード)rを求め,rがuとvの祖先であるようにする.この質問は「質問−回答」と見なすことができる.式の問題.2つの方法でこの問題を解決することができます.1つは、まず十分な前処理を行い、質問に答えるたびに、わずかな時間で済むことです.このアルゴリズムをオンラインアルゴリズム(online algorithm)といいます.もう1つは、すべての質問を収集(読み込み)してから、すべての回答を完了するアルゴリズムです.このアルゴリズムをオフラインアルゴリズム(Offline algorithm)と言います.
最も素朴なオンラインアルゴリズム:ノードuからルートノードへの経路(すべての通過ノード)を1つのチェーンテーブルに格納し、vからルートへ歩き始めると、発見された最初のチェーンテーブルのノードが最近の共通の祖先である.明らかにこの2つのステップが最悪の場合、O(n)が必要であり、アルゴリズム全体の最悪の時間複雑度はO(Q*n)、Qは問い合わせの回数である.△この方法でPOJ 1330を通過するのはストレスがない.その問題は一つの質問しかないからだ...
オンラインO(n 2)−O(1)繰返しの考え方:L(u)をノードuの深さ(根からの距離)とする.if L(u)
★オフラインのTarjanアルゴリズム:O(n+Q)tarjanアルゴリズムは集合操作のためのデータ構造-並列調査セット(union-find set or disjoint set)を利用する.しかし,ここではこのデータ構造は補助的であり,理解アルゴリズムには影響を及ぼさず,アルゴリズムがどのようなものであるかを理解し,調べることができることを理解した.tarjanアルゴリズムは,現在のノードがrootであると仮定すると,rootノードには多くのサブツリーがあるに違いないが,最も左側のサブツリーから研究を開始し,クエリする2つのノードu,vが最も左のサブツリーであれば,より小規模な問題となる.uが一番左のサブツリーにあり、vが他のサブツリーにある場合、LCA(v,u)=father(u)になります.では、uが一番左のサブツリーの中にある場合、LCA(v,u)=father(father(u)).ここを見て、よく知っている人や、集まった人を調べてみると、集合のfather情報を探すようなものかもしれません.そう、これがtarjanアルゴリズムの核心思想です.上記の方法は扱いにくいように見えますが、どのようにしてfather(u)を保存しておき、LCA(u,v)=father(...father(...father(u)))をどのように知るのでしょうか.これがTarjanアルゴリズムの巧みさである:再帰的なLCA(プロセス)を利用する.疑似コード:
void LCA(u){ MAKE-SET(u); ancestor(u) = u; for (u v){ LCA(v); Union(u,v); ancestor[FIND-SET[u]] = u; } color[u] = BLACK; // ， 。 for (Q[u] v) if color[v] == BLACK ans_LCA(u,v) = ancestor[FIND-SET(v)]; } LCA(u)が完了すると、uをルートとするツリーのすべてのノードFIND-SETのfatherがuになることを考慮する.では、各質問vについて、vがすでにアクセスされている場合は、2つの状況にほかならない.v uのサブツリーの中で;2.vはuのサブツリーにありません.状況1と言えばFIND-SET(v)は自然にuであり、vが集まる(サブツリー)のfather---uである.それでは状況2を考える.vはすでに訪問されているので、彼は①father(u)を根に現れる可能性がある.uの左兄弟のサブツリー(私たちのデフォルトのツリーの遍歴順序は左から右)では、FIND-SET(v)=father(u)(LCAプロセスがuに達したため、uの左兄弟がLCAプロセスを完了し、father(u)の集合に統合されたことを示している)であり、答えも確かにそうではないでしょうか.②father(father(u))を元に、father(u)の左兄弟の子木に(①でなければfather(u)から除外されているのか)、同様にfather(u)の左兄弟がLCAプロセスを完了しているため、father(father(u))代表の集合に統合されているため、FIND-SET(v)=father(u))となる.これで実際にあったはずの答えに対応します.では、①時のfather(u)、②時のfather(u))は彼ら自身を代表しているのかと聞かれます.彼らの父に合併されなかったのか?明らかにありません.LCA(u)はまだ進行中なので、LCA(father(u))はまだ完成していませんし、LCA(father(u))ももちろんまだ完成していません...この時father(u)、father(u))は彼自身の集合の中にあり、まだ父の集合に合併していない.(同じ色は同じ集合を表す) LCAタイトル:
POJ 1330 Nearest Common Ancestors(ベース)この水は素朴な方法で簡単で速いですが、LCAに入るといいですね.コード(
LCAテンプレート):
http://ideone.com/1pnjB7
POJ 3694 Network(好題)辺二連通成分+を調べ、縮点+素朴LCAを維持する.LCAに対する理解を深める.
http://www.abandonzhang.com/archives/649
POJ 1986 Distance Queries(ベース)は基本的なLCAより少し距離が多いが,本質はd[u,v]=dis[u]+dis[v]−dis[LCA(u,v)]という問いに対して同じである.現在のポイントからルートまでの距離をLCAで動的に変更できます.コード:
http://ideone.com/A0M7Ms
その他のテーマ:
POJ:
3728実は記録されているものが少し多い(1)子供から父親までの最大価格(2)子供から父親までの最小価格(3)自分から祖先までの最大収益(4)祖先から自分の最大収益まで、ここでの状況別討論は手動でスケッチを描くだけで、使用してセットを調べると同時に、更新操作をして、上記の4つの変数を維持して、1つのクエリーに対して、私たちは山の斜面を登る方法で最適値を保留して、この中で絵を描くともっと直観的になります.
3417 LCA+DP//新しく追加されたm辺について、その2つの端点のツリー上の経路を考えてみましょう.新しい辺を追加すると、明らかにツリーにリングが発生します.新しい辺を削除し、元の木から//いずれかを削除すると、図全体の連通性が破壊されます.この点から、最後にm辺を追加した後の図を見てみましょう.1本のツリー上の辺について、1つ以上のループに囲まれている場合、1つのエッジを削除すると図が連通しないため、問題は各ツリーエッジがどれだけのループに含まれているかを統計することに転化し、ここでの統計は//ツリーDPを使用し、dp[x]はxからヒールまでのエッジバックループが覆われた回数を表す.では、新たに追加されたエッジ(x,y)が統計結果に及ぼす影響はdp[x]+,dp[y]+,//dp[lca(x,y)]-2であり、最終結果を分析すると、被リングに0が含まれているエッジについては、明らかに図中でエッジが切断されている場合、それを削除し、mエッジから任意のエッジ//を選択して徒歩で連通することができ、被リングに1回含まれるエッジについては削除し、そしてリングの中でm本の辺の中の辺を削除して辺部を連通させることができて、最後の結果はこの2つの部分//ここで注意しなければならないのは、1つのx=yの辺に対して、直接それを無視して、私はこの死活をプラスしていません
3237 LCA+RMQ、地味なTarjanでもいいはずなので、すべてのクエリーを前処理しますが、書くのが面倒で、ちょうどこの機会にRMQの形式を勉強して、まずdfsで木をオラシーケンスに変えて、それからrmqを前処理して、逆を取って、クエリー操作に対して、同じように山の斜面を登る方式を採用して、このような問題はずっと簡単になりました
2763//具体的なやり方:まず0操作に対して、前の位置と形成されたクエリー対//と見なして記録し、次にLCAを行い、LCAをするときにdfsを利用してタイムスタンプを記録し、//これで私たちは1つの区間を得て、この区間の表示は1つのサブツリーを代表して、もちろん、ここでは1つのセグメントツリーでメンテナンスできます//1つのエッジを検索するたびに、このエッジの重み値をツリー配列に挿入し、ルートに加えて、サブノードからフォローまでの距離を表します.ルートの開始時間は必然的に1//であるため、現在のノードの終了時間を現在のエッジの重み値に追加する必要があるのは明らかです.またこの点の前の時間帯から削除して、このように実際の効果は//1辺の重み値を挿入して、ここで長い間考えて、それでは操作を修正して、同じ道理でここのタイムスタンプnの初めは根を代表して、どうして、毎回追加して調整するのは//サブツリーで、dfsのため、最後に更新するのは必ず1この木です
ZOJ 3195//問題の説明、1本の辺権の木を与えて、3つの点の照会を与えて、彼らをつなぐ最小の代価//2を求めて距離の和を求めて2を除いて、数軸の上の3つの点に連絡して、このように求めますか?
HDU 3078の標準的なやり方はLCA+treap+線分樹であるべきで、ここでは山の斜面を登る方法で水を使って、1つのスタックで記録することができます.
HDU 2586という問題は、1本の木を与え、各辺に一定の重み値があり、q回の質問で、ある2点間の距離を毎回尋ねることを意味している.これでLCAで解くことができ,まずu,vの2点のlcaを見つけ,距離値を計算すればよい.ここでの計算方法は,ルートノードから任意の点までの距離dis[]を記すことで,ans=dis[u]+dis[v]−2*dis[lca(v,v)]となり,この式は比較的容易に理解できる.