Advanced Trees

Cây Cartesian

Với dãy giá trị đôi một khác nhau, cây Cartesian (theo cực tiểu) có gốc là vị trí nhỏ nhất, cây con trái dựng từ đoạn bên trái, cây con phải từ đoạn bên phải. Duyệt trung thứ tự ra đúng thứ tự vị trí, và giá trị cha nhỏ hơn giá trị con. Cực tiểu của đoạn $[l, r]$ là LCA của $l$ và $r$.

Dựng trong $O(n)$ bằng ngăn xếp đơn điệu chứa đường biên phải của cây: thêm $i$, bỏ khỏi ngăn xếp mọi phần tử lớn hơn $a_i$; phần tử cuối cùng bị bỏ trở thành con trái của $i$, và $i$ thành con phải của đỉnh ngăn xếp còn lại. Các phần tử bị bỏ khác giữ nguyên cha cũ.

Ví dụCây Phân Hoạch Theo Giá Trị Nhỏ Nhất

Đề. Dãy $n \le 10^6$ giá trị đôi một khác nhau. In cha của mỗi vị trí trong cây Cartesian nhỏ nhất (gốc có cha là chính nó).

Lời giải. Dựng bằng ngăn xếp biên phải như ở trên. st[0..top-1] là biên phải của cây đã dựng cho các phần tử $0..i-1$, giá trị tăng dần từ đáy lên đỉnh. Thêm $i$: bỏ khỏi ngăn xếp mọi phần tử lớn hơn $a_i$; phần tử bị bỏ cuối cùng thành con trái của $i$, còn $i$ thành con phải của phần tử đang ở đỉnh ngăn xếp.

last là phần tử cuối bị bỏ: nó và cả cây con của nó lớn hơn $a_i$ và nằm bên trái $i$, nên trở thành cây con trái của $i$; các phần tử bị bỏ trước đó vẫn là con của nhau như cũ. Ngăn xếp rỗng thì $i$ tạm là gốc; nếu sau này có phần tử nhỏ hơn đến, par[i] được sửa lại khi $i$ là last của lần bỏ đó.

for (int i = 0; i < n; i++) {
    int last = -1;
    while (top && a[st[top - 1]] > a[i]) last = st[--top];
    if (last != -1) par[last] = i;
    par[i] = top ? st[top - 1] : i;
    st[top++] = i;
}
par[st[0]] = st[0];

Đáy ngăn xếp cuối cùng là phần tử nhỏ nhất, tức gốc, có cha là chính nó theo yêu cầu đề.

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

const int N = 1e6 + 5;
int n, a[N], par[N], st[N], top;

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

    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) {
        int last = -1;
        while (top && a[st[top - 1]] > a[i]) last = st[--top];
        if (last != -1) par[last] = i;
        par[i] = top ? st[top - 1] : i;
        st[top++] = i;
    }
    par[st[0]] = st[0];
    for (int i = 0; i < n; i++) cout << par[i] << ' ';
    cout << '\n';
}

Input5
8 3 6 1 5

Output1 3 1 3 3

Mỗi chỉ số vào và ra ngăn xếp một lần: $O(n)$.

Ví dụTổng Các Giá Trị Nhỏ Nhất

Đề. Hoán vị độ dài $n \le 2 \cdot 10^5$. Tính tổng cực tiểu của mọi đoạn con.

Lời giải. Đếm theo đóng góp: $a_i$ là cực tiểu của đúng các đoạn chứa $i$ và nằm trong cây con của $i$ trên cây Cartesian. Cây con đó là khoảng $(L_i, R_i)$, với $L_i$, $R_i$ là vị trí gần nhất bên trái, bên phải có giá trị nhỏ hơn. Đầu trái chọn trong $(L_i, i]$, đầu phải trong $[i, R_i)$, nên đóng góp là $a_i (i - L_i)(R_i - i)$. Không cần dựng cây: $L$, $R$ tìm bằng ngăn xếp đơn điệu.

