木上のパスに関する問題!!
LCA で解決できる典型問題
問題概要
頂点数 の木が与えられる。次の 個のクエリに答えよ。
- 各クエリでは木上の 2 頂点 が与えられる
- 木に辺 を仮に追加したとすると、閉路が 1 個形成される
- その閉路に含まれる辺の本数を答えよ
制約
考えたこと
グラフ理論的には、木とは「閉路をもたないグラフ」ということになる。下図のように、それに辺を新たに付け加えると閉路ができるのだ。
一般に、辺 を付け加えることでできる閉路の長さは、パス - の長さに 1 を足したものになる。
よって各クエリは「パス - の長さを答えてください (それに 1 を足して出力してください)」と言い換えられるのだ。
木のパスの長さ
木のパスの長さに答える問題は超有名問題で、蟻本上級編「グラフマスターへの道」にも解説がある。いろんなやり方があるが、LCA を求める方法が有名だ (さらに LCA を求める方法もたくさんある)。
まず、木の根を 1 つ決めて根付き木にしてしまう。そして、二頂点 に対して、LCA (最近共通祖先) を求めよう (下図の頂点 )。
LCA の求め方は蟻本参照。
LCA が求められたら、次の値を合計することでパスの長さが求められる。
前者は (頂点 の深さ) - (頂点 の深さ) で求められて、後者は (頂点 の深さ) - (頂点 の深さ) で求められる。つまり、
depth[a] + depth[b] - 2 * depth[v]
で求められる (depth は各頂点の深さ)。
コード
ここでは、LCA を求める処理をライブラリ化したものを用いた。
https://github.com/drken1215/algorithm/blob/master/DataStructureOnTree/LCA_doubling.cppgithub.com
計算量は となる。
#include <iostream>
#include <vector>
using namespace std;
using Graph = vector<vector<int>>;
struct LCA {
vector<vector<int> > parent;
vector<int> depth;
LCA() { }
LCA(const Graph &G, int r = 0) { init(G, r); }
void init(const Graph &G, int r = 0) {
int V = (int)G.size();
int h = 1;
while ((1<<h) < V) ++h;
parent.assign(h, vector<int>(V, -1));
depth.assign(V, -1);
dfs(G, r, -1, 0);
for (int i = 0; i+1 < (int)parent.size(); ++i)
for (int v = 0; v < V; ++v)
if (parent[i][v] != -1)
parent[i+1][v] = parent[i][parent[i][v]];
}
void dfs(const Graph &G, int v, int p, int d) {
parent[0][v] = p;
depth[v] = d;
for (auto e : G[v]) if (e != p) dfs(G, e, v, d+1);
}
int get(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int i = 0; i < (int)parent.size(); ++i)
if ( (depth[v] - depth[u]) & (1<<i) )
v = parent[i][v];
if (u == v) return u;
for (int i = (int)parent.size()-1; i >= 0; --i) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
return parent[0][u];
}
};
int main() {
int N;
cin >> N;
Graph G(N);
for (int i = 0; i < N-1; ++i) {
int a, b;
cin >> a >> b;
--a, --b;
G[a].push_back(b);
G[b].push_back(a);
}
LCA lca(G);
int Q;
cin >> Q;
for (int q = 0; q < Q; ++q) {
int a, b;
cin >> a >> b;
--a, --b;
int v = lca.get(a, b);
int len = lca.depth[a] + lca.depth[b] - 2 * lca.depth[v];
cout << len + 1 << endl;
}
}