7697: BZOJ3697:采药人的路径

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

采药人的药田是一个树状结构,每条路径上都种植着同种药材。
采药人以自己对药材独到的见解,对每种药材进行了分类。大致分为两类,一种是阴性的,一种是阳性的。
采药人每天都要进行采药活动。他选择的路径是很有讲究的,他认为阴阳平衡是很重要的,所以他走的一定是两种药材数目相等的路径。采药工作是很辛苦的,所以他希望他选出的路径中有一个可以作为休息站的节点(不包括起点和终点),满足起点到休息站和休息站到终点的路径也是阴阳平衡的。他想知道他一共可以选择多少种不同的路径。


输入格式

第1行包含一个整数N。
接下来N-1行,每行包含三个整数a_i、b_i和t_i,表示这条路上药材的类型。


输出格式

输出符合采药人要求的路径数目。


样例输入

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

样例输出

1

提示

对于100%的数据,N ≤ 100,000。


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: