ひとりで勝手にはじめた蟻本読書会 グラフ理論 最短路問題 ワーシャルフロイド法 蟻本読書会 の続きです。
蟻本ではグラフに関する章はダイクストラ法、ベルマンフォード法、ワーシャルフロイド法で終わっているのですが、面白い課題をみつけたので掲載します。「木上での全頂点対最短経路問題」と「最小共通祖先」です。
Contents
根付き木の最小共通祖先
根付き木において、ある2頂点の共通祖先（2頂点から根までのパス両方の上にある頂点）のうち、いちばん根から遠いものを最小共通祖先（LCA：Lowest Common Ancestor）と呼びます。
木上の 2 頂点 u, v の距離は、（根から u までの距離）+（根から v までの距離）- 2 ×（根から u, v のLCAまでの距離）です。
根から各頂点までの距離は幅優先探索や深さ優先探索で O(V)（V は頂点数） で求めることができます。では最小共通祖先はどのようにすれば求めることができるでしょうか？
オイラーツアーを使った方法
木の根から DFS の探索で訪れた頂点を、その順に記録することをオイラーツアーといいます。オイラーツアーで生成された頂点配列の特徴として「任意の連続する部分列に含まれる頂点集合が部分木になる」があります。
u, v を含み、LCAの祖先を含まない部分木は、最初に u が登場する部分と、最初に v が登場する部分の間の列の集合で表現できます。この中で最も根からの距離が小さいものを求めれば、それが最小共通祖先となります。
木において、最小共通祖先を求めるには（1）根から各頂点までの距離を求める前処理と（2）オイラーツアーを生成する前処理が必要です。
実践問題
n 個の頂点と n – 1 本の辺からなる連結な無向グラフが与えられます。それぞれの頂点には 1 から n までの番号が順番にふられています。
グラフ理論において、このような条件を満たすグラフは木と呼ばれ、閉路を含まないという性質があります。このグラフに対し、元のグラフに含まれない追加辺 (a, b) を 1 つ追加したグラフについて考えてみるとこのグラフはちょうど 1 つの閉路を含みます。
あなたの仕事はそのようなグラフについて閉路の長さ(閉路に含まれる辺の数)を出力することです。ただ追加辺の候補はいくつかあり Q 個与えられるので、それら全ての候補について答えを出力してください。
入力されるデータ
N
x_1 y_1
x_2 y_2
…
x_N-1 y_N-1
Q
a_1 b_1
a_2 b_2
…
a_Q b_Q1 ≦ N, Q ≦ 100,000
各頂点までの距離とオイラーツアーで最小共通祖先を求める
入力されたデータから木の隣接リストを生成します。そのあとGetDistancesメソッドで根を頂点 0 としてここからの各頂点までの距離を求め、結果を配列で返しています。そのあと GetEulerTourメソッドでオイラーツアーで訪問する順に頂点番号のリストを取得しています。
オイラーツアーで頂点 v が最初に登場するのは何番目かをすぐに取得できるようにするために、頂点ｖはindexs[v] を見ればどこにあるかわかるようにしています。また distances2 にはオイラーツアーの index から対応する頂点の最短距離を取得できるようにしています。
そのあとクエリーが飛んできたらオイラーツアーのなかで最初に a が登場する部分と、最初に b が登場する部分の間を調べ、この中で最も根からの距離がもっとも小さいを探しています。これが最小共通祖先の根からの最短距離となります。あとは木上の 2 頂点 u, v の距離は、（根から u までの距離）+（根から v までの距離）- 2 ×（根から u, v のLCAまでの距離）なので、これに新しく追加した辺の長さである 1 を追加したものを返しています。
ただ、これだと制限時間以内に終わらないのではないかと思われます。1 ≦ N, Q ≦ 100,000 という制約があるため、最大で長さが 100,000 ある区間で最小値を探す処理を 100,000 回繰り返すことになります。たぶんダメだと思います。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 |
using System; using System.Collections.Generic; using System.Linq; class Program { static long[] GetDistances(List<int>[] list, int vCount) { long[] costs = new long[vCount]; for (int i = 0; i < costs.Length; i++) costs[i] = long.MaxValue / 2; bool[] isVisits = new bool[vCount]; Queue<int> queue = new Queue<int>(); queue.Enqueue(0); isVisits[0] = true; costs[0] = 0; while (queue.Count > 0) { int v = queue.Dequeue(); long cost = costs[v]; foreach (int next in list[v]) { if (isVisits[next]) continue; isVisits[next] = true; costs[next] = cost + 1; queue.Enqueue(next); } } return costs; } static List<int> GetEulerTour(List<int>[] list, int vCount) { bool[] isVisits = new bool[vCount]; isVisits[0] = true; List<int> rets = new List<int>(); rets.Add(0); Dfs(0); return rets; void Dfs(int v) { foreach (int next in list[v]) { if (isVisits[next]) continue; isVisits[next] = true; rets.Add(next); Dfs(next); rets.Add(v); } } } static void Main() { int N = int.Parse(Console.ReadLine()); List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); for (int i = 0; i < N - 1; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = vs[0] - 1; int y = vs[1] - 1; list[x].Add(y); list[y].Add(x); } long[] distances = GetDistances(list, N); List<int> eulerTour = GetEulerTour(list, N); // オイラーツアーで頂点 v が最初に登場するのは何番目かをすぐに取得できるようにする // 頂点ｖはindexs[v] 番目にある int[] indexs = new int[eulerTour.Count]; for (int i = 0; i < eulerTour.Count; i++) indexs[i] = -1; for (int i = 0; i < eulerTour.Count; i++) { int a = eulerTour[i]; if(indexs[a] == -1) indexs[a] = i; } // オイラーツアーの配列の index から対応する頂点の最短距離を取得できるようにする long[] distances2 = new long[eulerTour.Count]; for (int i = 0; i < eulerTour.Count; i++) distances2[i] = distances[eulerTour[i]]; int Q = int.Parse(Console.ReadLine()); List<long> rets = new List<long>(); for (int i = 0; i < Q; i++) { // クエリーが飛んできたらオイラーツアーのなかで // 最初に a が登場する部分と、最初に b が登場する部分の間を調べる。 // indexs[a], indexs[b] のうち、小さいほうを start, 大きいほうを end とすると、 // distances2 の [start, end] の区間から最小値を探す。 // これが（頂点 a と頂点 b の最小共通祖先）の根からの最短距離 int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int start = Math.Min(indexs[a], indexs[b]); int end = Math.Max(indexs[a], indexs[b]); long min = long.MaxValue; for (int j = start; j <= end; j++) min = Math.Min(min, distances2[j]); // 木上の 2 頂点 u, v の距離を求める // （根から u までの距離）+（根から v までの距離）- 2 ×（根から u, v のLCAまでの距離） long d = distances[a] + distances[b] - 2 * min; // 上記に 1 を追加したものが求める解 rets.Add(d + 1); } foreach(long ret in rets) Console.WriteLine(ret); } } |
distances2 の [start, end] の区間から最小値を探すという処理を短時間に何度も繰り返すことになるので、これに対応できる処理を書く必要があります。
平方分割で大量のクエリに対応できるようにする
どうするか？ 平方分割はどうでしょうか？
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 |
class Program { static void Main() { int N = int.Parse(Console.ReadLine()); List<int>[] list = new List<int>[N]; for (int i = 0; i < N; i++) list[i] = new List<int>(); for (int i = 0; i < N - 1; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int x = vs[0] - 1; int y = vs[1] - 1; list[x].Add(y); list[y].Add(x); } long[] distances = GetDistances(list, N); List<int> eulerTour = GetEulerTour(list, N); int[] indexs = new int[eulerTour.Count]; for (int i = 0; i < eulerTour.Count; i++) indexs[i] = -1; for (int i = 0; i < eulerTour.Count; i++) { int a = eulerTour[i]; if(indexs[a] == -1) indexs[a] = i; } long[] distances2 = new long[eulerTour.Count]; for (int i = 0; i < eulerTour.Count; i++) distances2[i] = distances[eulerTour[i]]; // ↑↑↑ ここまでは同じ // 平方分割で大量クエリに対応できるようにする // 配列 distances2 全体をひとつのブロックの長さが sqrt のブロック sqrt 個に分割し // ブロック内の最小値を求める int sqrt = (int)Math.Ceiling(Math.Sqrt(distances2.Length)); long[] blocks = new long[sqrt]; for (int i = 0; i < sqrt; i++) blocks[i] = long.MaxValue; for (int i = 0; i < distances2.Length; i++) blocks[i / sqrt] = Math.Min(blocks[i / sqrt], distances2[i]); // 前処理が終わったのでクエリを処理する int Q = int.Parse(Console.ReadLine()); List<long> rets = new List<long>(); for (int i = 0; i < Q; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; // 配列 indexs からオイラーツアー配列のどこからどこまでの最小値を取得するか調べる int start = Math.Min(indexs[a], indexs[b]); int end = Math.Max(indexs[a], indexs[b]); int cur = start; long min = long.MaxValue; while (true) { // ブロックを完全に披露する場合は ひとつひとつ調べずにブロックに格納された最小値で評価する // ブロックを完全に披露する場合とは現在位置が cur が sqrt で割り切れる場合で // （1）end が現在位置に sqrt - 1 を足した位置と同じかそれより向こうにある場合 // （2）（1）ではない場合で end が配列の最後の位置である場合 // 単純に（1）または（2）とすると事故るので注意！！！ int case0 = 0; if (cur % sqrt == 0) { if (end >= cur + sqrt - 1) case0 = 1; else if (end == distances2.Length - 1) case0 = 2; } if (case0 == 1 || case0 == 2) { min = Math.Min(min, blocks[cur / sqrt]); cur += sqrt; if (case0 == 2) break; } else { min = Math.Min(min, distances2[cur]); cur++; } if (cur > end) break; } // ↓↓↓↓ あとは上記コードと同じ long d = distances[a] + distances[b] - 2 * min; rets.Add(d + 1); } foreach(long ret in rets) Console.WriteLine(ret); } } |
