Yin and Yang

Farmer John is planning his morning walk on the farm. The farm is structured like a tree: it has $N$ barns ($1 \le N \le 100{,}000$) connected by $N-1$ edges, so he can reach any barn from any other. Farmer John wants to choose a path that starts and ends at two different barns and never traverses any edge twice. Worried that his path might be a little long, he also wants to pick a "rest stop" barn on this path that is distinct from both the start and the end.

Along each edge is a herd of cows, either of the Charolais (white hair) or the Angus (black hair) variety. Being a wise man, Farmer John wants to balance the forces of yin and yang on his walk. To do so, he wants a path such that he passes an equal number of Charolais herds and Angus herds both on the way from the start to the rest stop and on the way from the rest stop to the end.

Farmer John is curious how many different "balanced" paths he can choose. Two paths are considered different only if they consist of different sets of edges; a path is counted only once even if several valid rest-stop locations along it make it balanced.

Please determine the number of paths Farmer John can choose.

• Line 1: The integer $N$ ($1 \le N \le 100{,}000$).
• Lines 2 to $N$: Three integers $a_i$, $b_i$, and $t_i$, giving the two barns that edge $i$ connects ($1 \le a_i, b_i \le N$). $t_i$ is $0$ if the herd along that edge is Charolais (white) and $1$ if it is Angus (black).

• Line 1: One integer, the number of balanced paths Farmer John can choose.

In the sample there are $7$ barns and $6$ edges. The edges 1–2, 2–4, and 2–5 carry Charolais herds. No path of length $2$ can hold a suitable rest stop, so only paths of length $4$ need be considered. The only path with a suitable rest stop is 3–1–2–5–7, with the rest stop at barn $2$.