AtCoder Begginer Contest #014 D.閉路
問題概要
- 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の最も近い共通の親を求めたいときは以下のようにする。
- depth[a]とdepth[b]を比較して、深い方を浅い方の深さに揃える
- 揃えるときは、depth[深い方] - depth[浅い方]回だけfを試行すればよいので、前回の記事のように実行してみる
- もし揃え終わった後、aとbが既に共通になっていれば、a(またはb)を返す
- kの降順ループについて、aとbのそれぞれについて、2^k回fを試行した結果を考える
- もし、試行した結果が同じ頂点なら、それよりも前(またはそれ自身)が最も近い親なので、何もしない
- もし、試行した結果が違う頂点なら、それよりも後に最も近い親がいるので、aとbを2^k回fを試行した後の頂点に変える。
- (このループは、降順で実行しているため、ループが終わるとaとbは必ず最も近い親の一つ前の子になる
- 最後に、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; }