Bước 1: nhỏ hơn gần nhất bên trái. Sau khi bỏ mọi phần tử lớn hơn $a_i$, đỉnh ngăn xếp là phần tử nhỏ hơn gần nhất bên trái; rỗng thì $L_i = 0$. Lượt phải sang trái làm đối xứng cho $R_i$, rỗng thì $R_i = n + 1$.

for (int i = 1; i <= n; i++) {
    while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
    L[i] = st.empty() ? 0 : st.back();
    st.push_back(i);
}

Bước 2: cộng đóng góp. Đóng góp tới $2 \cdot 10^5 \cdot 10^5 \cdot 10^5$, nên ép sang long long trước khi nhân.

for (int i = 1; i <= n; i++) ans += (ll)a[i] * (i - L[i]) * (R[i] - i);

Hoán vị nên không có hai giá trị bằng nhau; với dãy có giá trị trùng thì một bên phải dùng >, bên kia >= để mỗi đoạn chỉ được tính cho đúng một vị trí.

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

const int N = 2e5 + 5;
int n, a[N], L[N], R[N];

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

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    vector<int> st;
    for (int i = 1; i <= n; i++) {
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        L[i] = st.empty() ? 0 : st.back();
        st.push_back(i);
    }
    st.clear();
    for (int i = n; i >= 1; i--) {
        while (!st.empty() && a[st.back()] > a[i]) st.pop_back();
        R[i] = st.empty() ? n + 1 : st.back();
        st.push_back(i);
    }
    ll ans = 0;
    for (int i = 1; i <= n; i++) ans += (ll)a[i] * (i - L[i]) * (R[i] - i);
    cout << ans << '\n';
}

Input5
3 1 5 2 4

Output28

$O(n)$.

Cây Kruskal dựng lại

Chạy Kruskal (hay thêm cạnh theo thời gian) với DSU, nhưng mỗi lần hợp hai thành phần gốc $r_a$, $r_b$ thì tạo đỉnh mới $t$ mang giá trị là trọng số (thời điểm) của cạnh, có hai con $r_a$, $r_b$. Được một cây với $n$ lá là các đỉnh gốc và $n - 1$ đỉnh trong. Giá trị tăng dần khi đi lên, nên:

• Thời điểm sớm nhất $u$, $v$ liên thông (hay ngưỡng nhỏ nhất để nối) là giá trị tại $\operatorname{lca}(u, v)$.
• Tập đỉnh nối được với $u$ khi chỉ dùng cạnh không quá $W$ là các lá trong cây con của tổ tiên cao nhất của $u$ có giá trị không quá $W$ (tìm bằng nhảy nhị phân).

Đỉnh mới có số hiệu lớn hơn hai con, nên duyệt số hiệu giảm dần là đi từ trên xuống, khỏi DFS.

Ví dụNgày Kết Nối Đầu Tiên

Đề. $n, m, q \le 2 \cdot 10^5$. Ngày $i$ xây đường thứ $i$. Mỗi truy vấn $(u, v)$ hỏi ngày sớm nhất hai thành phố liên thông, 0 nếu $u = v$, $-1$ nếu không bao giờ.

Lời giải. Dựng cây Kruskal theo thứ tự ngày: mỗi lần đường mới nối hai thành phần, tạo đỉnh mới mang số ngày, hai con là gốc của hai thành phần. Đỉnh càng cao mang ngày càng lớn, và $u$, $v$ liên thông lần đầu vào ngày ghi ở LCA của chúng. Hai đỉnh ở hai cây khác nhau thì không bao giờ liên thông.

Bước 1: dựng cây Kruskal. dsu[x] trỏ tới đỉnh cây Kruskal đang là gốc thành phần chứa $x$. Hợp $a$, $b$: tạo tot, gán dsu[a] = dsu[b] = tot và đặt tot làm cha của cả hai; val[tot] là ngày.

