[USACO13OPEN] Yin and Yang G

题目描述

Farmer John is planning his morning walk on the farm. The farm is structured like a tree: it has N barns (1 <= N <= 100,000) which are connected by N-1 edges such that he can reach any barn from any other. Farmer John wants to choose a path which starts and ends at two different barns, such that he does not traverse any edge twice. He worries that his path might be a little long, so he also wants to choose another "rest stop" barn located on this path (which is distinct from the start or the end).

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

Farmer John is curious how many different paths he can choose that are "balanced" as described above. Two paths are different only if they consist of different sets of edges; a path should be counted only once even if there are multiple valid "rest stop" locations along the path that make it balanced.

Please help determine the number of paths Farmer John can choose!

农夫约翰计划在农场进行晨间散步。农场的结构如同一棵树：共有N个谷仓（1 ≤ N ≤ 100,000），由N-1条边连接，使得他可以从任意一个谷仓到达其他任何谷仓。农夫约翰想要选择一条起点和终点为两个不同谷仓的路径，且他不会重复经过任何一条边。他担心路径可能有点长，因此他还想在这条路径上选择一个额外的“休息点”谷仓（该谷仓不同于起点或终点）。

每条边上有一群牛，要么是夏洛莱牛（白毛），要么是安格斯牛（黑毛）。作为一位睿智的农夫，约翰希望平衡他行走过程中的阴阳之力。为此，他想要选择一条路径，使得他从起点到休息点途中经过的夏洛莱牛群和安格斯牛群数量相等，并且从休息点到终点途中经过的两类牛群数量也相等。

农夫约翰想知道有多少条不同的路径满足上述的“平衡”条件。两条路径仅当它们由不同的边集构成时才视为不同；即使一条路径上有多个有效的“休息点”位置使其平衡，该路径也只应被计算一次。

请帮助确定农夫约翰可以选择多少条这样的路径！

输入格式

* Line 1: The integer N.

* Lines 2..N: Three integers a_i, b_i and t_i, representing the two barns that edge i connects. t_i is 0 if the herd along that edge is Charcolais, and 1 if the herd is Angus.

输出格式

* Line 1: One integer, representing the number of possible paths Farmer John can choose from.

样例 #1

样例输入 #1

7 
1 2 0 
3 1 1 
2 4 0 
5 2 0 
6 3 1 
5 7 1

样例输出 #1

1

提示

There are 7 barns and 6 edges. The edges from 1 to 2, 2 to 4 and 2 to 5 have Charcolais herds along them.

No path of length 2 can have a suitable rest stop on it, so we can only consider paths of length 4. The only path that has a suitable rest stop is 3-1-2-5-7, with a rest stop at 2.