競プロ++

TopCoderやCodeforces, AtCoderなど。解いた問題の備忘録。とりあえずの目標はICPCの予選突破です…

AtCoder Begginer Contest #014 D.閉路

プログラミングコンテスト AtCoder ダブリング

問題

http://abc014.contest.atcoder.jp/tasks/abc014_4

問題概要

  • N個の頂点からなる木が与えられる（辺はN-1個）
    • グラフは単純（自己辺、多重辺を含まない）である
    • 辺の長さは1
  • Q個のクエリ(a, b)が与えられるので、頂点aとbを結んだときに出来る閉路の長さを求めよ。
制約
  • 1<=N<=100000
  • 1<=Q<=100000

解法

頂点aとbを結んだときに出来る閉路の長さは、aとbの最短距離に1を足したものと等価。
また、適当に根sを定め、sから見た頂点iの深さをdepth[i]とすると、
任意の頂点aとbの最短距離は、

depth[a] + depth[b] - 2 * depth[aとbの最も近い共通の親]

となる。（ここまで本番中に考察できた）

問題は、「aとbの最も近い共通の親」をどのようにして求めるか、である。
これは、LCA(Lowest Common Ancestor)という有名問題らしい。

LCAはダブリングによって効率的に求めることができる。
ダブリングについてはこちらから。
http://kakira.hatenablog.jp/entry/2014/09/16/201532

f : V→V(Vは頂点集合)をv∈Vについて、f(v) := vの親 とする。
ただし、vが根の場合、f(v) = -1。
fを2^k回試行した後の値をdp[k][v]の配列に格納するとすると、
dp[k + 1][v] = dp[k][f[k][v]];
が成り立つ。
k = 0のときのdp[0][v]は深さ優先探索で調べればOK。

aとbの最も近い共通の親を求めたいときは以下のようにする。

  1. depth[a]とdepth[b]を比較して、深い方を浅い方の深さに揃える
    • 揃えるときは、depth[深い方] - depth[浅い方]回だけfを試行すればよいので、前回の記事のように実行してみる
    • もし揃え終わった後、aとbが既に共通になっていれば、a(またはb)を返す
  2. kの降順ループについて、aとbのそれぞれについて、2^k回fを試行した結果を考える
    • もし、試行した結果が同じ頂点なら、それよりも前（またはそれ自身）が最も近い親なので、何もしない
    • もし、試行した結果が違う頂点なら、それよりも後に最も近い親がいるので、aとbを2^k回fを試行した後の頂点に変える。
    • (このループは、降順で実行しているため、ループが終わるとaとbは必ず最も近い親の一つ前の子になる
  3. 最後に、dp[0][a](またはdp[0][b])つまり、aの一つ上の親を返して終わり。

ダブリングが分かっていればそこまで難しくはない。
が、細かいチェックがあるので油断すると死。

覚えておくべきこと

今回のように、LCAは閉路の長さを求めるのにも使えるが、やはり一番使えるのは最短距離。
depth[a] + depth[b] - 2 * depth[aとbの最も近い共通の親]の公式と合わせて覚えておこう。

つまづいたところ

  • ダブリングを知らなかった
    • 前回のエントリーの方が後に解いた問題です
  • LCAを知らなかった

感想

  • 非常にためになる問題でした。

ソースコード

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <functional>
 
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
 
using namespace std;
 
typedef    long long          ll;
typedef    unsigned long long ull;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      pii;
 
const int INF=1<<29;
const double EPS=1e-9;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};
 
std::vector<pii> e[100000];
std::vector<int> depth(100000, -2);
int dp[17][100000];
int n;
 
void dfs(int v, int dep, int parent) {
	depth[v] = dep;
	dp[0][v] = parent;
 
	for (int i = 0; i < e[v].size(); ++i) {
		if (depth[e[v][i].second] != -2) continue;
		dfs(e[v][i].second, dep + 1, v);
	}
}
 
int getV(int v, int dep) {
	int now = v;
	int i = 0;
 
	do {
		if (dep % 2 == 1) {
			now = dp[i][now];
		}
		dep /= 2;
		i++;
	} while(dep != 0);
	return now;
}
 
int main(int argc, char const *argv[]) {
	
	cin >> n;
 
	for (int i = 0; i < n - 1; ++i) {
		int a, b;
		cin >> a >> b;
		a--, b--;
 
		e[a].push_back(mp(a, b));
		e[b].push_back(mp(b, a));
	}
 
	dfs(0, 0, -1);
 
	for (int k = 1; k < 17; ++k) {
		for (int v = 0; v < n; ++v) {
			if (dp[k - 1][v] == -1) {
				dp[k][v] = -1;
			} else {
				dp[k][v] = dp[k - 1][dp[k - 1][v]];
			}
		}
	}
	int Q;
	cin >> Q;
	for (int i = 0; i < Q; ++i) {
		int u, v;
		int ans = 0;
		cin >> u >> v;
		u--, v--;
		int u_ = u, v_ = v;
 
		if (depth[u] > depth[v]) {swap(u, v);}
 
		ans += depth[v] - depth[u];
 
		v = getV(v, depth[v] - depth[u]);
		
 
		if (v == u) {
			cout << ans + 1 << endl;
			continue;
		}
		for (int k = 16; k >= 0; --k) {
 
			if (dp[k][v] == dp[k][u]) {continue;}
			//cout << "debug : " << k << endl;
			v = dp[k][v];
			u = dp[k][u];
		}
 
		int p = dp[0][v];
 
		ans = depth[u_] + depth[v_] - 2 * depth[p] + 1;
 
		cout << ans << endl;
	}
 
 
	return 0;
}