Editorial for tree: Bầy kiến xây tổ

Hiểu bài toán

Xây dựng một cây có N đỉnh sao cho với mỗi đỉnh u, khoảng cách từ u đến đỉnh xa nhất (eccentricity) bằng A_u. Xác định xem có tồn tại cây như vậy hay không.

Cây là đồ thị liên thông không chu trình. Trong cây, đường đi giữa hai đỉnh là duy nhất. Đỉnh xa nhất của một đỉnh u trong cây luôn là một trong hai đầu mút của đường kính (đường đi dài nhất trong cây).

Ta cần kiểm tra xem tập hợp các giá trị A_u có thỏa mãn các điều kiện hình học của một cây hay không.

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

Cách Kiểm tra theo bán kính (Hash Map)

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;cin>>n;
    vector<int> a(n);
    map<int,int> f;
    int d=0;
    for (int i=0;i<n;i++){
        cin>>a[i];
        d=max(d,a[i]);
        f[a[i]]++;
    }
    if (f[d]<2){
        cout<<"Impossible";
        return 0;
    }
    int m;
    if (d%2==0){
        m=d/2;
        if (f[m]!=1){
            cout<<"Impossible";
            return 0;
        }
    }else{
        m=(d+1)/2;
        if (f[m]!=2){
            cout<<"Impossible";
            return 0;
        }
    }
    for (map<int,int>::iterator it=f.begin();it!=f.end();++it){
        if (it->first<m){
            cout<<"Impossible";
            return 0;
        }
    }
    for (int i=m+1;i<d;i++){
        if (f[i]<2){
            cout<<"Impossible";
            return 0;
        }
    }
    cout<<"Possible";
    return 0;
}

• Time Complexity: O(N log N)
• Space Complexity: O(N)

Phương pháp này phân tích cấu trúc của các giá trị A_u dựa trên giả định rằng chúng ta có thể chọn một đường kính.

1. Tìm giá trị lớn nhất d trong mảng A. Đây là đường kính của cây.
2. Pseudocode trong solution 1 giả định rằng d chính là đường kính. Điều này không hoàn toàn chính xác trong mọi trường hợp (ví dụ: dãy 3 3 3 có thể là đường kính 4), nhưng là một cách tiếp cận phổ biến.
3. Kiểm tra số lượng giá trị bằng d (phải >= 2).
4. Xác định m là bán kính (radius):
   • Nếu d chẵn: m = d/2, chỉ có 1 đỉnh ở khoảng cách này (đỉnh trung tâm).
   • Nếu d lẻ: m = (d+1)/2, có 2 đỉnh ở khoảng cách này (hai đỉnh trung tâm).
5. Kiểm tra tần suất xuất hiện của m.
6. Kiểm tra các giá trị từ m+1 đến d-1 phải xuất hiện ít nhất 2 lần.
7. Các giá trị nhỏ hơn m không được phép.

Lưu ý: Solution 1 chỉ hoạt động chính xác khi d chọn lọc chính là đường kính thực sự. Trong nhiều trường hợp (ví dụ 3 3 3), d thực tế lớn hơn max(A). Tuy nhiên, logic này vẫn được giữ lại vì nó là một dạng phổ biến của bài toán.

Cách Xây dựng cây giả lập (Simulation)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
using namespace std;

