Solução escrita por Márcio Vitor
Conhecimentos prévios:
No problema é pedido para calcularmos somas da distâncias de todos os pares de vértices em uma componente e juntar componentes, isso é um forte indício que vamos usar union-find.
A condição que o problema da para a construção de estradas garante que em toda componente existe apenas um vértice que pode receber arestas vamos chamar ele de “líder” de sua componente e toda aresta adicionada liga sempre dois lideres.
Seja $ans[u] =$ soma de distância dos pares de vértice, tudo que temos que descobrir é como manter essa resposta dinamicamente quando dois lideres tem sua componente unida, sejam eles, por exemplo, $u$ e $v$. Perceba também que pelo menos um entre $u$ e $v$ não aprece mais nas próximas criações de estrada, assuma que isso aconteça com o $u$.
A resposta para a nova componente será $ans[u] + ans[v] +$ (os caminhos que passam por $w$), ou seja $(w+w1) + (w+w1^{‘}) + (w+ w1 + w3 + w1^{‘}) + … = w \cdot sz[u] \cdot sz[v] + (w1)sz[v] + (w1 + w3$ $)sz[v] + (w2)sz[v] + (w1^{‘})sz[u] + (w1^{‘} + w2^{‘})sz[u] + (w1^{‘} + w2^{‘})sz[u] = w \cdot sz[u] \cdot sz[v] + sz[v]$(soma das distâncias dos caminhos que iniciam em u) $+ sz[u]$(soma das distâncias dos caminhos que iniciam em v).
Assim definindo $d_u$ = a soma das distâncias que partem do líder da componente do $u$. temos então que ao fazer $v$ ser o líder de $u$ $ans[v] += ans[u] + w \cdot sz[u] \cdot sz[v] + d[u] \cdot sz[v] + d[v] \cdot sz[u]$ e $d_v += d_u + w \cdot sz[u]$.
Complexidade: $\mathcal{O}(N \cdot log_2(N))$ (usando apenas o path compression)
Nota: também é possível implementar o small-to-large fazendo algumas mudanças no código e assim a complexidade fica $\mathcal{O}(N \cdot \alpha(n))$