Tìm bộ ba nút có tổng đường đi lớn nhất trong cây C++

Cho cây N nút. Tìm 3 nút (triplet) sao cho số nút khác nhau trên các đường đi nối 3 cặp giữa chúng lớn nhất.

Ý tưởng

• Tìm đường kính cây (2 nút xa nhất) → u, v.
• Tìm nút w xa nhất đường kính (khoảng cách đến đường kính lớn nhất).
• Triplet (u, v, w) tối ưu.

Code C++ (đã sửa logic)

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

const int MAXN = 100005;
vector<int> adj[MAXN];
int parent[MAXN], dist[MAXN];
bool vis[MAXN];

pair<int,int> bfs(int src) {
    fill(dist, dist+MAXN, -1);
    queue<int> q; q.push(src); dist[src] = 0;
    int far = src;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        for (int v : adj[u]) if (dist[v] == -1) {
            dist[v] = dist[u] + 1;
            parent[v] = u;
            q.push(v);
            if (dist[v] > dist[far]) far = v;
        }
    }
    return {far, dist[far]};
}

int main() {
    int n; 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);
    }
    
    // 1. Tìm đường kính
    auto [u, _] = bfs(1);
    auto [v, diam] = bfs(u);
    
    // 2. Đánh dấu đường kính
    vector onDia(n+1, false);
    for (int x = v; x != u; x = parent[x]) onDia[x] = true;
    onDia[u] = true;
    
    // 3. Tìm w xa đường kính nhất (multi-source BFS từ các nút trên đường kính)
    fill(dist, dist+MAXN, -1);
    queue<int> q;
    for (int i = 1; i <= n; i++) if (onDia[i]) {
        dist[i] = 0; q.push(i);
    }
    int w = u, maxD = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        if (dist[x] > maxD) { maxD = dist[x]; w = x; }
        for (int y : adj[x]) if (dist[y] == -1) {
            dist[y] = dist[x] + 1;
            q.push(y);
        }
    }
    
    cout << "Triplet: " << u << " " << v << " " << w << endl;
    return 0;
}

Lưu ý: Code gốc có logic phức tạp và output (0,0,0) do nhập liệu sai. Phiên bản trên dùng BFS chuẩn.