a = find(a), b = find(b);
if (a == b) continue;
++tot;
val[tot] = i;
dsu[a] = dsu[b] = tot;
up[0][a] = up[0][b] = tot;

Bước 2: độ sâu. Đỉnh mới luôn có số hiệu lớn hơn hai con, nên duyệt x từ tot xuống 1 là đi từ trên xuống: cha đã có dep trước con. Đỉnh không có cha là gốc của một cây, đặt up[0][x] = x. lca bằng nhảy nhị phân như bài 36.

for (int x = tot; x >= 1; x--) {
    if (!up[0][x]) up[0][x] = x, dep[x] = 0;
    else dep[x] = dep[up[0][x]] + 1;
}

Bước 3: trả lời. $u = v$ in 0; khác thành phần in $-1$; còn lại in val của LCA.

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

const int N = 4e5 + 5, LG = 19;
int n, m, q, tot, dsu[N], val[N], up[LG][N], dep[N];

int find(int u) {
    while (dsu[u] != u) u = dsu[u] = dsu[dsu[u]];
    return u;
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j = LG - 1; j >= 0; j--)
        if (dep[u] - (1 << j) >= dep[v]) u = up[j][u];
    if (u == v) return u;
    for (int j = LG - 1; j >= 0; j--)
        if (up[j][u] != up[j][v]) u = up[j][u], v = up[j][v];
    return up[0][u];
}

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

    cin >> n >> m >> q;
    for (int i = 1; i < 2 * n; i++) dsu[i] = i;
    tot = n;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        a = find(a), b = find(b);
        if (a == b) continue;
        ++tot;
        val[tot] = i;
        dsu[a] = dsu[b] = tot;
        up[0][a] = up[0][b] = tot;
    }
    for (int x = tot; x >= 1; x--) {
        if (!up[0][x]) up[0][x] = x, dep[x] = 0;
        else dep[x] = dep[up[0][x]] + 1;
    }
    for (int j = 1; j < LG; j++)
        for (int x = 1; x <= tot; x++) up[j][x] = up[j - 1][up[j - 1][x]];
    while (q--) {
        int u, v;
        cin >> u >> v;
        if (u == v) cout << 0 << '\n';
        else if (find(u) != find(v)) cout << -1 << '\n';
        else cout << val[lca(u, v)] << '\n';
    }
}

Input5 3 4
1 2
3 4
2 3
1 1
1 2
1 4
1 5

Output0
1
3
-1

Dựng $O(m\,\alpha(n) + n \log n)$, mỗi truy vấn $O(\log n)$.

Cây ảo

Nhiều truy vấn, mỗi truy vấn chỉ quan tâm $k$ đỉnh, tổng $k$ nhỏ: DP trên cả cây mỗi truy vấn là $O(nq)$. Cây ảo gồm các đỉnh được hỏi cùng LCA của mọi cặp, và nối mỗi đỉnh với tổ tiên gần nhất trong tập đó. Nó có không quá $2k - 1$ đỉnh và giữ nguyên quan hệ tổ tiên, nên DP trên nó thay cho DP trên cây gốc.

Dựng: sắp các đỉnh theo thứ tự DFS, thêm gốc; duyệt với ngăn xếp chứa một đường từ gốc xuống. Với đỉnh mới $v$, lấy $l = \operatorname{lca}(v, \text{đỉnh ngăn xếp})$; bỏ khỏi ngăn xếp (và nối cạnh ảo) những đỉnh sâu hơn $l$, chèn $l$ nếu chưa có, rồi đẩy $v$. Tổng $O(k \log n)$ cho việc sắp và LCA. Thông tin trên cạnh ảo (như trọng số nhỏ nhất trên đường) phải tính từ cây gốc, thường là tiền xử lý dọc đường từ gốc.

Ví dụCắt Đường Bảo Vệ Gốc

