Hướng giải của Mọi đường kính

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

Sử dụng Centroid Decomposition kết hợp với kỹ thuật theo dõi độ sâu lớn nhất.

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

  1. Tính khoảng cách từ \(C\) đến mọi đỉnh trong thành phần của nó.
  2. Với mỗi đỉnh \(u\) (khác \(C\)), xem xét các đường đi qua \(u\) mà \(C\) là tổ tiên centroid của \(u\).
  3. Duy trì hai giá trị lớn nhất của khoảng cách từ \(C\) đến các đỉnh trong các nhánh khác nhau.
  4. Khi duyệt một nhánh con của \(C\), với mỗi đỉnh \(u\) trong nhánh đó, đóng góp từ các nhánh khác là \(dist(C, u) + maxDistOtherBranch\).

Centroid Decomposition đảm bảo mỗi cặp đỉnh được xét đúng một lần tại centroid thấp nhất nằm trên đường đi giữa chúng.

Độ phức tạp
  • Thời gian: \(O(N \log N)\).
  • Bộ nhớ: \(O(N)\).
Code mẫu
// Giải thuật cd cho bài toán cd-diameter-all\n#include <bits/stdc++.h>
using namespace std;

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

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 dfs_collect(int u, int p, long long d, vector<pair<long long,int>> &out) {
    out.push_back({d, u});
    for (auto [v, w] : adj[u])
        if (v != p && !removed[v])
            dfs_collect(v, u, d + w, out);
}

void decompose(int u) {
    dfs_size(u, -1);
    int c = find_centroid(u, -1, subsize[u]);
    removed[c] = true;

    vector<vector<pair<long long,int>>> branches;
    for (auto [v, w] : adj[c]) {
        if (removed[v]) continue;
        vector<pair<long long,int>> branch;
        dfs_collect(v, c, w, branch);
        if (!branch.empty()) branches.push_back(branch);
    }

    long long max1 = -INF, max2 = -INF;
    int idx1 = -1;
    for (int i = 0; i < (int)branches.size(); i++) {
        long long best = 0;
        for (auto [d, node] : branches[i]) best = max(best, d);
        if (best > max1) { max2 = max1; idx1 = i; max1 = best; }
        else if (best > max2) max2 = best;
    }

    if (branches.size() >= 2) ans[c] = max(ans[c], max1 + max2);
    if (branches.size() >= 1) ans[c] = max(ans[c], max1);
    for (auto [v, w] : adj[c]) ans[c] = max(ans[c], (long long)w);

    for (int i = 0; i < (int)branches.size(); i++) {
        long long other_max = (i == idx1) ? max2 : max1;
        if (other_max < 0) other_max = 0;
        for (auto [d, node] : branches[i]) {
            ans[node] = max(ans[node], d + other_max);
        }
    }

    for (auto [v, w] : adj[c])
        if (!removed[v]) decompose(v);
}

int main() {
    // Doc du lieu dau vao
    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);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << "\n";
    return 0;
}

Nhận xét

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