Tổ tiên chung gần nhất · Lowest Common Ancestor

Trên cây có gốc, tổ tiên chung gần nhất (lowest common ancestor, LCA) của $u$ và $v$ là tổ tiên chung sâu nhất của chúng; đường đi giữa $u$ và $v$ đi lên từ $u$ tới LCA rồi đi xuống tới $v$ . Nhờ vậy mọi câu hỏi trên đường đi (độ dài, đỉnh thứ $k$ , cạnh nặng nhất, số đường đi qua một đỉnh) tách thành hai đoạn dọc, mỗi đoạn đi từ một đỉnh lên tổ tiên. Nhảy nhị phân (bài 35) tìm LCA trong $O(\log n)$ ; thứ tự Euler cùng bảng thưa (bài 22) cho $O(1)$ .

Nâng hai đỉnh lên gặp nhau

Dựng bảng up[j][v] (tổ tiên cách $2^j$ bậc) và độ sâu dep[v]. Tìm LCA của $a$ và $b$ :

Giả sử $a$ sâu hơn; nâng $a$ lên đúng $dep_a - dep_b$ bậc theo các bit của hiệu. Nếu lúc này $a = b$ thì đó là LCA.
Ngược lại hai đỉnh cùng độ sâu nhưng khác nhau. Duyệt $j$ từ cao xuống: nếu up[j][a] != up[j][b] thì nhảy cả hai. Hai tổ tiên còn khác nhau nghĩa là vẫn ở dưới LCA, nhảy an toàn; bằng nhau thì có thể đã vượt quá LCA, không nhảy.
Kết thúc, $a$ và $b$ là hai con khác nhau của LCA, đáp án là up[0][a].

Đỉnh cam là u, xanh dương là v; mỗi bước nâng theo một lũy thừa hai. Đỉnh xanh lá là LCA.

C++

ll lca(ll a, ll b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (ll j = LG - 1; j >= 0; j--)
        if (dep[a] - (1LL << j) >= dep[b]) a = up[j][a];
    if (a == b) return a;
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) a = up[j][a], b = up[j][b];
    return up[0][a];
}

Hỏi nhanh

Ở bước hai, vì sao chỉ nhảy khi up[j][a] != up[j][b] chứ không nhảy khi chúng bằng nhau?

Ví dụTổ Tiên Chung Gần Nhất

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh gốc 1 cho bằng cha $p_v < v$ . $q \le 2 \cdot 10^5$ câu hỏi LCA.

Lời giải. LCA bằng bảng nhảy, hai pha: đưa hai đỉnh về cùng độ sâu, rồi nâng cả hai cùng lúc tới ngay dưới tổ tiên chung. Ở đây cha của gốc là chính gốc: nhảy quá gốc thì dừng lại ở gốc, không cần lính canh 0.

Bước 1: cha, độ sâu và bảng. Cha có chỉ số nhỏ hơn con nên một vòng $v = 2..n$ cho cả độ sâu lẫn tầng 0; các tầng sau dựng theo $j$ . LG = 18 vì $2^{17} < 2 \cdot 10^5 \le 2^{18}$ .

C++

up[0][1] = 1;
for (ll v = 2; v <= n; v++) {
    cin >> up[0][v];
    dep[v] = dep[up[0][v]] + 1;
}
for (ll j = 1; j < LG; j++)
    for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];

Bước 2: hàm LCA. Pha một nâng $a$ (sâu hơn) lên cùng độ sâu với $b$ , thử bước lớn trước, tức viết hiệu độ sâu dưới dạng nhị phân. Pha hai nâng cả hai cùng lúc, chỉ khi tổ tiên $2^j$ của chúng còn khác nhau. “Tổ tiên chung” đơn điệu theo số bước nhảy, nên thử bước lớn trước và chỉ nhảy khi chưa chung là chặt nhị phân trên số bước. Xong vòng, $a$ và $b$ là hai con khác nhau của LCA, nên đáp án là cha của chúng.

C++

