题目描述
给一棵树,每条边上有一个字符,求有多少对 (x,y)(x<y),满足 x 到 y 路径上的边上的字符按顺序组成的字符串为回文串。
输入格式
第一行有一个整数:n;
接下来 n−1 行,第 i 行有三个整数 xi,yi,zi,表示有一条连接 xi 和 yi 的边,边上的字符为 zi。
输出格式
输出满足要求的点对数量。
样例
4
1 2 0
1 3 0
1 4 1
4
满足条件的有:(1,2),(1,3),(1,4),(2,3)。
见下发文件中的 ex_string2.in
与 ex_string2.out
。
见下发文件中的 ex_string3.in
与 ex_string3.out
。
数据范围与提示
子任务 1[5 pts]:n≤10;
子任务 2[15 pts]:n≤5000;
子任务 3[15 pts]:对于所有的边,xi=i,yi=i+1;
子任务 4[25 pts]:对于所有的边,yi=i+1,xi 在 [1,i] 之间随机。
子任务 5[40 pts]:无特殊限制。
对于所有数据:1≤n≤50000,1≤xi,yi≤n,zi∈{0,1}。