题目描述

农夫约翰正在计划他早晨在农场里的散步路线。农场的结构是一棵树：它有 $N$ 个牛棚 $(1 \le N \le 100,000)$，由 $N-1$ 条边连接，使得他可以从任意一个牛棚到达任意另一个牛棚。农夫约翰想选择一条路径，这条路径从两个不同的牛棚之一出发，并在另一个牛棚结束，且不能经过任何边两次。他担心自己的路径可能有点长，所以他还想在这条路径上选择另一个“休息点”牛棚（该牛棚不能是起点或终点）。

每条边旁都有一群奶牛，品种要么是 Charcolais（白毛），要么是 Angus（黑毛）。作为一个聪明人，农夫约翰想要平衡散步途中作用在他身上的阴阳之力。为此，他希望选择一条路径，使得他经过的 Charcolais 牛群和 Angus 牛群数量相等——无论是从起点到休息点的途中，还是从休息点到终点的途中。

农夫约翰很好奇，他可以选择多少条如上所述“平衡”的不同路径。两条路径只有在它们由不同的边集合组成时才被认为不同；即使一条路径上有多个合法的“休息点”位置能使它平衡，这条路径也只应被计数一次。

请帮助求出农夫约翰可以选择的路径数量！

输入格式

• 第 $1$ 行：整数 $N$。

• 第 $2 \sim N$ 行：三个整数 $a_i$、$b_i$ 和 $t_i$，表示第 i 条边连接的两个牛棚。若该边旁的牛群是 Charcolais，则 $t_i$ 为 $0$；若该边旁的牛群是 Angus，则 $t_i$ 为 $1$。

输出格式

• 第 $1$ 行：一个整数，表示农夫约翰可以选择的可能路径数量。

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

1 

提示

共有 $7$ 个牛棚和 $6$ 条边。从 $1$ 到 $2$、$2$ 到 $4$ 以及 $2$ 到 $5$ 的边旁都有 Charcolais 牛群。

长度为 $2$ 的路径不可能有合适的休息点，因此我们只能考虑长度为 $4$ 的路径。唯一一条具有合适休息点的路径是 $3-1-2-5-7$，休息点在 $2$。

由 ChatGPT 5 翻译。