ll lca(ll a, ll b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (ll j = LG - 1; j >= 0; j--)
        if (dep[a] - (1LL << j) >= dep[b]) a = up[j][a];
    if (a == b) return a;
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) a = up[j][a], b = up[j][b];
    return up[0][a];
}

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 2e5 + 5, LG = 18;
ll n, q, dep[N], up[LG][N];

ll lca(ll a, ll b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (ll j = LG - 1; j >= 0; j--)
        if (dep[a] - (1LL << j) >= dep[b]) a = up[j][a];
    if (a == b) return a;
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) a = up[j][a], b = up[j][b];
    return up[0][a];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    up[0][1] = 1;
    for (ll v = 2; v <= n; v++) {
        cin >> up[0][v];
        dep[v] = dep[up[0][v]] + 1;
    }
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    while (q--) {
        ll a, b;
        cin >> a >> b;
        cout << lca(a, b) << '\n';
    }
}

Input8 5
1 1 2 2 3 6 6
4 5
4 7
7 8
3 8
1 5

Output2
1
6
3
1

Dựng $O(n \log n)$ , mỗi câu hỏi $O(\log n)$ .

Khoảng cách và đỉnh thứ k

Với $l = \mathrm{lca}(u, v)$ : số cạnh trên đường là $dep_u + dep_v - 2 dep_l$ . Có trọng số thì thay độ sâu bằng tổng trọng số từ gốc $wd_v$ : $wd_u + wd_v - 2 wd_l$ . Đỉnh thứ $k$ (đếm từ 1, bắt đầu ở $u$ ) nằm trên đoạn lên nếu $k - 1 \le dep_u - dep_l$ , khi đó là tổ tiên cách $u$ đúng $k - 1$ bậc; ngược lại nằm trên đoạn xuống, là tổ tiên của $v$ cách $v$ đúng (độ dài đường $- (k - 1)$ ) bậc.

Ví dụKhoảng Cách Giữa Hai Đỉnh

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh cho bằng danh sách cạnh, $q \le 2 \cdot 10^5$ câu hỏi khoảng cách.

Lời giải. Gọi $l$ là LCA của $a$ và $b$ . Đường đi từ $a$ lên $l$ rồi xuống $b$ , nên khoảng cách là $dep_a + dep_b - 2\,dep_l$ .

Bước 1: BFS lấy cha và độ sâu. Cây cho bằng cạnh nên phải tự chọn gốc 1. BFS thay cho DFS đệ quy, để cây dạng đường dài $2 \cdot 10^5$ không làm tràn ngăn xếp. Cha của gốc là chính gốc.

C++

vector<ll> ord = {1};
up[0][1] = 1;
for (ll i = 0; i < (ll)ord.size(); i++) {
    ll u = ord[i];
    for (ll v : g[u])
        if (v != up[0][u]) {
            up[0][v] = u;
            dep[v] = dep[u] + 1;
            ord.push_back(v);
        }
}

Bước 2: bảng và hàm lca giống hệt ví dụ trước.

Bước 3: công thức khoảng cách.

C++

cout << dep[a] + dep[b] - 2 * dep[lca(a, b)] << '\n';

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 2e5 + 5, LG = 18;
ll n, q, dep[N], up[LG][N];
vector<ll> g[N];

ll lca(ll a, ll b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (ll j = LG - 1; j >= 0; j--)
        if (dep[a] - (1LL << j) >= dep[b]) a = up[j][a];
    if (a == b) return a;
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) a = up[j][a], b = up[j][b];
    return up[0][a];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 1; i < n; i++) {
        ll u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    vector<ll> ord = {1};
    up[0][1] = 1;
    for (ll i = 0; i < (ll)ord.size(); i++) {
        ll u = ord[i];
        for (ll v : g[u])
            if (v != up[0][u]) {
                up[0][v] = u;
                dep[v] = dep[u] + 1;
                ord.push_back(v);
            }
    }
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    while (q--) {
        ll a, b;
        cin >> a >> b;
        cout << dep[a] + dep[b] - 2 * dep[lca(a, b)] << '\n';
    }
}

Output2
5
2
0
3

Dựng $O(n \log n)$ , mỗi câu hỏi $O(\log n)$ .

