Editorial for ptit016: Đường kính của cây

Hiểu bài toán

Cho một cây có n đỉnh và gốc tại đỉnh 1. Với mỗi đỉnh i, ta cần tính đường kính của cây con tại đỉnh i (bao gồm i và tất cả các con cháu của nó).

Đường kính của một cây là độ dài lớn nhất của đường đi giữa hai đỉnh bất kỳ trong cây đó.

Ví dụ:

• Input: Cây 4 đỉnh (1 là cha của 2, 3, 4).
• Với đỉnh 1: Cây con gồm {1, 2, 3, 4}. Đường kính là đường đi giữa 2 lá bất kỳ qua 1 (ví dụ 2-1-3), độ dài 2.
• Với các đỉnh 2, 3, 4: Cây con chỉ gồm 1 đỉnh, đường kính bằng 0.
• Output: 2 0 0 0.

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

Cách Naive DFS (Tính trên cây con)

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

const int MAXN = 100005;
vector<int> adj[MAXN];
int n;

// Hàm tìm đường kính của một cây con bằng BFS/DFS 2 lần
int get_diameter(int u, int parent) {
    // Tạm bỏ qua implementation chi tiết do độ phức tạp cao
    // Logic: Duyệt BFS/DFS từ u để tìm node xa nhất A,
    // rồi BFS/DFS từ A để tìm node xa nhất B.
    // Khoảng cách A-B là đường kính.
    return 0;
}

int main() {
    cin >> n;
    for(int i=0; i<n-1; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Với mỗi đỉnh i, gọi get_diameter(i, -1)
    // In kết quả
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n)

Cách tiếp cận trực quan nhất. Với mỗi đỉnh i, ta coi nó là gốc của cây con và tính đường kính của cây đó.

Để tính đường kính của một cây, ta có thể dùng thuật toán kinh điển:

1. Chọn một đỉnh bất kỳ (ví dụ gốc i).
2. Tìm đỉnh xa nhất từ i (gọi là A).
3. Tìm đỉnh xa nhất từ A (gọi là B).
4. Khoảng cách từ A đến B là đường kính.

Vì ta phải làm việc này cho tất cả n đỉnh, và mỗi lần làm mất O(n), tổng thời gian là O(n^2). Với n ≤ 10^5, giải pháp này chắc chắn bị TLE (Time Limit Exceeded). Tuy nhiên, nó rất hữu ích để kiểm tra tính đúng đắn của bài toán trên các test nhỏ.

Cách DFS Duyệt 2 lần (Tree DP)

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100005

// Cấu trúc lưu đồ thị (Adjacency List)
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

Node* adj[MAXN];
int max1[MAXN]; // Chiều sâu nhánh dài nhất
int max2[MAXN]; // Chiều sâu nhánh dài thứ hai
int diam[MAXN];  // Đường kính của cây con tại đỉnh đó

Node* makeNode(int v) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

void addEdge(int u, int v) {
    Node* newNode = makeNode(v);
    newNode->next = adj[u];
    adj[u] = newNode;

    newNode = makeNode(u);
    newNode->next = adj[v];
    adj[v] = newNode;
}

void dfs(int u, int parent) {
    max1[u] = 0;
    max2[u] = 0;
    diam[u] = 0;

    Node* p = adj[u];
    while(p != NULL) {
        int v = p->vertex;
        if (v == parent) {
            p = p->next;
            continue;
        }

        dfs(v, u);

        // Cập nhật độ sâu hai nhánh dài nhất tại u
        int depth_v = max1[v] + 1;
        if (depth_v > max1[u]) {
            max2[u] = max1[u];
            max1[u] = depth_v;
        } else if (depth_v > max2[u]) {
            max2[u] = depth_v;
        }

        // Cập nhật đường kính (lấy max từ các con)
        if (diam[v] > diam[u]) {
            diam[u] = diam[v];
        }

        p = p->next;
    }

    // Đường kính đi qua u: max1[u] + max2[u]
    int path_through_u = max1[u] + max2[u];
    if (path_through_u > diam[u]) {
        diam[u] = path_through_u;
    }
}

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        scanf("%d %d", &u, &v);
        addEdge(u, v);
    }

    dfs(1, 0);

    for (int i = 1; i <= n; i++) {
        printf("%d ", diam[i]);
    }
    printf("\n");

    return 0;
}

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

Đây là thuật toán tối ưu cách 1 và là phương pháp chuẩn để giải quyết bài toán này (Tree DP - Dynamic Programming trên cây).

Lưu ý quan trọng: Code C mẫu trong đề bài bị sai logic. Nó chỉ cập nhật diam[u] = max(diam[u], diam[v]) nhưng không xử lý trường hợp đường kính đi qua u bằng cách kết hợp hai nhánh con. Code ở đây đã sửa lỗi đó.

Logic thuật toán:

1. Ta duyệt DFS từ gốc (đỉnh 1).
2. Với mỗi đỉnh u, ta cần 3 thông tin từ các con của nó:
   • max1[u]: Chiều sâu của nhánh dài nhất từ u đi xuống.
   • max2[u]: Chiều sâu của nhánh dài thứ hai.
   • diam[u]: Đường kính của cây con tại u.
3. Quá trình duyệt (Bottom-up):
   • Khi duyệt từ con v trở về u, ta có sẵn diam[v], max1[v]. Chiều sâu từ u qua v là max1[v] + 1.
   • Cập nhật max1[u] và max2[u] dựa trên các nhánh con.
   • Cập nhật diam[u] bằng cách so sánh:
     • Đường kính lớn nhất trong các cây con (max diam[v]).
     • Đường kính đi qua u (ghép 2 nhánh sâu nhất: max1[u] + max2[u]).
4. Độ phức tạp: O(N) do duyệt mỗi cạnh đúng 2 lần.

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

Bài học kinh nghiệm

• Đường kính của cây con tại đỉnh u có thể được tính toán bằng cách kết hợp thông tin từ các con của u (Dynamic Programming).
• Đường kính tại u là max của: (1) Đường kính lớn nhất trong các cây con của u, (2) Chiều sâu nhánh dài nhất + Chiều sâu nhánh dài thứ hai đi qua u.
• Bài toán yêu cầu tính toán cho mọi gốc, phù hợp với thuật toán DFS duyệt toàn bộ cây một lần (O(N)).

Lỗi thường gặp

• Lỗi Logic (Code mẫu): Chỉ cập nhật diam[u] = max(diam[u], diam[v]) mà quên mất trường hợp đường kính đi qua u bằng cách nối hai nhánh con (max1 + max2).
• Quên xử lý trường hợp cây con chỉ có 1 đỉnh (leaf node): Khi đó diam phải là 0.
• Lỗi tràn số/integer overflow: Nếu dùng int nhưng chiều sâu có thể lớn hơn 2^31 - 1 (với n=10^5 thì không sao, nhưng cẩn thận).