最小共通祖先問題(ダブリング)

目的

最小共通祖先をダブリングによって$O(\log n)$で求めます。
$n$は木の頂点の数です。 最小共通祖先とは根つき木のある二つの頂点u, vに対して、もっとも近い位置にある共通の祖先のことです。

計算量

$O(\log n)$

使い方

static ArrayList edges[]
最小共通祖先を求める根つき木の隣接リスト。
static void init(int N)
Nは根つき木の頂点数。ダブリングを実行するための前計算を行ないます。
static int lca(int u, int v)
頂点uと頂点vの最小共通祖先を$O(\log n)$でreturnします。

ソースコード

// Verified ABC014 D,yukicoder No363
static int MAX_LOG_V;// =(int)log2(MAX_V)+1
static int MAX_V;
static int root;// 根ノードの番号
static int parent[][];// [MAX_LOG_V + 1][MAX_V]
// parent[k][v] 2^k回親を辿ったときに到達する頂点(根を通り過ぎたときは-1)
static int[] depth;// [MAX_V] 根からの深さ
static ArrayList<Integer> edges[];

static void init(int N) {
    // 変数の用意
    MAX_V = N;
    MAX_LOG_V = (int) (Math.log(MAX_V) / Math.log(2)) + 1;
    root = 0;
    parent = new int[MAX_LOG_V + 1][MAX_V];
    depth = new int[MAX_V];

    // parent[0]とdepthを初期化する
    bfs(root, -1, 0);
    // parentを初期化する
    for (int k = 0; k < MAX_LOG_V; k++) {
	for (int v = 0; v < MAX_V; v++) {
	    if (parent[k][v] < 0) {
		parent[k + 1][v] = -1;
	    } else  {
		parent[k + 1][v] = parent[k][parent[k][v]];
	    }
	}
    }
}

static class P {
    int parent;
    int me;
    int depth;

    P(int me, int parent, int depth) {
	this.me = me;
	this.parent = parent;
	this.depth = depth;
    }
}

// dfsだとstack over flow が怖いのでbfs
static void bfs(int v, int p, int d) {
    ArrayDeque<P> q = new ArrayDeque<P>();
    q.add(new P(v, p, d));
    while (!q.isEmpty()) {
	P u = q.poll();
	parent[0][u.me] = u.parent;
	depth[u.me] = u.depth;
	for (int i = 0; i < edges[u.me].size(); i++) {
	    if (edges[u.me].get(i) != u.parent)
		q.add(new P(edges[u.me].get(i), u.me, u.depth + 1));
	}
    }
}

static int lca(int u, int v) {
    // uとvの深さが同じになるまで親を辿る
    if (depth[u] > depth[v]) {
	int d = u;
	u = v;
	v = d;
    }
    // depth[v]-depth[u]>=2^kとなる最小のkを求める。
    // つまりuをvと深さが同じか小さいぎりぎりのところまで親を辿る。
    for (int k = 0; k < MAX_LOG_V; k++) {
	if ((((depth[v] - depth[u]) >> k) & 1) == 1) {
	    v = parent[k][v];
	}
    }
    if (u == v)
	return u;
    // uとvが衝突しないように辿る。
    for (int k = MAX_LOG_V - 1; k >= 0; k--) {
	if (parent[k][u] != parent[k][v] && parent[k][u] != -1 && parent[k][v] != -1) {
	    u = parent[k][u];
	    v = parent[k][v];
	}
    }
    return parent[0][u];
}

Verified

yukicoder No.399 動的な領主