34224번 - 멀지만 가까운 사이

문제

숭고한 동네에는 $N$개의 마을이 있다. 마을들은 $N-1$개의 도로로 연결되어 있고, 도로는 항상 두 마을을 직접 연결하며, 모든 마을이 연결되어 있어 전체 구조는 하나의 트리^†이다. 각 도로에는 마을과 마을 사이의 거리가 적혀 있다.

문성이는 모든 마을 쌍 중에서 특별한 관계를 가지는 쌍들을 찾고자 한다. 문성이는 다음과 같이 정의된 마을 쌍을 멀지만 가까운 사이라고 부른다.

• 두 마을 $u,ドル $v$ 사이의 경로를 따라 도로의 거리 값을 전부 XOR 했을 때, 그 결과가 정확히 0ドル$이 되는 경우

문성이는 궁금해졌다. 이런 특별한 관계를 가진 마을 쌍이 총 몇 쌍이나 존재할까?

단, $(u, v)$와 $(v, u)$는 같은 쌍으로 간주하며, $u \ne v$인 경우만 센다.

^† 트리는 $N$개의 정점과 $N-1$개의 간선으로 이루어진 무방향 연결 그래프이다.

입력

첫째 줄에 마을의 수 $N$이 주어진다. $(2 \le N \le 500,000円)$

이어서 $N - 1$개의 각 줄에는 $i$번째 도로가 잇는 두 마을 $u_i,ドル $v_i$와 거리를 나타내는 정수 $w_i$가 공백으로 구분되어 주어진다. $(1 \le u, v \le N;\ 0 \le w \le 10^9)$

출력

첫째 줄에 멀지만 가까운 사이를 이루는 마을 쌍의 수를 출력한다.

제한

노트

두 수의 XOR 연산은, 두 수를 이진수로 나타냈을 때 각 비트 자리에서 서로 다르면 1ドル,ドル 같으면 0ドル$이 되는 비트 연산이다. 예를 들어, 6ドル$과 4ドル$를 이진수로 나타내면 각각 110ドル_{(2)},ドル 100ドル_{(2)}$이 되고, 두 수를 XOR한 값은 010ドル_{(2)}$으로 2ドル$가 된다.