Hướng dẫn cho Tạo dữ liệu (CK OLP MTTN lần V)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Tóm tắt đề bài

Cho một cây gồm \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\). Một tập con các đỉnh được gọi là "đẹp" nếu:

  1. Tập con này chứa các số hiệu liên tiếp nhau, tức là có dạng \([L, R]\) với \(1 \leq L \leq R \leq n\).
  2. Tập con này không phải là tập tất cả các đỉnh ban đầu (phải xóa đi ít nhất một đỉnh).
  3. Các đỉnh trong tập con này tạo thành một đồ thị con liên thông.
  4. Tập con phải có ít nhất một đỉnh.

Yêu cầu: Đếm số lượng tập con "đẹp".

Phân tích

  • Điều kiện liên thông của cây: Một tính chất quan trọng của cây là: Một tập con gồm \(k\) đỉnh của một cây sẽ liên thông nếu và chỉ nếu số cạnh nối giữa các đỉnh trong tập con đó đúng bằng \(k-1\).
  • Tập số hiệu liên tiếp: Tập các đỉnh còn lại có dạng \([L, R]\). Số lượng đỉnh trong tập này là \(k = R - L + 1\).
  • Kết hợp hai điều kiện: Một đoạn \([L, R]\) (với \(R-L+1 < n\)) là đẹp nếu số cạnh \((u, v)\) trong cây gốc thỏa mãn \(L \leq u, v \leq R\) đúng bằng \((R - L)\).
  • Đếm số cạnh: Gọi \(E(L, R)\) là số cạnh \((u, v)\) mà cả \(u\) và \(v\) đều thuộc đoạn \([L, R]\). Điều kiện cần tìm là:
    \[ E(L, R) = (R - L) \]

    Vì trong bất kỳ đồ thị không chu trình nào (như cây), số cạnh luôn \(\leq\) số đỉnh \(- 1\), nên ta luôn có \(E(L, R) \leq R - L\). Do đó, điều kiện \(E(L, R) = R - L\) cũng tương đương với việc tối đa hóa biểu thức:
    \[ (R - L) - E(L, R) = 0 \]

Hướng giải quyết

Thuật toán

Ta cần đếm số cặp \((L, R)\) sao cho \(1 \leq L \leq R \leq n\), \((L, R) \neq (1, n)\) và \(R - L - E(L, R) = 0\).
Để giải quyết bài toán này hiệu quả với \(n = 3 \cdot 10^5\), ta có thể sử dụng kỹ thuật Sweepline kết hợp với Segment Tree.

  1. Cố định \(R\) và chạy biến \(R\) từ \(1\) đến \(n\). Với mỗi \(R\), ta cần đếm số lượng \(L \in [1, R]\) thỏa mãn \(R - L - E(L, R) = 0\).
  2. Biến đổi biểu thức: \(E(L, R)\) là số cạnh \((u, v)\) sao cho \(\max(u, v) \leq R\) và \(\min(u, v) \geq L\).
  3. Khi tăng \(R\) lên \(R+1\):
    • Giá trị \(R - L\) tăng thêm 1 đơn vị cho tất cả \(L \in [1, R]\).
    • Xét các cạnh \((u, R+1)\) của cây. Với mỗi cạnh như vậy, nếu \(u < R+1\), thì với mọi \(L \leq u\), số cạnh \(E(L, R+1)\) sẽ tăng thêm 1 so với \(E(L, R)\).
  4. Sử dụng Segment Tree để quản lý giá trị \(f(L) = (R - L) - E(L, R)\):
    • Mỗi nút trên Segment Tree lưu giá trị nhỏ nhất (minVal) và số lượng vị trí đạt giá trị nhỏ nhất đó (cntMin).
    • Khi tăng \(R\):
      • Update đoạn \([1, R]\) cộng thêm 1 (do \(R\) tăng).
      • Với mỗi cạnh \((u, R)\), update đoạn \([1, u]\) trừ đi 1 (do \(E\) tăng).
    • Kết quả tại mỗi bước \(R\) là số lượng \(L\) sao cho \(f(L) = 0\). Vì \(f(L) \geq 0\) luôn đúng trong đồ thị dạng rừng, ta chỉ cần lấy cntMin nếu minVal == 0.
  5. Lưu ý: Đề bài yêu cầu xóa ít nhất một đỉnh, nên ta không tính trường hợp \(L=1, R=n\).

