Trong xử lý cấu trúc dữ liệu cây, Điểm phân trị (Centroid Decomposition) là một kỹ thuật mạnh mẽ giúp giải quyết các bài toán liên quan đến đường đi. Ý tưởng cốt lõi là chia nhỏ cây ban đầu thành các thành phần nhỏ hơn bằng cách chọn một "trọng tâm" (centroid) làm gốc, sau đó xử lý đệ quy trên từng phần.

Cơ chế hoạt động

Giả sử chúng ta cần kiểm tra xem trên cây có tồn tại đường đi độ dài $k$ hay không. Với một nút bất kỳ được chọn làm gốc (gọi là root), mọi đường đi trong cây sẽ thuộc một trong hai loại:

• Đường đi đi ngang qua root (bao gồm cả các đường đi bắt đầu hoặc kết thúc tại root).
• Đường đi nằm hoàn toàn trong một nhánh con của root.

Kỹ thuật điểm phân trị xử lý loại thứ nhất trực tiếp tại mỗi bước và xử lý loại thứ hai bằng cách lặp lại quy trình tương tự trong các cây con sau khi loại bỏ root.

Tìm trọng tâm của cây

Để đảm bảo hiệu suất, chúng ta không chọn gốc ngẫu nhiên. Trọng tâm của một cây là nút mà sau khi loại bỏ nó, kích thước của các thành phần còn lại không vượt quá một nửa kích thước cây ban đầu. Việc chọn trọng tâm giúp độ sâu của cây đệ quy tối đa chỉ là $O(\log N)$.

int nodeCount, centroid;
int subSize[MAXN], maxSub[MAXN];
bool removed[MAXN];

void calculateSize(int u, int p) {
    subSize[u] = 1;
    maxSub[u] = 0;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (v != p && !removed[v]) {
            calculateSize(v, u);
            subSize[u] += subSize[v];
            maxSub[u] = max(maxSub[u], subSize[v]);
        }
    }
}

void findCentroid(int u, int p, int total) {
    maxSub[u] = max(maxSub[u], total - subSize[u]);
    if (maxSub[u] < maxSub[centroid]) {
        centroid = u;
    }
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (v != p && !removed[v]) {
            findCentroid(v, u, total);
        }
    }
}

Xử lý các đường đi qua trọng tâm

Tại mỗi bước phân trị, chúng ta thu thập khoảng cách từ trọng tâm hiện tại đến tất cả các nút trong các nhánh con. Để kiểm tra sự tồn tại của đường đi độ dài $K$, ta có thể sử dụng một mảng đánh dấu (hoặc bitset) để lưu trữ các độ dài đường đi đã xuất hiện ở các nhánh con trước đó, tránh việc kết hợp hai đường đi thuộc cùng một nhánh con (vì chúng không đi qua trọng tâm).

int dists[MAXN], distCount;
bool exists[10000005]; // Mảng đánh dấu khoảng cách
int queries[M], hasPath[M];
vector<int> history;

void collectDistances(int u, int p, int d) {
    dists[++distCount] = d;
    for (auto& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (v != p && !removed[v]) {
            collectDistances(v, u, d + w);
        }
    }
}

void solve(int u) {
    removed[u] = true;
    exists[0] = true;
    history.push_back(0);

    for (auto& edge : adj[u]) {
        int v = edge.first;
        int w = edge.second;
        if (!removed[v]) {
            distCount = 0;
            collectDistances(v, u, w);
            
            // Kiểm tra các truy vấn dựa trên các khoảng cách đã tìm thấy
            for (int i = 1; i <= distCount; ++i) {
                for (int q = 1; q <= m; ++q) {
                    if (queries[q] >= dists[i]) {
                        if (exists[queries[q] - dists[i]]) hasPath[q] = true;
                    }
                }
            }
            
            // Cập nhật các khoảng cách mới vào mảng đánh dấu
            for (int i = 1; i <= distCount; ++i) {
                if (dists[i] < 10000005) {
                    exists[dists[i]] = true;
                    history.push_back(dists[i]);
                }
            }
        }
    }

    // Reset mảng đánh dấu cho bước phân trị tiếp theo
    for (int d : history) exists[d] = false;
    history.clear();

    // Đệ quy xuống các thành phần con
    for (auto& edge : adj[u]) {
        int v = edge.first;
        if (!removed[v]) {
            calculateSize(v, 0);
            centroid = 0;
            maxSub[centroid] = n;
            findCentroid(v, 0, subSize[v]);
            solve(centroid);
        }
    }
}

Độ phức tạp

Kỹ thuật này có độ phức tạp thời gian là $O(N \log N \times \text{cost per node})$. Trong bài toán kiểm tra độ dài đường đi, nếu chúng ta xử lý các truy vấn một cách hiệu quả, tổng độ phức tạp sẽ rơi vào khoảng $O(N \log N + M \times N)$.

Một điểm cần lưu ý là khi triển khai, việc tìm trọng tâm cần được thực hiện chính xác cho mỗi cây con riêng biệt. Nếu không, cây đệ quy có thể bị lệch (ví dụ trong trường hợp đồ thị dạng đường thẳng hoặc hình hoa cúc), dẫn đến độ phức tạp bị đẩy lên $O(N^2)$.