G - Distance Queries on a Tree

以下の問題の解説を理解するための知識をまとめてみました。

atcoder.jp

繰り返し二乗法

繰り返し二乗法とは、x¹, x², x⁴, x⁸, x¹⁶, ... を組み合わせて、xⁿを高速で計算するアルゴリズムです。

x¹, x², x⁴, x⁸, x¹⁶ は、二乗していけば、簡単に求めていくことができます。

nを1, 2, 4, 8, 16, ... の組み合わせで表すことができます。 例えば、n=7 の場合、7 = 1 + 2 + 4 で表すことができます。 もう少し表し直すと 7 = 2⁰ + 2¹ + 2² となり、やっていることは２進数の変換です。

long long pow(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret *= x; // n & 1で、1ビット目を見る
        x *= x; // x^1, x^2, x^4, x^8, ... を計算していく
        n >>= 1; // nを1bit右にずらして、1bit目に各桁のbitが来るようにする
    }
    return ret;
}

参考

algo-logic.info

ダブリング

繰り返し二乗法は、ダブリングの一種です。

ダンブリングは、「2^k 先の要素は何か」を求めます。以下の変数を考えます。

doubling[k][i] : i番目の要素から2^k先の要素は何か

初期化は、2⁰=1個先を記録します。これをもとに2^k先の要素を求めていきます。 求め方は、以下のとおりです。

doubling[k+1][i] = doubling[k][doubling[k][i]]

doubling[k][doubling[k][i]] は、「i番目の要素から2^k先の要素から、さらに2^k先の要素」という意味になります。

クエリとして、「K個先の要素を求める」を考えます。 Kのk桁目が1ならば now = doubling[k][now]とします。

algo-logic.info

最近共通祖先（LCA：Lowest Common Ancestor）

LCAでは、ダブリングを使います。

DFSなどで、すべての頂点について、根からの距離と親を求め(ダブリングの初期化)、ダブリングによって2^k先の祖先を求めます。

algo-logic.info