#6681. yww 与树上的回文串

内存限制:512 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: yww

题目描述

给一棵树,每条边上有一个字符,求有多少对 (x,y)(x<y) ,满足 x y 路径上的边上的字符按顺序组成的字符串为回文串。

输入格式

第一行有一个整数: n

接下来 n-1 行,第 i 行有三个整数 x_i,y_i,z_i ,表示有一条连接 x_i y_i 的边,边上的字符为 z_i

输出格式

输出满足要求的点对数量。

样例

样例一

样例输入

4
1 2 0
1 3 0
1 4 1

样例输出

4

样例解释

满足条件的有: (1,2),(1,3),(1,4),(2,3)

样例二

见下发文件中的 ex_string2.inex_string2.out

样例三

见下发文件中的 ex_string3.inex_string3.out

数据范围与提示

子任务 1[5\ \text{pts}] n\leq 10

子任务 2[15\ \text{pts}] n\leq 5000

子任务 3[15\ \text{pts}] :对于所有的边, x_i=i,y_i=i+1

子任务 4[25\ \text{pts}] :对于所有的边, y_i=i+1,x_i [1,i] 之间随机。

子任务 5[40\ \text{pts}] :无特殊限制。

对于所有数据: 1\leq n\leq 50000,1\leq x_i,y_i\leq n,z_i\in\{0,1\}