Ví dụKhoảng Cách Và Đỉnh Thứ K

Đề. Cây $N \le 10^5$ đỉnh có trọng số cạnh, $M \le 10^5$ câu hỏi: tổng trọng số trên đường $(u, v)$ , hoặc đỉnh thứ $k$ trên đường từ $u$ tới $v$ .

Lời giải. Kèm $wd_v$ là tổng trọng số từ gốc tới $v$ ; tổng trên đường $(u, v)$ là $wd_u + wd_v - 2\,wd_l$ với $l$ là LCA. Đỉnh thứ $k$ trên đường đi tách theo hai đoạn: đoạn đi lên từ $u$ tới $l$ , và đoạn đi xuống từ $l$ tới $v$ .

Bước 1: BFS kèm tổng trọng số. wd tính cùng lúc với dep.

C++

for (pair<ll, ll> e : g[u])
    if (e.first != up[0][u]) {
        up[0][e.first] = u;
        dep[e.first] = dep[u] + 1;
        wd[e.first] = wd[u] + e.second;
        ord.push_back(e.first);
    }

Bước 2: nhảy lên đúng $k$ bậc. kth(v, k) nhảy theo từng bit của $k$ ; lca dùng nó cho pha nâng độ sâu.

C++

ll kth(ll v, ll k) {
    for (ll j = 0; j < LG; j++)
        if (k >> j & 1) v = up[j][v];
    return v;
}

Bước 3: đỉnh thứ $k$ . d1 là số cạnh từ $u$ lên LCA, len là độ dài cả đường. Đỉnh thứ $k$ cách $u$ đúng $k - 1$ cạnh; nếu còn trên đoạn đi lên thì là tổ tiên của $u$ , ngược lại là tổ tiên của $v$ cách $v$ đúng len - (k - 1) cạnh.

C++

ll d1 = dep[u] - dep[l], len = d1 + dep[v] - dep[l];
if (k - 1 <= d1) cout << kth(u, k - 1) << '\n';
else cout << kth(v, len - (k - 1)) << '\n';

Tổng trọng số tới $10^5 \cdot 10^9$ , dùng long long.

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, LG = 17;
ll n, m, dep[N], wd[N], up[LG][N];
vector<pair<ll, ll>> g[N];

ll kth(ll v, ll k) {
    for (ll j = 0; j < LG; j++)
        if (k >> j & 1) v = up[j][v];
    return v;
}

ll lca(ll a, ll b) {
    if (dep[a] < dep[b]) swap(a, b);
    a = kth(a, dep[a] - dep[b]);
    if (a == b) return a;
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) a = up[j][a], b = up[j][b];
    return up[0][a];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    vector<ll> ord = {1};
    up[0][1] = 1;
    for (ll i = 0; i < (ll)ord.size(); i++) {
        ll u = ord[i];
        for (pair<ll, ll> e : g[u])
            if (e.first != up[0][u]) {
                up[0][e.first] = u;
                dep[e.first] = dep[u] + 1;
                wd[e.first] = wd[u] + e.second;
                ord.push_back(e.first);
            }
    }
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    cin >> m;
    while (m--) {
        ll t, u, v;
        cin >> t >> u >> v;
        ll l = lca(u, v);
        if (t == 1) cout << wd[u] + wd[v] - 2 * wd[l] << '\n';
        else {
            ll k;
            cin >> k;
            ll d1 = dep[u] - dep[l], len = d1 + dep[v] - dep[l];
            if (k - 1 <= d1) cout << kth(u, k - 1) << '\n';
            else cout << kth(v, len - (k - 1)) << '\n';
        }
    }
}

Output21
4
1
7
3
31
6

Mỗi câu hỏi $O(\log N)$ .

Gộp min, max trên đường

