Hiểu bài toán

Cho một đồ thị cây liên thông với n đỉnh và n-1 cạnh, mỗi cạnh có trọng số nguyên dương. Với mỗi truy vấn (k, v), yêu cầu đếm số lượng đỉnh u sao cho 'trọng số của đường đi đơn từ u đến v' >= k. 'Trọng số của đường đi đơn' ở đây được định nghĩa là trọng số nhỏ nhất trên các cạnh của đường đi đó (min weight). Nói cách khác, ta cần đếm số lượng đỉnh u có đường đi đến v mà tất cả các cạnh trên đường đi đều có trọng số >= k.

Ví dụ: Input: 4 3, Cạnh: (1-2, 3), (2-3, 2), (2-4, 4). Truy vấn (k=1, v=2): Các đỉnh có đường đi đến 2 toàn bộ cạnh >= 1 là {1, 2, 3, 4} -> Kết quả 4. Truy vấn (k=4, v=2): Cạnh nối 2-4 có trọng số 4 >= 4, các cạnh khác nhỏ hơn 4. Đỉnh 4 có đường đi đến 2 (cạnh 4) thỏa mãn. Đỉnh 2 thỏa mãn (đường đi rỗng/độ dài 0). Các đỉnh 1, 3 không thỏa mãn vì qua cạnh 3 hay 2 đều < 4. -> Kết quả 2.

Dữ liệu: n, Q <= 10^5.

Các cách tiếp cận

Cách Brute Force BFS/DFS

void solve_naive() {
    // Duyệt từng truy vấn
    for (int i = 0; i < Q; i++) {
        int k = queries[i].k, v = queries[i].v;
        int count = 0;
        // BFS từ v, chỉ đi qua cạnh có trọng số >= k
        queue<int> q;
        vector<bool> visited(n + 1, false);
        q.push(v);
        visited[v] = true;
        count++;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (auto [next, weight] : adj[u]) {
                if (!visited[next] && weight >= k) {
                    visited[next] = true;
                    count++;
                    q.push(next);
                }
            }
        }
        cout << count << "\n";
    }
}

• Time Complexity: O(Q * n)
• Space Complexity: O(n)

Với mỗi truy vấn, ta thực hiện BFS hoặc DFS từ đỉnh v. Ta chỉ duyệt qua các cạnh có trọng số lớn hơn hoặc bằng k. Nếu đồ thị là cây (độ dài đường đi tối đa O(n)), độ phức tạp cho mỗi truy vấn là O(n). Với Q lên tới 10^5, tổng thời gian chạy sẽ khoảng 10^10 thao tác, quá thời gian cho phép.

Cách Offline Query + DSU (Kruskal Reconstruction)

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

const int MAXN = 100005;
int n, q;
struct Edge { int u, v, w; } edges[MAXN];
struct Query { int k, v, id, ans; } queries[MAXN];
int parent[MAXN], sz[MAXN];

int find_set(int v) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (sz[a] < sz[b]) swap(a, b);
        parent[b] = a;
        sz[a] += sz[b];
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> q;
    for (int i = 0; i < n - 1; i++) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }
    for (int i = 0; i < q; i++) {
        cin >> queries[i].k >> queries[i].v;
        queries[i].id = i;
    }

    // Sort edges descending by weight
    sort(edges, edges + n - 1, [](Edge a, Edge b) { return a.w > b.w; });
    // Sort queries descending by k
    sort(queries, queries + q, [](Query a, Query b) { return a.k > b.k; });

    // Init DSU
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        sz[i] = 1;
    }

    int edge_idx = 0;
    for (int i = 0; i < q; i++) {
        int k = queries[i].k;
        int v = queries[i].v;

        // Add edges with weight >= k into DSU
        while (edge_idx < n - 1 && edges[edge_idx].w >= k) {
            union_sets(edges[edge_idx].u, edges[edge_idx].v);
            edge_idx++;
        }

        // Find the size of the connected component containing v
        queries[i].ans = sz[find_set(v)];
    }

    // Sort answers back to original order
    sort(queries, queries + q, [](Query a, Query b) { return a.id < b.id; });
    for (int i = 0; i < q; i++) {
        cout << queries[i].ans << "\n";
    }
    return 0;
}

• Time Complexity: O((n + Q) log n)
• Space Complexity: O(n)

Đây là phương pháp tối ưu nhất.

1. Tư duy: Điều kiện 'đường đi từ u đến v có tất cả cạnh >= k' tương đương với việc u và v thuộc cùng một thành phần liên thông khi ta chỉ xét các cạnh có trọng số >= k.
2. Offline: Vì các truy vấn không phụ thuộc nhau, ta có thể xử lý offline (tất cả cùng lúc).
3. Thuật toán:
   • Sắp xếp các cạnh của cây theo trọng số giảm dần.
   • Sắp xếp các truy vấn theo giá trị k giảm dần.
   • Dùng DSU (Disjoint Set Union) để quản lý các thành phần liên thông.
   • Duyệt qua các truy vấn theo thứ tự k giảm dần. Với mỗi truy vấn, ta cập nhật DSU bằng cách thêm vào các cạnh có trọng số >= k (các cạnh này chưa được thêm vào trước đó vì ta duyệt k giảm dần).
   • Khi đã thêm đủ các cạnh thỏa mãn, kích thước của thành phần chứa v chính là câu trả lời.
4. Độ phức tạp: Sắp xếp cạnh O(n log n), sắp xếp truy vấn O(Q log Q), xử lý DSU (tìm tập hợp và gộp) gần như tuyến tính O((n + Q) * α(n)). Tổng thể O((n + Q) log n).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán có thể quy về bài toán thành phần liên thông (Connected Components). Nếu chỉ xét các cạnh có trọng số >= k, u và v liên thông <=> đường đi từ u đến v chỉ chứa các cạnh có trọng số >= k.
• Xử lý offline các truy vấn bằng cách sắp xếp theo điều kiện trọng số/k là kỹ thuật mạnh mẽ để tránh lặp lại các thao tác cho mỗi truy vấn.
• DSU (Disjoint Set Union) là cấu trúc dữ liệu phù hợp để quản lý các thành phần liên thông động khi thêm từng cạnh vào.

Lỗi thường gặp

• Quên khởi tạo DSU (parent và size) cho các đỉnh từ 1 đến n.
• Xử lý sai thứ tự khi kết hợp Sort cạnh và Sort truy vấn (phải duyệt giảm dần cho cả hai để đảm bảo cạnh được thêm vào đúng lúc).
• Sử dụng DFS/BFS online cho mỗi truy vấn sẽ gây Time Limit Exceeded trên dữ liệu lớn.