Đề. Cây $n \le 2.5 \cdot 10^5$ đỉnh có trọng số cạnh, gốc 1. Tới $5 \cdot 10^5$ truy vấn, tổng số đỉnh đặc biệt tới $5 \cdot 10^5$. Mỗi truy vấn: phá cạnh với tổng chi phí nhỏ nhất để gốc không tới được đỉnh đặc biệt nào.

Lời giải. $mn_v$ là cạnh rẻ nhất trên đường từ gốc tới $v$, tính một lần cho cả cây. Gọi $f(v)$ là chi phí nhỏ nhất để cắt mọi đỉnh đặc biệt trong cây con của $v$ khỏi gốc. Nếu $v$ đặc biệt thì phải cắt trên đường từ gốc tới $v$, rẻ nhất là $mn_v$. Ngược lại có hai lựa chọn: cắt một lần ở trên $v$ ($mn_v$), hoặc lo riêng từng con, $\sum_c f(c)$. Quy hoạch động này chỉ cần các đỉnh đặc biệt và LCA của chúng, nên mỗi truy vấn dựng cây ảo $O(k)$ đỉnh và chạy trên đó.

Bước 1: duyệt cây một lần. Lấy $u$ ra khỏi ngăn xếp thì gán dfn[u] rồi đẩy các con; thứ tự lấy ra là một thứ tự DFS hợp lệ. mn[v] lấy min dọc đường đi xuống; gốc có mn = INF vì không cắt được phía trên gốc.

up[0][v] = u, dep[v] = dep[u] + 1, mn[v] = min(mn[u], (ll)e.second);

Bước 2: dựng cây ảo. Sắp đỉnh đặc biệt theo dfn, ngăn xếp s giữ một đường từ gốc xuống. Với $v$ mới, l = lca(v, s.back()). Mọi đỉnh trên ngăn xếp sâu hơn $l$ đã xong cây con, được nối với đỉnh dưới nó rồi bỏ đi. Nếu đỉnh còn lại trên cùng không phải $l$ thì $l$ là đỉnh rẽ nhánh mới: nối $l$ với đỉnh đó và thay nó bằng $l$. Rồi đẩy $v$.

for (int v : h) {
    int l = lca(v, s.back());
    while (s.size() >= 2 && dep[s[s.size() - 2]] >= dep[l]) {
        vt[s[s.size() - 2]].push_back(s.back());
        s.pop_back();
    }
    if (s.back() != l) {
        vt[l].push_back(s.back());
        s.back() = l;
        nodes.push_back(l);
    }
    s.push_back(v);
    nodes.push_back(v);
}

Bước 3: quy hoạch động trên cây ảo. nodes sắp theo dfn và bỏ trùng; duyệt ngược thì con xong trước cha. Đỉnh đặc biệt lấy mn[v]; gốc chỉ có thể lo từng con; đỉnh khác lấy min hai lựa chọn.

for (int i = (int)nodes.size() - 1; i >= 0; i--) {
    int v = nodes[i];
    ll sum = 0;
    for (int c : vt[v]) sum += f[c];
    if (key[v]) f[v] = mn[v];
    else if (v == 1) f[v] = sum;
    else f[v] = min(mn[v], sum);
}

Cuối mỗi truy vấn xóa vt và key của đúng các đỉnh đã dùng, không xóa cả mảng.

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

const int N = 2.5e5 + 5, LG = 18;
const ll INF = 1e18;
int n, tim, dfn[N], dep[N], up[LG][N];
ll mn[N], f[N];
bool key[N];
vector<pair<int, int>> adj[N];
vector<int> vt[N];

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int j = LG - 1; j >= 0; j--)
        if (dep[u] - (1 << j) >= dep[v]) u = up[j][u];
    if (u == v) return u;
    for (int j = LG - 1; j >= 0; j--)
        if (up[j][u] != up[j][v]) u = up[j][u], v = up[j][v];
    return up[0][u];
}

