O problema de determinar o peso total de uma árvore (a soma de todos os comprimentos de suas arestas) a partir de uma matriz que forneece as distâncias entre todos os pares de folhas pode ser resolvido de forma eficiente utilizando abordagens gulosas e propriedades métricas das árvores.

Abordagem 1: Construção Incremental com Simulação

A primeira estratégia baseia-se na construção da árvore nó a nó. A ideia central é integrar cada nova folha à estrutura já formada pelas folhas anteriores. Ao adicionar a folha i, calculamos o comprimento do ramo que a conecta à árvore existente e registramos o ponto exato de inserção. Embora essa simulação seja intuitiva, ela exige cuidado no gerenciamento das conexões e na compressão dos caminhos para evitar complexidade desnecessária.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>

using namespace std;

int main() {
    int n;
    while (cin >> n && n > 0) {
        vector<vector<int>> d(n + 1, vector<int>(n + 1, 0));
        for (int i = 1; i < n; ++i) {
            for (int j = i + 1; j <= n; ++j) {
                cin >> d[i][j];
                d[j][i] = d[i][j];
            }
        }

        vector<int> branchWeights(n + 1, 0);
        branchWeights[2] = d[1][2];

        for (int currentLeaf = 3; currentLeaf <= n; ++currentLeaf) {
            int minBranch = d[1][currentLeaf];
            for (int prevLeaf = 2; prevLeaf < currentLeaf; ++prevLeaf) {
                int connectionDist = (d[1][currentLeaf] + d[1][prevLeaf] - d[currentLeaf][prevLeaf]) / 2;
                int branchLen = d[1][currentLeaf] - connectionDist;
                minBranch = min(minBranch, branchLen);
            }
            branchWeights[currentLeaf] = minBranch;
        }

        int totalTreeWeight = accumulate(branchWeights.begin() + 2, branchWeights.end(), 0);
        cout << totalTreeWeight << "\n";
    }
    return 0;
}

Aobrdagem 2: Abstração Matemática e Cálculo Direto

Em vez de simular a topologia da árvore, podemos abstrair o problema para uma fórmula puramente matemática. O comprimento do ramo que conecta a folha i à subárvore formada pelas folhas 1 a i-1 é dado pelo mínimo de (d(1, i) - d(1, j) + d(i, j)) / 2 para todo j < i. Somando esses comprimentos mínimos para todas as folhas de 2 a N, obtemos o peso total da árvore sem a necessidade de estruturas de dados auxiliares para rastrear conexões.

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int leafCount;
    while (cin >> leafCount && leafCount > 0) {
        vector<vector<int>> matrix(leafCount + 1, vector<int>(leafCount + 1, 0));
        
        for (int i = 1; i < leafCount; ++i) {
            for (int j = i + 1; j <= leafCount; ++j) {
                cin >> matrix[i][j];
                matrix[j][i] = matrix[i][j];
            }
        }

        long long totalWeight = 0;
        
        for (int i = 2; i <= leafCount; ++i) {
            int minEdgeWeight = numeric_limits<int>::max();
            
            for (int j = 1; j < i; ++j) {
                int weight = matrix[1][i] - ((matrix[1][i] + matrix[1][j] - matrix[i][j]) / 2);
                minEdgeWeight = min(minEdgeWeight, weight);
            }
            
            totalWeight += minEdgeWeight;
        }

        cout << totalWeight << "\n";
    }

    return 0;
}