Độ phức tạp

  • Thời gian: \(O(n \log n)\) do duyệt qua \(n\) đỉnh và mỗi cạnh được xử lý một lần trên Segment Tree.
  • Bộ nhớ: \(O(n)\) để lưu danh sách kề và cây phân đoạn.

Code tham khảo

C++
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

struct Node {
    int minVal;
    long long cntMin;
};

Node tree[4 * MAXN];
int lazy[4 * MAXN];

Node merge(Node a, Node b) {
    if (a.minVal < b.minVal) return a;
    if (b.minVal < a.minVal) return b;
    return {a.minVal, a.cntMin + b.cntMin};
}

void push(int v) {
    if (lazy[v] != 0) {
        tree[2 * v].minVal += lazy[v];
        lazy[2 * v] += lazy[v];
        tree[2 * v + 1].minVal += lazy[v];
        lazy[2 * v + 1] += lazy[v];
        lazy[v] = 0;
    }
}

void update(int v, int tl, int tr, int l, int r, int add) {
    if (l > r) return;
    if (l == tl && r == tr) {
        tree[v].minVal += add;
        lazy[v] += add;
    } else {
        push(v);
        int tm = (tl + tr) / 2;
        update(2 * v, tl, tm, l, min(r, tm), add);
        update(2 * v + 1, tm + 1, tr, max(l, tm + 1), r, add);
        tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
    }
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        tree[v] = {0, 1};
    } else {
        int tm = (tl + tr) / 2;
        build(2 * v, tl, tm);
        build(2 * v + 1, tm + 1, tr);
        tree[v] = merge(tree[2 * v], tree[2 * v + 1]);
    }
}

vector<int> adj[MAXN];

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

    int n;
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    build(1, 1, n);
    long long ans = 0;

    for (int r = 1; r <= n; r++) {
        // Khi mở rộng R, f(L) = (R-L) - E(L, R)
        // Ban đầu tại L=r, f(r) = (r-r) - 0 = 0.
        // Với các L < r, R tăng 1 làm f(L) tăng 1.
        if (r > 1) update(1, 1, n, 1, r - 1, 1);

        // Với mỗi cạnh (u, r) mà u < r, E(L, r) tăng 1 với mọi L <= u
        // Do đó f(L) giảm 1 với mọi L <= u
        for (int u : adj[r]) {
            if (u < r) {
                update(1, 1, n, 1, u, -1);
            }
        }

        // Đếm số L trong [1, r] có f(L) == 0
        // Segment tree đang quản lý từ 1..n, nhưng ta chỉ quan tâm 1..r
        // Các vị trí L > r hiện có minVal rất lớn (hoặc ta có thể xử lý riêng)
        // Ở đây ta có thể query đoạn [1, r]
        Node res = {1000000000, 0};
        auto query = [&](auto self, int v, int tl, int tr, int l, int r) -> Node {
            if (l > r) return {1000000000, 0};
            if (l == tl && r == tr) return tree[v];
            push(v);
            int tm = (tl + tr) / 2;
            return merge(self(self, 2 * v, tl, tm, l, min(r, tm)),
                         self(self, 2 * v + 1, tm + 1, tr, max(l, tm + 1), r));
        };

        Node q = query(query, 1, 1, n, 1, r);
        if (q.minVal == 0) ans += q.cntMin;
    }

    // Trừ đi trường hợp L=1, R=n (không xóa đỉnh nào)
    cout << ans - 1 << endl;

    return 0;
}

Bình luận

Mới nhất
Tải bình luận...

Không có bình luận nào.