Processing math: 100%
编程题
                ### 问题描述

给定 N 个节点 N1 条边的树,边有点权,一对点对 (u,v) 满足 1u<vN 是好的,当且仅当简单路径 (u,v) 上所有边的边权构成的序列中,每种数字出现的次数均为偶数次,例如 2,2,1,1 满足条件, 1,1,4 不满足条件,询问有多少对点对 (u,v) 是好的。

输入格式

第一行包含 1 个正整数 N,表示树的节点个数。

之后 N1 行,每行给定 ui,vi,wi,表示一条无向边,边权为 wi

输出格式

输出一行,包含一个整数,表示答案。

样例输入

5
1 2 1
1 3 1
1 4 2
1 5 2

样例输出

2

样例解释

满足条件的点对有 (2,3),(4,5)

评测数据规模

对于所有测评数据,1N105,1wiN

查看答案
赣ICP备20007335号-2