Phân tích bài toán

Đề bài yêu cầu chọn các cạnh để chia đôi trọng số (làm tròn xuống) sao cho tổng trọng số các đường từ gốc đến các lá không vượt quá giá trị cho trước S. Mỗi lần chọn cạnh, ta chỉ được chọn một cạnh duy nhất và tính lại tổng.

Chiến lược giải quyết

Chúng ta cần xác định mức độ ảnh hưởng của từng cạnh đến tổng trọng số bằng cách tính tích của trọng số cạnh và số lần cạnh đó xuất hiện trong các đường đi. Cạnh có tích này càng lớn thì hiệu ứng giảm tổng sẽ càng mạnh khi chia đôi.

Cài đặt chi tiết

Đầu tiên, sử dụng DFS để đếm số đường đi qua mỗi cạnh. Sau đó, dùng hàng đợi ưu tiên (priority queue) để chọn cạnh có khả năng giảm tổng cao nhất ở mỗi bước.

// Hàm DFS đếm số đường đi qua mỗi cạnh
void dfs(int u, int parent) {
    bool isLeaf = true;
    for (int i = 0; i < g[u].size(); i++) {
        int v = g[u][i];
        if (v != parent) {
            dfs(v, u);
            countEdges[idMap[u][v]] = countPath[v];
            countPath[u] += countPath[v];
            isLeaf = false;
        }
    }
    if (isLeaf) countPath[u] = 1;
}

Cấu trúc dữ liệu ưu tiên

Định nghĩa cấu trúc nút trong hàng đợi ưu tiên dựa trên khả năng giảm tổng khi chia đôi trọng số:

struct EdgeNode {
    int id;
    long long weight;
    bool operator < (const EdgeNode& other) const {
        return (weight - weight / 2) * countEdges[id] 
               < (other.weight - other.weight / 2) * countEdges[other.id];
    }
};

Quy trình xử lý

Tính tổng ban đầu và đẩy các cạnh vào hàng đợi ưu tiên. Lặp cho đến khi tổng không vượt quá S:

// Tính tổng ban đầu và khởi tạo hàng đợi
long long currentSum = 0;
for (int i = 1; i < n; i++) {
    edgeQueue.push({i, weights[i]});
    currentSum += countEdges[i] * weights[i];
}

// Vòng lặp tối ưu
int operations = 0;
while (currentSum > S) {
    EdgeNode top = edgeQueue.top();
    edgeQueue.pop();
    long long reduction = (top.weight - top.weight / 2) * countEdges[top.id];
    currentSum -= reduction;
    operations++;
    top.weight /= 2;
    edgeQueue.push(top);
}

Lưu ý

Với mỗi test case, cần reset toàn bộ dữ liệu để tránh ảnh hưởng giữa các lần chạy. Đặc biệt cần xóa sạch các vector, map và hàng đợi ưu tiên.