bool byDfn(int a, int b) {
    return dfn[a] < dfn[b];
}

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

    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<int> st = {1};
    up[0][1] = 1, mn[1] = INF;
    while (!st.empty()) {
        int u = st.back();
        st.pop_back();
        dfn[u] = ++tim;
        for (pair<int, int> e : adj[u])
            if (e.first != up[0][u]) {
                int v = e.first;
                up[0][v] = u, dep[v] = dep[u] + 1, mn[v] = min(mn[u], (ll)e.second);
                st.push_back(v);
            }
    }
    for (int j = 1; j < LG; j++)
        for (int v = 1; v <= n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
    int q;
    cin >> q;
    while (q--) {
        int k;
        cin >> k;
        vector<int> h(k);
        for (int i = 0; i < k; i++) cin >> h[i], key[h[i]] = 1;
        sort(h.begin(), h.end(), byDfn);
        vector<int> nodes = {1}, s = {1};
        for (int v : h) {
            int l = lca(v, s.back());
            while (s.size() >= 2 && dep[s[s.size() - 2]] >= dep[l]) {
                vt[s[s.size() - 2]].push_back(s.back());
                s.pop_back();
            }
            if (s.back() != l) {
                vt[l].push_back(s.back());
                s.back() = l;
                nodes.push_back(l);
            }
            s.push_back(v);
            nodes.push_back(v);
        }
        while (s.size() >= 2) {
            vt[s[s.size() - 2]].push_back(s.back());
            s.pop_back();
        }
        sort(nodes.begin(), nodes.end(), byDfn);
        nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());
        for (int i = (int)nodes.size() - 1; i >= 0; i--) {
            int v = nodes[i];
            ll sum = 0;
            for (int c : vt[v]) sum += f[c];
            if (key[v]) f[v] = mn[v];
            else if (v == 1) f[v] = sum;
            else f[v] = min(mn[v], sum);
        }
        cout << f[1] << '\n';
        for (int v : nodes) vt[v].clear(), key[v] = 0;
    }
}

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

Output5
7
5

Tổng $O(\sum k \log n)$.

Cây cầu

Cầu là cạnh mà bỏ đi thì đồ thị mất liên thông. Bỏ mọi cầu, mỗi thành phần còn lại là một thành phần liên thông hai cạnh; co mỗi thành phần thành một đỉnh, các cầu nối chúng thành một cây. Mọi đường $s \to t$ bắt buộc đi qua đúng các cầu trên đường đi giữa hai thành phần trong cây này, nên bài “số cạnh bắt buộc lớn nhất” là đường kính của cây cầu.

Tìm cầu bằng Tarjan: low[v] là tin nhỏ nhất tới được từ cây con của $v$ bằng một cạnh ngược; cạnh cây $(p, v)$ là cầu khi low[v] > tin[p]. Với $3 \cdot 10^5$ đỉnh, viết DFS bằng ngăn xếp tường minh lưu chỉ số cạnh kế tiếp, và bỏ qua đúng cạnh vừa đi lên (theo chỉ số) chứ không phải đỉnh cha.

Ví dụTuyến Đường Bắt Buộc Dài Nhất

Đề. Đồ thị đơn liên thông $n, m \le 3 \cdot 10^5$. Chọn $s \ne t$ để số cạnh mà mọi đường $s \to t$ đều phải qua là lớn nhất.

Lời giải. Cạnh mà mọi đường $s \to t$ đều phải đi qua là cầu nằm giữa thành phần của $s$ và thành phần của $t$ trên cây cầu. Vậy đáp án là đường kính của cây cầu. Tìm cầu bằng Tarjan không đệ quy, tô các thành phần liên thông hai cạnh bằng BFS không đi qua cầu, nối các thành phần bằng cầu, rồi tìm đường kính bằng hai lần BFS.