Kèm vào bảng nhảy giá trị gộp của các cạnh trên đoạn nhảy: mn[j][v] là cạnh nhẹ nhất trên $2^j$ cạnh từ $v$ đi lên, mx[j][v] là cạnh nặng nhất. Khi nâng $u$ và $v$ trong lúc tìm LCA, mỗi bước nhảy gộp thêm giá trị của đoạn vừa nhảy. Đường đi gồm đúng các đoạn đã nhảy của cả hai bên cộng hai cạnh cuối tới LCA, nên kết quả gộp lại là đáp án. Phép gộp chỉ cần kết hợp: min, max, tổng, GCD đều được.

Ví dụCạnh Nhẹ Nhất Và Nặng Nhất

Đề. Cây $N \le 10^5$ đỉnh có trọng số cạnh, $K \le 10^5$ câu hỏi: cạnh nhẹ nhất và nặng nhất trên đường $(u, v)$ .

Lời giải. Bảng nhảy kèm giá trị: mn[j][v], mx[j][v] là cạnh nhẹ nhất, nặng nhất trong $2^j$ cạnh từ $v$ đi lên. Câu hỏi đi đúng hai pha của LCA, mỗi lần nhảy gộp thêm giá trị của đoạn vừa nhảy. Các đoạn đã nhảy của hai bên cộng hai cạnh cuối nối $a$ , $b$ với LCA phủ đúng mọi cạnh trên đường, không trùng không sót.

Bước 1: tầng 0 khi BFS. Tầng 0 là trọng số cạnh $v$ với cha. Gốc đặt mn = INF, mx = -INF để các bước nhảy “quá gốc” (dừng ở gốc) không làm sai min, max.

C++

up[0][1] = 1;
mn[0][1] = INF;
mx[0][1] = -INF;

C++

ll v = e.first;
up[0][v] = u;
mn[0][v] = mx[0][v] = e.second;
dep[v] = dep[u] + 1;
ord.push_back(v);

Bước 2: ghép hai nửa. Tầng $j$ gộp hai nửa liền nhau, giống cách dựng up.

C++

ll p = up[j - 1][v];
up[j][v] = up[j - 1][p];
mn[j][v] = min(mn[j - 1][v], mn[j - 1][p]);
mx[j][v] = max(mx[j - 1][v], mx[j - 1][p]);

Bước 3: hai pha có gộp. Pha một nâng $a$ về độ sâu của $b$ , gộp từng đoạn nhảy. Nếu $a = b$ thì một đầu là tổ tiên của đầu kia, xong. Ngược lại pha hai nâng cả hai, gộp đoạn của cả hai bên, rồi gộp nốt hai cạnh cuối up[0] của $a$ và $b$ .

C++

if (a != b) {
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) {
            lo = min({lo, mn[j][a], mn[j][b]});
            hi = max({hi, mx[j][a], mx[j][b]});
            a = up[j][a];
            b = up[j][b];
        }
    lo = min({lo, mn[0][a], mn[0][b]});
    hi = max({hi, mx[0][a], mx[0][b]});
}

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, LG = 17, INF = 1e18;
ll n, k, dep[N], up[LG][N], mn[LG][N], mx[LG][N];
vector<pair<ll, ll>> g[N];

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;
    for (ll i = 1; i < n; i++) {
        ll a, b, w;
        cin >> a >> b >> w;
        g[a].push_back({b, w});
        g[b].push_back({a, w});
    }
    vector<ll> ord = {1};
    up[0][1] = 1;
    mn[0][1] = INF;
    mx[0][1] = -INF;
    for (ll i = 0; i < (ll)ord.size(); i++) {
        ll u = ord[i];
        for (pair<ll, ll> e : g[u])
            if (e.first != up[0][u]) {
                ll v = e.first;
                up[0][v] = u;
                mn[0][v] = mx[0][v] = e.second;
                dep[v] = dep[u] + 1;
                ord.push_back(v);
            }
    }
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) {
            ll p = up[j - 1][v];
            up[j][v] = up[j - 1][p];
            mn[j][v] = min(mn[j - 1][v], mn[j - 1][p]);
            mx[j][v] = max(mx[j - 1][v], mx[j - 1][p]);
        }
    cin >> k;
    while (k--) {
        ll a, b;
        cin >> a >> b;
        ll lo = INF, hi = -INF;
        if (dep[a] < dep[b]) swap(a, b);
        for (ll j = LG - 1; j >= 0; j--)
            if (dep[a] - (1LL << j) >= dep[b]) {
                lo = min(lo, mn[j][a]);
                hi = max(hi, mx[j][a]);
                a = up[j][a];
            }
        if (a != b) {
            for (ll j = LG - 1; j >= 0; j--)
                if (up[j][a] != up[j][b]) {
                    lo = min({lo, mn[j][a], mn[j][b]});
                    hi = max({hi, mx[j][a], mx[j][b]});
                    a = up[j][a];
                    b = up[j][b];
                }
            lo = min({lo, mn[0][a], mn[0][b]});
            hi = max({hi, mx[0][a], mx[0][b]});
        }
        cout << lo << ' ' << hi << '\n';
    }
}

