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 ≤ 10^5
- 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 |
