#P5365. [Lydsy1805月赛]回文树
[Lydsy1805月赛]回文树
回文树
题目描述
给定一棵 个点的树,节点编号为 。节点 上有正整数 。
令 为从 到 的唯一路径上,按从 到 的顺序读到的整数序列。如果这一序列正着读和倒着读相同,则称它为回文。例如 1 2 1 和 1 3 3 1 是回文,而 1 21 不是。每个节点上的整数是序列的一个元素。
求满足 且 是回文的点对 数量。
输入格式
从标准输入读入。第一行一个正整数 (),表示数据组数。
每组数据第一行一个正整数 ()。第二行 个正整数 ();原题说明每个 可视为在 内等概率随机选取。
接下来 行,每行两个不同的节点编号 (),表示一条无向树边。
输出格式
向标准输出对每组数据写出一行一个整数,表示满足条件的点对数。
样例
输入
2
3
1 2 1
1 2
2 3
2
2 2
1 2
输出
4
3
相关
在下列比赛中: