Música - Midwest Indigo Na faculdade aprendemos um conceito chamado "Árvore Geradora Mínima". Ela consiste em achar um subconjunto de arestas de um grafo de modo que as arestas formem uma árvore (grafo conexo, que conecta todos os vértices, e acíclico), e com menor soma total dos pesos.
Fábio quer passar essa questão para seus alunos, mas como hoje me dia o ChatGPT consegue resolver a questão ele resolveu deixar um pouco mais complicado. A questão é a seguinte:
É dada uma árvore T de n vértices com peso nas arestas e nos vértices. Os pesos nos vértices são dados por uma sequência pi, para 1 ≤ i ≤ n.
Defina um novo grafo G completo, em que existe uma aresta de u para v com peso w(u, v) = p(u) + d(u, v) + p(v), sendo d(u, v) a distância de u e v em T. Ou seja, d(u, v) é a soma dos pesos das arestas no menor caminho de u até v na árvore T, enquanto w(u, v) é d(u, v) somado aos pesos dos vértices u e v.
Você deve encontrar o custo da árvore geradora mínima de G.
Será que você consegue se provar mais inteligente que o Chat-GPT e resolver essa questão?
A primeira linha do input contém um inteiro n, 1 ≤ n ≤ 3·105, representando o número de vértices em T.
Seguem n inteiros pi, 1 ≤ pi ≤ 109.
Por fim, seguem n - 1 linhas ui vi wi representando uma aresta de T de ui para vi com peso wi. É garantido que T é uma árvore e que 1 ≤ wi ≤ 109.
Imprima um único inteiro representando o custo da árvore geradora mínima de G.
4 1000 1 10 100 1 2 1 1 3 2 1 4 3
1121
4 1 2 3 4 1 2 1 2 3 100 3 4 1
117
