Hướng giải của Đường đi dài nhất

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Lời giải

Ý tưởng

Đường kính của cây có thể tìm bằng Centroid Decomposition hoặc DFS 2 lần đơn giản hơn. Tuy nhiên để luyện tập centroid, ta làm như sau:

Tại mỗi centroid \(C\):

  1. Tính khoảng cách từ \(C\) đến mọi đỉnh trong subtree của nó.
  2. Tìm hai đường đi dài nhất từ \(C\) đi vào hai subtree khác nhau.
  3. Đường kính đi qua \(C\) là tổng hai khoảng cách lớn nhất từ hai nhánh khác nhau.

Đệ quy xuống các centroid con để tìm đường kính trong từng thành phần.

Độ phức tạp
  • Thời gian: \(O(N \log N)\).
  • Bộ nhớ: \(O(N)\).
Code mẫu
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<pair<int,int>> adj[MAXN];
int subsize[MAXN];
bool removed[MAXN];
int n;
long long ans = 0;

void dfs_size(int u, int p) {
    subsize[u] = 1;
    for (auto [v, w] : adj[u])
        if (v != p && !removed[v]) {
            dfs_size(v, u);
            subsize[u] += subsize[v];
        }
}

int find_centroid(int u, int p, int tot) {
    for (auto [v, w] : adj[u])
        if (v != p && !removed[v] && subsize[v] > tot / 2)
            return find_centroid(v, u, tot);
    return u;
}

void get_dists(int u, int p, long long d, vector<long long>& out) {
    // Thu thập khoảng cách từ centroid
    out.push_back(d);
    for (auto [v, w] : adj[u])
        if (v != p && !removed[v])
            get_dists(v, u, d + w, out);
}

void update_diameter(int u) {
    // Cập nhật đường kính tại centroid u
    vector<long long> all;
    for (auto [v, w] : adj[u]) {
        if (removed[v]) continue;
        vector<long long> dists;
        get_dists(v, u, w, dists);
        for (long long d : dists) all.push_back(d);
        // Lấy max của dists để so với max từ các nhánh trước
        sort(dists.rbegin(), dists.rend());
        if (!dists.empty()) {
            if (all.size() > dists.size()) {
                // Có ít nhất một nhánh trước đó
            }
        }
    }
    // Cách đơn giản: lấy 2 giá trị lớn nhất từ tất cả dists
    sort(all.rbegin(), all.rend());
    if (all.size() >= 2) ans = max(ans, all[0] + all[1]);
    if (all.size() >= 1) ans = max(ans, all[0]);
}

void decompose(int u) {
    dfs_size(u, -1);
    int c = find_centroid(u, -1, subsize[u]);
    update_diameter(c);
    removed[c] = true;
    for (auto [v, w] : adj[c])
        if (!removed[v]) decompose(v);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, w; cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    decompose(1);
    cout << ans << "\n";
    return 0;
}

Nhận xét

Không có ý kiến tại thời điểm này.