Rotas de duas cores
Uma árvore possui vértices e comprimentos positivos nas arestas. Cada vértice é vazio, vermelho ou azul.
Emparelhe todos os vértices vermelhos com todos os vértices azuis, usando cada vértice colorido em exatamente um par. A rota de um par é o caminho simples entre seus dois vértices. Seu comprimento é a soma dos comprimentos das arestas desse caminho.
Duas rotas não podem compartilhar arestas. Elas podem compartilhar vértices, inclusive vértices coloridos. Um vértice colorido pode estar no interior da rota de outro par, sem deixar de ser extremidade de sua própria rota.
Minimize o maior comprimento entre as rotas. Se não houver emparelhamento válido, informe isso. Se não houver vértices coloridos, a resposta é zero.
Input
A primeira linha contém um inteiro ().
A segunda linha contém inteiros . O valor representa um vértice vazio, representa vermelho e representa azul.
Cada uma das próximas linhas contém três inteiros , e (, ), indicando uma aresta entre e de comprimento .
As arestas formam uma árvore não direcionada: o grafo é conexo e não tem ciclos, laços ou arestas repetidas. Não há garantia de que as quantidades das duas cores sejam iguais. A entrada contém uma única instância.
Output
Imprima o menor valor possível do maior comprimento de uma rota, ou -1 se não existir emparelhamento válido. Se não houver vértices coloridos, imprima 0.
Samples
Sample 1
Input
5 0 1 1 2 2 1 2 1 1 3 4 1 4 2 1 5 3
Output
6
Os pares e têm comprimentos e . Suas rotas compartilham o vértice , mas nenhuma aresta. A outra escolha de pares produz uma rota de comprimento .