Lowest Common Ancestor

Nâng hai đỉnh

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$:

1. 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.
2. 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.
3. Kết thúc, $a$ và $b$ là hai con khác nhau của LCA, đáp án là up[0][a].

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];
}

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}$.

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.

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];
}

#include <bits/stdc++.h>
using namespace std;
#define 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';
    }
}

ChạyInput8 5
1 1 2 2 3 6 6
4 5
4 7
7 8
3 8
1 5

Output2
1
6
3
1

Độ phức tạp: dựng $O(n \log n)$, mỗi câu hỏi $O(\log n)$.

Khoảng cách, đỉ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ó 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 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.

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.

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.

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.

#include <bits/stdc++.h>
using namespace std;
#define 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';
        }
    }
}

+16 dòngChạyInput8
1 2 4
1 3 7
2 4 3
2 5 6
3 6 5
6 7 2
6 8 9
7
1 4 7
2 4 7 1
2 4 7 3
2 4 7 6
2 7 5 3
1 8 5
2 6 6 1

Output21
4
1
7
3
31
6

Độ phức tạp: mỗi câu hỏi $O(\log N)$.

Gộp 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.

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

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.

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$.

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]});
}

#include <bits/stdc++.h>
using namespace std;
#define 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';
    }
}

+12 dòngChạyInput7
1 2 8
1 3 3
2 4 6
2 5 10
3 6 4
6 7 12
4
4 5
4 7
3 7
1 5

Output6 10
3 12
4 12
8 10

Độ phức tạp: dựng $O(N \log N)$, mỗi câu hỏi $O(\log N)$.

Mảng hiệu trên cây

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ó.

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.

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.

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

#include <bits/stdc++.h>
using namespace std;
#define 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';
}

+12 dòngChạyInput7 5
1 2
1 3
2 4
2 5
3 6
6 7
4 5
4 7
2 6
3 3
5 7

Output3 4 4 2 2 3 2

Độ phức tạp: $O((n + m) \log n)$, phần $\log$ do LCA.

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.

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.

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.

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.

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

#include <bits/stdc++.h>
using namespace std;
#define 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';
}

ChạyInput7 5
1 2
1 3
2 4
2 5
3 6
6 7
4 5 2 3 0 1

Output2

Độ phức tạp: dựng $O(n \log n)$, mỗi câu hỏi hai lần đọc bảng.

So với nhảy nhị phân khi số câu hỏi rất lớn:

Euler cộng bảng thưa nhanh hơn khoảng 4 lần. Với vài trăm nghìn câu hỏi thì nhảy nhị phân đủ và ngắn hơn để viết; hàng triệu câu hỏi trở lên mới đáng dùng Euler.