El diámetro de un árbol es la lnogitud del camino más largo entre dos nodos. Existen enfoques eficientes para calcularlo, como la programación dinámica en árboles y el algoritmo de doble búsqueda en amplitud (BFS).

Programación Dinámica en Árboles

Puede manejar aristas con pesos negativos.

Complejidad temporal: O(n).

Sea distancia[x] la máxima distancia alcanzable desde el nodo x en el subárbol que lo tiene como raíz. Para cada nodo hijo y_i, con peso de arista peso(x, y_i), se cumple:

distancia[x] = max(distancia[y_i] + peso(x, y_i)) para todo i.

Para calcular la cadena más larga que pasa por x, se combina la mayer y segunda mayor distancia hacia sus hijos:

cadena_larga[x] = max(distancia[y_i] + distancia[y_j] + peso(x, y_i) + peso(x, y_j)) donde j ≠ i.

struct Arista {int destino, peso;};
vector<vector>> grafo;
int diametro_global = 0;
vector<bool> visitado;
vector<int> max_dist;

void dfs(int nodo) {
    visitado[nodo] = true;
    for (const auto& arista : grafo[nodo]) {
        if (visitado[arista.destino]) continue;
        dfs(arista.destino);
        diametro_global = max(diametro_global, max_dist[nodo] + max_dist[arista.destino] + arista.peso);
        max_dist[nodo] = max(max_dist[nodo], max_dist[arista.destino] + arista.peso);
    }
}
</int></bool></vector>

Doble BFS para Diámetro

No soporta pesos negativos en las aristas.

Complejidad temporal: O(n).

Este método no solo calcula la longitud del diámetro, sino que también puede recuperar los nodos que lo forman.

struct Nodo {int id, dist_recorrido;};
struct Arista {int destino, peso;};

vector<vector>> grafo;
vector<bool> visitado;
vector<int> padre;

Nodo bfs_lejano(int inicio) {
    queue<Nodo> cola;
    visitado.assign(grafo.size(), false);
    cola.push({inicio, 0});
    visitado[inicio] = true;
    Nodo mas_lejano = {inicio, 0};

    while (!cola.empty()) {
        Nodo actual = cola.front(); cola.pop();
        if (actual.dist_recorrido > mas_lejano.dist_recorrido) {
            mas_lejano = actual;
        }
        for (const auto& arista : grafo[actual.id]) {
            if (!visitado[arista.destino]) {
                visitado[arista.destino] = true;
                cola.push({arista.destino, actual.dist_recorrido + arista.peso});
                padre[arista.destino] = actual.id;
            }
        }
    }
    return mas_lejano;
}

pair<int, vector<int>> obtener_diametro() {
    Nodo primero = bfs_lejano(0);
    Nodo segundo = bfs_lejano(primero.id);
    vector<int> camino;
    camino.push_back(segundo.id);

    int actual = segundo.id;
    while (actual != primero.id) {
        actual = padre[actual];
        camino.push_back(actual);
    }
    reverse(camino.begin(), camino.end());
    return {segundo.dist_recorrido, camino};
}

int main() {
    int num_nodos;
    cin >> num_nodos;
    grafo.resize(num_nodos);
    padre.resize(num_nodos, -1);

    for (int i = 0; i < num_nodos - 1; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        grafo[u].push_back({v, w});
        grafo[v].push_back({u, w});
    }

    auto [longitud, camino] = obtener_diametro();
    cout << longitud << endl;
    for (int id : camino) {
        cout << id + 1 << " ";
    }
    cout << endl;
    return 0;
}
</int></bool></vector>