ライブラリ LCA
計算量
構築$ O(NlogN)
クエリ$ O(logN)
機能
LCAは、根付き木において、２つの頂点を含む部分木の最小の共通の祖先を$ O(logN)で求める方法である。 内部で使用するアルゴリズムとしてはダブリングを使用している。 まず、
根からの深さdepth
距離dist
ダブリング配列nexted
を用意する。
次に、ダブリングを構築して、ある頂点$ vの$ pだけ親の頂点を$ O(logp)で求められうようにする。
そして、実際に共通する祖先を求める$ (u, v)の組について考える。
まず、もし最初深さが同じでないなら、同じ深さにしたいので、ダブリングをして、共通の深さにする。
https://gyazo.com/72ea4ebb4fef9892878cb08a4326d08e
そして、depth[u] = depth[v]としたら、深さが同じになったため、共通する頂点にたどり着くようにダブリングをする。
しかし、実際にダブリングすると-1が面倒なので、
$ u, vから$ p親側に動かすとしたとき、一致しなければ動かすとする。
もし範囲外にでれば-1となって共通してしまうため、一致しないとすれば動かせる。
よって、
https://gyazo.com/40704908ffb0e162aebf5157bca82468
上記のように共通祖先である$ wの一個子供分の頂点にそれぞれ$ u, vが来る。
よって、あとはreturn nexted[0][u]として、一個分親の頂点を返せば、$ u, vの共通祖先を$ O(logp)の定数倍で求めることができる。
嬉しさ
共通する祖先を求めることができると、木上の任意の二点$ u, vを結ぶパスの距離を$ O(1)で計算できる。
（共通祖先$ w = loca(u, v)を求めるのは$ O(logp)だけかかってしまうが･･･）
https://gyazo.com/6bea5b6f838f06e064d6d56de84bfa66
上記のように、根$ rから$ u,vまでの距離を求めて、共通する祖先$ wと$ rの距離を引けば、
$ u, v間の経路の距離を$ O(logp)で求めることができて嬉しい。
code:cpp
template<typename T>
class LowestCommonAncestor {
private:
const long long LOG;
const int N;
const WeightedGraph<T> &graph;
vector<int> depth;
vector<T> dist;
vector<vector<int>> nexted;
public:
LowestCommonAncestor(const WeightedGraph<T> &graph, const long long LOG = 60) : graph(graph), LOG(LOG), N(graph.size()), depth(N, -1), dist(N, numeric_limits<T>::max()) {
nexted.assign(LOG + 1, vector<int>(N, -1));
}
void dfs(int v, int p, int d, long long sum) {
int to = e.to;
long long cost = e.cost;
if (to != p) {
dfs(to, v, d + 1, sum + cost);
}
}
}
void build(int s) {
dfs(s, -1, 0, 0);
for (int k = 0; k < LOG; k++) {
for (int v = 0; v < N; v++) {
}
}
}
int lca(int u, int v) {
if (depthu > depthv) swap(u, v); for (long long i = LOG - 1; i >= 0; i--) {
if ((depthv - depthu) & (1LL << i)) { }
}
if (u == v)return u;
for (long long i = LOG - 1; i >= 0; i--) {
if (nextediu != nextediv) { }
}
}
int parent_d(int v, long long d) {
for (long long i = LOG - 1; i >= 0; i--) {
if (d & (1LL << i)) {
}
}
return v;
}
T get_distance(int u, int v) {
return sum;
}
};