Output6 10
3 12
4 12
8 10

Dựng $O(N \log N)$ , mỗi câu hỏi $O(\log N)$ .

Cộng trên đường bằng mảng hiệu

Muốn cộng 1 cho mọi đỉnh trên đường $(u, v)$ rồi cuối cùng mới đọc kết quả, dùng mảng hiệu trên cây: cộng 1 vào $u$ và $v$ , trừ 1 ở $l = \mathrm{lca}(u, v)$ và trừ 1 ở cha của $l$ . Giá trị thật của một đỉnh là tổng các dấu trong cây con của nó. Một đỉnh $x$ trên đoạn từ $u$ lên $l$ có $u$ trong cây con nên nhận $+1$ ; $l$ nhận $+1 + 1 - 1 = 1$ ; cha của $l$ trở lên thì các dấu triệt tiêu hết. Cộng trên cạnh thay vì đỉnh thì trừ 2 ở $l$ và không đụng tới cha của $l$ , mỗi cạnh ứng với đỉnh con của nó.

Cam là hai đầu đường, xanh dương là LCA, đỏ là cha của LCA. Sau đó cộng dồn từ tầng sâu nhất lên.

Hỏi nhanh

Đánh dấu đường $(u, v)$ bằng $+1$ ở $u$ và $v$ , $-1$ ở $l = \mathrm{lca}(u, v)$ . Còn thiếu dấu nào để mỗi đỉnh trên đường nhận đúng 1?

Ví dụDấu Chân Trên Các Đỉnh

Đề. Cây $n \le 2 \cdot 10^5$ đỉnh và $m \le 2 \cdot 10^5$ đường đi. Với mỗi đỉnh, đếm số đường đi chứa nó.

Lời giải. Cộng hiệu trên cây: mỗi đường $(u, v)$ đặt bốn dấu, $+1$ ở $u$ và $v$ , $-1$ ở LCA $l$ và ở cha của $l$ . Sau khi cộng dồn từ lá lên, giá trị ở mỗi đỉnh là tổng dấu trong cây con của nó, và bốn dấu trên làm tổng đó bằng 1 đúng với các đỉnh nằm trên đường: đỉnh trên đoạn $u..l$ hoặc $v..l$ nhận một dấu $+1$ (riêng $l$ nhận hai dấu $+1$ và một dấu $-1$ ), đỉnh từ cha của $l$ trở lên nhận đủ cả bốn dấu, tổng 0.

Bước 1: BFS và bảng. Như ví dụ trước, nhưng ở đây up[0][1] = 0 (mảng toàn cục sẵn bằng 0): ô 0 là lính canh nhận dấu $-1$ khi LCA là gốc, và không bao giờ được in. up[j][0] = 0 nên mọi bước nhảy vượt gốc dừng ở 0; hàm lca vẫn đúng vì chỉ nhảy khi còn đủ độ sâu và khi hai tổ tiên còn khác nhau.

Bước 2: đặt dấu cho mỗi đường.

C++

ll l = lca(u, v);
c[u]++;
c[v]++;
c[l]--;
c[up[0][l]]--;

Bước 3: cộng dồn một lần. Duyệt ord từ cuối lên là duyệt con trước cha; cộng giá trị của mỗi đỉnh vào cha.

C++

