当前你的浏览器版本过低，网站已在兼容模式下运行，兼容模式仅提供最小功能支持，网站样式可能显示不正常。
请尽快升级浏览器以体验网站在线编辑、在线运行等功能。

建议使用的浏览器：

谷歌Chrome 火狐Firefox Opera浏览器 微软Edge浏览器 QQ浏览器 360浏览器 傲游浏览器

6295：回文树

题目描述
给定一棵$n$个点的树，任意两点之间有且仅有一条直接或间接路径。这些点编号依次为$1$到$n$，其中编号为$i$的点上有一个正整数$a_i$。你可以认为每个数$a_i$都是在$[1,n]$里等概率随机挑选的。

令$S(u,v)$表示在树上$u$到$v$的唯一最短路径上，按照离$u$从近到远依次考虑每个点，将它们上面的数字$a$按顺序写下连成的字符串。若一个字符串正着读和倒着读相等，则称它为回文串，比如1 2 1和1 3 3 1是回文串，但是1 21不是回文串。

请写一个程序，统计有多少个正整数对$(u,v)$满足$1\leq u\leq v\leq n$，且$S(u,v)$是回文串。
输入解释
第一行包含一个正整数$T(1\leq T\leq 20)$，表示测试数据的组数。

每组数据第一行包含一个正整数$n(1\leq n\leq 100000)$，表示点数。

第二行包含$n$个正整数$a_1,a_2,...,a_n(1\leq a_i\leq n)$，依次表示每个点上的数字。你可以认为每个数$a_i$都是在$[1,n]$里等概率随机挑选的。

接下来$n-1$行，每行两个正整数$u_i,v_i(1\leq u_i,v_i\leq n,u_i\neq v_i)$，表示一条连接$u_i$和$v_i$的双向树边。
输出解释
对于每组数据，输出一行一个整数，即满足条件的点对$(u,v)$的数量。
输入样例 
2
3
1 2 1
1 2
2 3
2
2 2
1 2
输出样例 
4
3
来自杭电HDUOJ的附加信息
Recommend liuyiding
该题目是Virtual Judge题目，来自 杭电HDUOJ
题目来源 "字节跳动杯"2018中国大学生程序设计竞赛-女生专场
源链接： HDU-6295
最后修改于 2020-10-25T23:30:03+00:00 由爬虫自动更新
共提交 0 次
通过率 --%
时间上限 内存上限
6000/3000MS(Java/Others) 512000/512000K(Java/Others)