Phương Pháp Phân Tâm Cơ Bản

Kỹ thuật phân tâm (centroid decomposition) giải quyết bài toán đếm đường đi trên cây thông qua việc chia nhỏ bài toán dựa trên trọng tâm. Với cây có n đỉnh và trọng số cạnh, ta cần xác định sự tồn tại của cặp đỉnh cách nhau đúng k đơn vị.

Quy trình thực hiện:

1. Tìm trọng tâm của cây hiện tại
2. Tính toán tất cả khoảng cách từ trọng tâm đến các đỉnh trong phạm vi
3. Áp dụng nguyên lý bù trừ: cộng tổng cặp đường đi từ trọng tâm, sau đó trừ bớt các đường đi nằm hoàn toàn trong từng cây con
4. Lặp lại cho từng cây con

Triển Khai Mã Nguồn

struct Canh {
    int dich, trongSo;
};

vector<Canh> ke[MAX_N];
bool daXet[MAX_N];
int kichThuoc[MAX_N], maxCon[MAX_N];
int tongKichThuoc, trongTam;

void timTrongTam(int u, int cha) {
    kichThuoc[u] = 1;
    maxCon[u] = 0;
    for (auto& c : ke[u]) {
        if (c.dich == cha || daXet[c.dich]) continue;
        timTrongTam(c.dich, u);
        kichThuoc[u] += kichThuoc[c.dich];
        maxCon[u] = max(maxCon[u], kichThuoc[c.dich]);
    }
    maxCon[u] = max(maxCon[u], tongKichThuoc - kichThuoc[u]);
    if (maxCon[u] < maxCon[trongTam]) trongTam = u;
}

vector<int> khoangCach;
void tinhKhoangCach(int u, int cha, int d) {
    khoangCach.push_back(d);
    for (auto& c : ke[u]) {
        if (c.dich == cha || daXet[c.dich]) continue;
        tinhKhoangCach(c.dich, u, d + c.trongSo);
    }
}

void xuLy(int u, int d, int heSo) {
    khoangCach.clear();
    tinhKhoangCach(u, 0, d);
    for (int i = 0; i < khoangCach.size(); ++i) {
        for (int j = i + 1; j < khoangCach.size(); ++j) {
            ketQua[khoangCach[i] + khoangCach[j]] += heSo;
        }
    }
}

void phanTach(int u) {
    daXet[u] = true;
    xuLy(u, 0, 1);
    for (auto& c : ke[u]) {
        if (daXet[c.dich]) continue;
        xuLy(c.dich, c.trongSo, -1);
        tongKichThuoc = kichThuoc[c.dich];
        maxCon[0] = tongKichThuoc;
        trongTam = 0;
        timTrongTam(c.dich, u);
        phanTach(trongTam);
    }
}

Phân Tâm Động Với Cây Phân Tâm

Với bài toán cập nhật động (ví dụ: QTREE4), ta xây dựng cây phân tâm để quản lý các trọng tâm. Cấu trúc dữ liệu chính bao gồm:

• heapToanCuc: Theo dõi giá trị lớn nhất toàn cục
• heapCon[v]: Lưu giá trị lớn nhất từ các cây con của v trong cây phân tâm
• heapNhanh[v]: Quản lý khoảng cách từ v đến tổ tiên trong cây phân tâm

Cơ Chế Cập Nhật

Khi thay đổi trạng thái đỉnh:

1. Cập nhật heapCon tại đỉnh hiện tại
2. Duyệt lên tổ tiên trong cây phân tâm
3. Điều chỉnh heapNhanh và heapCon tại mỗi tổ tiên
4. Cập nhật heapToanCuc

struct HeapDinhHuong {
    priority_queue<int> chinh, rac;
    
    void them(int x) { chinh.push(x); }
    void xoa(int x) { rac.push(x); }
    
    int layDinh() {
        while (!rac.empty() && chinh.top() == rac.top()) {
            chinh.pop(); rac.pop();
        }
        return chinh.empty() ? -INF : chinh.top();
    }
    
    int tinhKetQua() {
        int max1 = layDinh();
        if (max1 == -INF) return -1;
        xoa(max1);
        int max2 = layDinh();
        them(max1);
        return max2 == -INF ? 0 : max1 + max2;
    }
};

HeapDinhHuong heapToanCuc, heapCon[MAX_N], heapNhanh[MAX_N];
int toTien[MAX_N][LOG_N];

void capNhat(int u, bool laXoa) {
    heapToanCuc.xoa(heapCon[u].tinhKetQua());
    laXoa ? heapCon[u].xoa(0) : heapCon[u].them(0);
    heapToanCuc.them(heapCon[u].tinhKetQua());
    
    for (int i = 1; i < toTien[u].size(); ++i) {
        int toT = toTien[u][i];
        int toT1 = toTien[u][i-1];
        
        heapToanCuc.xoa(heapCon[toT].tinhKetQua());
        int giaTriCu = heapNhanh[toT1].layDinh();
        if (giaTriCu != -INF) heapCon[toT].xoa(giaTriCu);
        
        laXoa ? heapNhanh[toT1].xoa(toTien[u][i-1]) 
              : heapNhanh[toT1].them(toTien[u][i-1]);
        
        int giaTriMoi = heapNhanh[toT1].layDinh();
        if (giaTriMoi != -INF) heapCon[toT].them(giaTriMoi);
        heapToanCuc.them(heapCon[toT].tinhKetQua());
    }
}

Lưu Ý Triển Khai Quan Trọng

• Luôn truyền trọng tâm (trongTam) chứ không truyền đỉnh con (to) khi đệ quy
• Khởi tạo lại kichThuoc và maxCon trước mỗi lần tìm trọng tâm
• Phân biệt rõ đỉnh hiện tại (u) và đỉnh con (c.dich) trong vòng lặp
• Sử dụng nguyên lý bù trừ để tránh đếm lặp đường đi trong cây con
• Khi xử lý khoảng cách, kiểm tra điều kiện biên k - khoangCach >= 0 trước khi truy vấn