struct Node {
    int id;
    int val;
    int deg;
};

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    map<int, int> cnt;
    int max_val = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        cnt[a[i]]++;
        max_val = max(max_val, a[i]);
    }

    // Giả định max_val là đường kính D
    int D = max_val;
    int R = (D + 1) / 2;

    // Nút 1: Cây đường kính (Pole)
    if (cnt[D] < 2) { cout << "Impossible"; return 0; }

    // Kiểm tra nút trung tâm
    if (D % 2 == 0) {
        if (cnt[D/2] != 1) { cout << "Impossible"; return 0; }
    } else {
        if (cnt[(D+1)/2] != 2) { cout << "Impossible"; return 0; }
    }

    // Kiểm tra các nhánh
    // Yêu cầu: Với mỗi giá trị v từ R+1 đến D-1, t tổng số node có giá trị >= v phải >= 2.
    // Tuy nhiên, logic đơn giản là:
    // Nếu node có giá trị v, nó phải là node lá hoặc node trong nhánh.
    // Logic từ Solution 3 (kiểm tra tổng số lượng từ trên xuống):

    int sum = 0;
    for (int i = R + 1; i <= D; i++) {
        if (cnt[i] < 2 && i != D) { // Logic thay đổi: Nếu số lượng < 2 thì phải là node cực đại
             // Solution 3 dùng một công thức tổng quát hơn
        }
    }

    // Áp dụng lại logic Solution 3:
    // sum += (cnt[i] >= 2) ? cnt[i] : -sum;
    // sum += (cnt[lim] == 1 + d % 2) ? cnt[lim] : -sum;
    // Nếu sum == n thì Possible.

    int sum_check = 0;
    int lim = (D + 1) / 2;
    for (int i = lim + 1; i <= D; ++i) {
        sum_check += (cnt[i] >= 2) ? cnt[i] : -sum_check;
    }
    sum_check += (cnt[lim] == 1 + D % 2) ? cnt[lim] : -sum_check;

    if (sum_check == n) cout << "Possible";
    else cout << "Impossible";

    return 0;
}

• Time Complexity: O(N)
• Space Complexity: O(N)

Phương pháp này cải tiến so với Hash Map bằng cách sử dụng một công thức tổng quát hơn để kiểm tra tính hợp lệ của dãy số.

Thay vì chỉ kiểm tra điều kiện biên, ta nhận thấy rằng:

• Các node nằm trên đường kính (có giá trị > R) phải xuất hiện ít nhất 2 lần để tạo thành các nhánh đối xứng (trừ node lá).
• Node ở bán kính R có số lượng cố định (1 nếu D chẵn, 2 nếu D lẻ).
• Logic của Solution 3 (sum += (cnt[i] >= 2) ? cnt[i] : -sum) là một cách viết gọn để kiểm tra xem tổng số node có giá trị >= i có đủ để "che chắn" cho các node có giá trị nhỏ hơn không. Nếu tại một mức giá trị nào đó, số lượng node không đủ 2 (trong khi cần thiết), biến sum sẽ bị reset (hoặc âm), dẫn đến việc sum != n ở cuối.

Cụ thể:

1. Liệt kê tần suất các giá trị.
2. Duyệt từ R+1 đến D:
   • Nếu số lượng >= 2, cộng dồn vào t tổng.
   • Nếu số lượng < 2, trừ tổng về 0 (để đảm bảo tổng không vượt quá n một cách sai lệch).
3. Kiểm tra R: Phải bằng 1 + D%2.
4. Nếu tổng cuối cùng bằng N, tức là tất cả node đều được phân bổ hợp lệ.

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

Bài học kinh nghiệm

• Vấn đề có thể được quy về kiểm tra xem tập hợp giá trị A_u có thể tạo thành một cây với đường kính D hay không, trong đó D là giá trị lớn nhất có thể có.
• Một cây có thể được chia thành 2 nhánh đối xứng qua trục đường kính. Điều này đòi hỏi số lượng node ở các khoảng cách đối xứng phải cân bằng.
• Giá trị Au của một node phụ thuộc vào khoảng cách từ node đó đến hai đầu mút của đường kính. Nếu node nằm trên nhánh, Au = max(disttoend1, disttoend2).

Lỗi thường gặp

• Không xử lý đúng các trường hợp đặc biệt của đường kính (lẻ/ chẵn).
• Bỏ qua việc một dãy số có thể tương ứng với nhiều độ dài đường kính khác nhau.
• Lỗi logic trong việc kiểm tra số lượng node ở các mức trung gian (phải >= 2).