Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MAPA14 - Mapa

Byteland é uma cidade bastante movimentada, cujo prefeito, Joãozinho, vem lutando recentemente por sua inclusão no grupo das cinco cidades mais importantes de Byteworld. Para uma cidade ser considerada importante em Byteworld, ela precisa seguir alguns critérios. Antes de tudo, vamos definir Byteland, que é uma cidade como qualquer outra, onde esquinas se conectam através de ruas de mão dupla. Sabe-se também que existe um e somente um caminho, sem repetir esquinas, entre qualquer par de esquinas. Além disso, cada rua pode ser considerada importante ou não. Caso ela seja importante, a rua é pintada de branco e caso não seja, é pintada de azul.

Para saber se uma cidade é importante ou não em Byteworld é necessario calcular um valor E: a quantidade de pares de esquinas (A, B) tal que existe ao menos uma rua importante no caminho entre A e B. Note que (A, B) e (B, A) são o mesmo par!

O prefeito de Byteland resolveu pedir sua ajuda para calcular o valor E e saber, assim, se Byteland é ou não uma cidade importante para Byteworld.

Entrada
A primeira linha da entrada contém um inteiro N indicando a quantidade de esquinas em Byteland. As próximas N − 1 linhas da entrada contêm cada uma três inteiros, A, B e C , indicando que existe uma rua entre as esquinas A e B pintada da cor C . Caso C seja 1, a rua é branca e importante, caso seja 0, a rua é azul e não importante.

Saída
Seu programa deve produzir uma única linha, contendo um único inteiro, o valor E definido acima.

Restrições
• 2 ≤ N ≤ 105
• 1 ≤ A, B ≤ N
• 0 ≤ C ≤ 1

Informações sobre a pontuação
• Em um conjunto de casos de teste equivalente a 40 pontos, N ≤ 103.

Exemplos

Entrada
4
1 2 0
2 3 1
3 4 0

Saída
4

Entrada
6
1 2 0
2 3 1
3 4 0
2 5 0
5 6 1

Saída
11


Adicionado por:Edmundo Rodrigues
Data:2014-08-31
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:ADA95 ASM32 GAWK BASH BF C CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN GO HASK ICON ICK JAVA JS-RHINO LUA NEM NICE NODEJS OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYTHON3 RUBY SCM qobi SCM guile SED ST WHITESPACE
Origem:Olimpíada Brasileira de Informática 2014 - Nível 2 - Fase 2

hide comments
2015-03-14 04:18:47 Rerisson Daniel Costa Silva Matos[IFPB-CG]
Atençăo: Onde diz 105 na verdade é 10^5.

Last edit: 2015-03-14 04:20:06
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.