Bước 1: Tarjan bằng ngăn xếp. it[u] là chỉ số cạnh kế tiếp của $u$, pe[u] là chỉ số cạnh đi từ cha xuống $u$. Bỏ qua đúng cạnh pe[u], không phải mọi cạnh tới đỉnh cha, để cạnh song song vẫn được tính là cạnh ngược. Gặp đỉnh đã thăm thì cập nhật low[u] bằng tin[v]. Hết cạnh thì đưa low[u] lên cha p; low[u] > tin[p] nghĩa là cây con của $u$ không có cạnh nào vòng lên trên $p$, nên cạnh pe[u] là cầu.

int u = st.back();
if (it[u] < (int)adj[u].size()) {
    int v = adj[u][it[u]].first, id = adj[u][it[u]].second;
    it[u]++;
    if (id == pe[u]) continue;
    if (tin[v]) low[u] = min(low[u], tin[v]);
    else {
        tin[v] = low[v] = ++timer, pe[v] = id;
        st.push_back(v);
    }
} else {
    st.pop_back();
    if (!st.empty()) {
        int p = st.back();
        low[p] = min(low[p], low[u]);
        if (low[u] > tin[p]) isBridge[pe[u]] = 1;
    }
}

Bước 2: tô thành phần, dựng cây cầu. BFS từ mỗi đỉnh chưa tô, chỉ đi qua cạnh không phải cầu. Mỗi cầu nối hai thành phần ở hai đầu; đồ thị liên thông nên tr là một cây.

for (int i = 0; i < m; i++)
    if (isBridge[i]) tr[comp[eu[i]]].push_back(comp[ev[i]]), tr[comp[ev[i]]].push_back(comp[eu[i]]);

Bước 3: đường kính. BFS từ thành phần bất kỳ tới đỉnh xa nhất a, rồi BFS từ a; khoảng cách xa nhất lần hai là đường kính.

int a = bfs(1, k), b = bfs(a, k);
cout << dist[b] << '\n';

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

const int N = 3e5 + 5;
int n, m, timer, tin[N], low[N], comp[N], dist[N], eu[N], ev[N], it[N], pe[N];
bool isBridge[N];
vector<pair<int, int>> adj[N];
vector<int> tr[N];

int bfs(int s, int k) {
    for (int i = 1; i <= k; i++) dist[i] = -1;
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    int far = s;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (dist[u] > dist[far]) far = u;
        for (int v : tr[u])
            if (dist[v] < 0) dist[v] = dist[u] + 1, q.push(v);
    }
    return far;
}

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

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> eu[i] >> ev[i];
        adj[eu[i]].push_back({ev[i], i});
        adj[ev[i]].push_back({eu[i], i});
    }
    vector<int> st = {1};
    tin[1] = low[1] = ++timer, pe[1] = -1;
    while (!st.empty()) {
        int u = st.back();
        if (it[u] < (int)adj[u].size()) {
            int v = adj[u][it[u]].first, id = adj[u][it[u]].second;
            it[u]++;
            if (id == pe[u]) continue;
            if (tin[v]) low[u] = min(low[u], tin[v]);
            else {
                tin[v] = low[v] = ++timer, pe[v] = id;
                st.push_back(v);
            }
        } else {
            st.pop_back();
            if (!st.empty()) {
                int p = st.back();
                low[p] = min(low[p], low[u]);
                if (low[u] > tin[p]) isBridge[pe[u]] = 1;
            }
        }
    }
    int k = 0;
    for (int s = 1; s <= n; s++) {
        if (comp[s]) continue;
        comp[s] = ++k;
        vector<int> q = {s};
        for (int i = 0; i < (int)q.size(); i++) {
            int u = q[i];
            for (pair<int, int> e : adj[u])
                if (!isBridge[e.second] && !comp[e.first]) comp[e.first] = k, q.push_back(e.first);
        }
    }
    for (int i = 0; i < m; i++)
        if (isBridge[i]) tr[comp[eu[i]]].push_back(comp[ev[i]]), tr[comp[ev[i]]].push_back(comp[eu[i]]);
    int a = bfs(1, k), b = bfs(a, k);
    cout << dist[b] << '\n';
}

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

Output3

$O(n + m)$.