for (ll i = n - 1; i >= 1; i--) c[up[0][ord[i]]] += c[ord[i]];

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 2e5 + 5, LG = 18;
ll n, m, dep[N], up[LG][N], c[N];
vector<ll> g[N];

ll lca(ll a, ll b) {
    if (dep[a] < dep[b]) swap(a, b);
    for (ll j = LG - 1; j >= 0; j--)
        if (dep[a] - (1LL << j) >= dep[b]) a = up[j][a];
    if (a == b) return a;
    for (ll j = LG - 1; j >= 0; j--)
        if (up[j][a] != up[j][b]) a = up[j][a], b = up[j][b];
    return up[0][a];
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;
    for (ll i = 1; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<ll> ord = {1};
    for (ll i = 0; i < (ll)ord.size(); i++) {
        ll u = ord[i];
        for (ll v : g[u])
            if (v != up[0][u]) {
                up[0][v] = u;
                dep[v] = dep[u] + 1;
                ord.push_back(v);
            }
    }
    for (ll j = 1; j < LG; j++)
        for (ll v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    while (m--) {
        ll u, v;
        cin >> u >> v;
        ll l = lca(u, v);
        c[u]++;
        c[v]++;
        c[l]--;
        c[up[0][l]]--;
    }
    for (ll i = n - 1; i >= 1; i--) c[up[0][ord[i]]] += c[ord[i]];
    for (ll v = 1; v <= n; v++) cout << c[v] << ' ';
    cout << '\n';
}

Output3 4 4 2 2 3 2

$O((n + m) \log n)$ , phần $\log$ do LCA.

Thứ tự Euler và RMQ

Ghi lại đỉnh mỗi lần DFS đi qua nó: khi vào, và mỗi lần quay về từ một con. Dãy dài $2n - 1$ . Giữa lần đầu gặp $u$ và lần đầu gặp $v$ trong dãy, DFS đi từ $u$ qua LCA rồi xuống $v$ và không lên cao hơn LCA, nên LCA chính là đỉnh có độ sâu nhỏ nhất trong đoạn đó. Bảng thưa (bài 22) trên dãy này trả lời mỗi câu hỏi trong $O(1)$ sau $O(n \log n)$ tiền xử lý: hợp khi số câu hỏi rất lớn.

Ví dụXOR Của Hàng Triệu LCA

Đề. Cây $n \le 10^5$ đỉnh gốc 1. Có $q \le 10^7$ câu hỏi LCA sinh bằng công thức tuyến tính từ sáu tham số; in XOR của mọi đáp án.

Lời giải. $10^7$ câu hỏi nhân $\log n$ là quá nhiều, nên cần LCA trong $O(1)$ mỗi câu. Dùng thứ tự Euler: đi DFS và ghi lại đỉnh mỗi lần đi qua, kể cả lúc quay về từ con. Giữa lần đầu gặp $u$ và lần đầu gặp $v$ trong dãy, đỉnh nông nhất chính là LCA. Bài thành min trên đoạn của một dãy cố định, trả lời bằng bảng thưa (bài 22).

Bước 1: dãy Euler. eu dài $2n - 1$ ; fst[v] là lần đầu gặp $v$ . Đệ quy sâu tới $10^5$ là mức thường chạy được.

C++

void dfs(ll u, ll p) {
    eu[++k] = u;
    fst[u] = k;
    for (ll v : g[u])
        if (v != p) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
            eu[++k] = u;
        }
}

Bước 2: bảng thưa theo độ sâu. st[j][i] là đỉnh nông nhất trong $2^j$ phần tử bắt đầu ở $i$ của eu; better chọn đỉnh nông hơn.

C++

for (ll i = 1; i <= k; i++) st[0][i] = eu[i];
for (ll j = 1; j < LG; j++)
    for (ll i = 1; i + (1 << j) - 1 <= k; i++) st[j][i] = better(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);

Bước 3: LCA trong $O(1)$ . Đoạn $[fst_u, fst_v]$ phủ bằng hai khối dài $2^j$ chồng lên nhau; lấy min mà chồng lên nhau không sao.

C++

ll lca(ll u, ll v) {
    ll l = fst[u], r = fst[v];
    if (l > r) swap(l, r);
    ll j = lg[r - l + 1];
    return better(st[j][l], st[j][r - (1 << j) + 1]);
}

Bước 4: sinh câu hỏi. u * uj tới $10^5 \cdot 10^9$ , phải là long long.

C++

for (ll i = 1; i <= q; i++) {
    ans ^= lca(u, v);
    u = (u * uj + ua) % n + 1;
    v = (v * vj + va) % n + 1;
}

Code đầy đủ

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 1e5 + 5, M = 2 * N, LG = 18;
ll n, q, k, dep[N], fst[N], eu[M], lg[M], st[LG][M];
vector<ll> g[N];

void dfs(ll u, ll p) {
    eu[++k] = u;
    fst[u] = k;
    for (ll v : g[u])
        if (v != p) {
            dep[v] = dep[u] + 1;
            dfs(v, u);
            eu[++k] = u;
        }
}

ll better(ll a, ll b) {
    return dep[a] < dep[b] ? a : b;
}

ll lca(ll u, ll v) {
    ll l = fst[u], r = fst[v];
    if (l > r) swap(l, r);
    ll j = lg[r - l + 1];
    return better(st[j][l], st[j][r - (1 << j) + 1]);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> q;
    for (ll i = 1; i < n; i++) {
        ll a, b;
        cin >> a >> b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    dfs(1, 0);
    for (ll i = 2; i <= k; i++) lg[i] = lg[i / 2] + 1;
    for (ll i = 1; i <= k; i++) st[0][i] = eu[i];
    for (ll j = 1; j < LG; j++)
        for (ll i = 1; i + (1 << j) - 1 <= k; i++) st[j][i] = better(st[j - 1][i], st[j - 1][i + (1 << (j - 1))]);
    ll u, v, uj, vj, ua, va;
    cin >> u >> v >> uj >> vj >> ua >> va;
    ll ans = 0;
    for (ll i = 1; i <= q; i++) {
        ans ^= lca(u, v);
        u = (u * uj + ua) % n + 1;
        v = (v * vj + va) % n + 1;
    }
    cout << ans << '\n';
}

Input7 5
1 2
1 3
2 4
2 5
3 6
6 7
4 5 2 3 0 1

Output2

Dựng $O(n \log n)$ , mỗi câu hỏi hai lần đọc bảng.

Khi đi thi

Mọi câu hỏi “trên đường $(u, v)$ ” trên cây tĩnh: tách tại LCA thành hai đoạn dọc; độ dài, tổng tiền tố từ gốc, đỉnh thứ $k$ đều làm được với bảng nhảy.
Nhảy nhị phân đủ cho $10^5$ đến $10^6$ câu hỏi; hàng chục triệu câu hỏi thì Euler cộng bảng thưa. Có cập nhật trên đường thì cần phân rã nặng nhẹ (bài 58).
Cộng trên đường rồi đọc cuối cùng: mảng hiệu trên cây với bốn dấu cho đỉnh, ba dấu cho cạnh. Chú ý cha của gốc.

Tóm tắt

LCA bằng nhảy nhị phân: cân độ sâu, rồi nhảy từ tầng cao khi tổ tiên còn khác, đáp án là cha chung.
Khoảng cách $dep_u + dep_v - 2dep_l$ ; tổng trọng số dùng tổng từ gốc; đỉnh thứ $k$ chọn đoạn lên hay đoạn xuống.
Gộp min, max theo từng bước nhảy cho câu hỏi trên đường.
Mảng hiệu trên cây: $+1$ ở hai đầu, $-1$ ở LCA và cha của LCA, rồi cộng dồn theo cây con.
LCA là đỉnh nông nhất giữa hai lần xuất hiện đầu trong thứ tự Euler: RMQ $O(1)$ .

Bài tập

Một Nhánh Có Đủ Gầncanuc80k3607Thay mỗi đỉnh bằng cha của nó (trừ gốc), lấy đỉnh sâu nhất

u

; có lời giải khi mọi đỉnh đã thay đều là tổ tiên của

u

LQDOJ

Đoạn Chung Dài Nhấtcanuc80k3608Với mỗi cách chọn đỉnh đích

f

trong ba đỉnh, số đỉnh chung của hai đường tới

f

là

(d(a, f) + d(b, f) - d(a, b)) / 2 + 1

; lấy lớn nhất.

LQDOJ

Cạnh Tạm Thờicanuc80k3609Đường đi dùng cạnh mới hay không: thử ba khoảng cách

d(a, b)

d(a, x) + 1 + d(y, b)

d(a, y) + 1 + d(x, b)

; được khi một trong số đó không quá

k

và cùng tính chẵn lẻ với

k

LQDOJ

Gốc Ẩn Và Một Truy Vấncanuc80k3613Tìm gốc là đỉnh không có cha, rồi LCA như thường.

LQDOJ

Số Đỉnh Trên Đườngcanuc80k3615Thêm cạnh

(a, b)

tạo chu trình dài

d(a, b) + 1

LQDOJ

LCA Khi Đổi Gốccanuc80k3619LCA khi gốc là

r

là đỉnh sâu nhất trong ba đỉnh

\mathrm{lca}(u, v)

\mathrm{lca}(u, r)

\mathrm{lca}(v, r)

tính với gốc 1.

LQDOJ

Lưu Lượng Qua Các Cạnhcanuc80k3620Mảng hiệu trên cạnh:

+1

ở hai đầu,

-2

ở LCA; cộng dồn theo cây con, cạnh ứng với đỉnh con.

LQDOJ

Các Phòng Cách Đềucanuc80k3621Đỉnh cách đều

a, b

chỉ có khi

d(a, b)

chẵn; lấy trung điểm bằng đỉnh thứ

k

, đếm theo kích thước cây con sau khi bỏ nhánh về phía

a

và

b

LQDOJ

Tâm Của Ba Đỉnhcanuc80k3622Tâm của ba đỉnh là một trong ba LCA từng cặp; thử từng ứng viên, kiểm khoảng cách tới ba đỉnh bằng nhau.

LQDOJ

Các Đỉnh Cùng Trên Một Đườngcanuc80k3623Lấy đỉnh sâu nhất làm một đầu, đầu kia là đỉnh xa nó nhất trong tập; mọi đỉnh của tập phải thỏa

d(a, x) + d(x, b) = d(a, b)

LQDOJ

Đường Kính Sau Mỗi Lần Thêmcanuc80k3626Giữ hai đầu đường kính; thêm đỉnh mới

x

thì đường kính mới có một đầu là

x

khi

d(x, a)

hoặc

d(x, b)

vượt đường kính cũ.

LQDOJ

Ngày Kết Nối Đầu Tiêncanuc80k3627Thêm đường theo ngày bằng DSU, dựng cây Kruskal hoặc rừng với trọng số là ngày; đáp án là cạnh có ngày lớn nhất trên đường

(a, b)

, hoặc

-1

nếu khác thành phần.

LQDOJ

Khoảng Cách Sau Khi Đổi Một Màucanuc80k3630Ngoại tuyến: với mỗi câu hỏi tách thành ba điểm

u

v

, LCA; DFS giữ số cạnh và tổng độ dài theo từng màu trên đường từ gốc.

LQDOJ

Mã Nhỏ Nhất Trên Đường Đicanuc80k3633Mỗi tầng nhảy giữ 10 mã nhỏ nhất trên đoạn; gộp hai danh sách đã sắp và cắt còn 10.

LQDOJ

Đọc thêm

Các phương pháp giải bài toán LCAVNOI WikiNhiều cách tìm LCA và ứng dụng, viết bằng tiếng Việt.
Lowest Common Ancestor - Binary Liftingcp-algorithmsCài đặt bằng nhảy nhị phân và thời điểm vào ra.
Lowest Common Ancestorcp-algorithmsĐưa LCA về RMQ trên thứ tự Euler.
Binary JumpingUSACO GuideLCA bằng nhảy nhị phân kèm bài luyện.