음과 양

농부 존은 아침 산책을 계획하고 있다. 농장은 트리 구조로, $N$개의 헛간($1 \le N \le 100{,}000$)이 $N-1$개의 간선으로 연결되어 있어 어떤 헛간에서든 다른 모든 헛간으로 갈 수 있다. 존은 서로 다른 두 헛간에서 시작하고 끝나는 경로를 하나 고르되, 같은 간선을 두 번 지나지 않으려 한다. 경로가 다소 길어질까 걱정한 그는 이 경로 위에 "쉼터" 헛간도 하나 정하려 하는데, 이 쉼터는 시작 헛간과 끝 헛간 모두와 달라야 한다.

각 간선에는 소 떼가 있는데, 샤롤레(흰 털) 종이거나 앵거스(검은 털) 종이다. 현명한 존은 산책에 깃든 음과 양의 기운을 맞추고 싶다. 이를 위해, 시작 헛간에서 쉼터까지 가는 동안 지나치는 샤롤레 무리 수와 앵거스 무리 수가 같고, 쉼터에서 끝 헛간까지 가는 동안에도 두 종의 무리 수가 같도록 경로를 고르려 한다.

존은 이렇게 "균형 잡힌" 경로를 몇 가지나 고를 수 있는지 궁금하다. 두 경로는 이루는 간선 집합이 다를 때에만 서로 다른 것으로 본다. 또한 하나의 경로에서 균형을 만드는 쉼터 위치가 여러 곳 있더라도 그 경로는 한 번만 센다.

존이 고를 수 있는 균형 잡힌 경로의 수를 구하여라.

• 첫째 줄: 정수 $N$ ($1 \le N \le 100{,}000$).
• 둘째 줄부터 $N$번째 줄까지: 세 정수 $a_i$, $b_i$, $t_i$. 간선 $i$가 잇는 두 헛간이 $a_i$와 $b_i$이다 ($1 \le a_i, b_i \le N$). $t_i$는 그 간선의 무리가 샤롤레(흰 털)면 $0$, 앵거스(검은 털)면 $1$이다.

• 첫째 줄: 존이 고를 수 있는 균형 잡힌 경로의 수를 나타내는 정수 하나.

예제에는 $7$개의 헛간과 $6$개의 간선이 있다. 간선 1–2, 2–4, 2–5에는 샤롤레 무리가 있다. 길이가 $2$인 경로에는 적절한 쉼터를 둘 수 없으므로 길이가 $4$인 경로만 살펴보면 된다. 조건을 만족하는 유일한 경로는 3–1–2–5–7이며, 쉼터는 헛간 $2$에 둔다.