小苯的路径计数

题号：NC315806
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 小苯有一棵 $n$ 个节点的有根树，根为 $1$ 。每个节点 $i$ 有一个颜色 $c_i$ 。
$\hspace{15pt}$ 小苯定义一条路径 $u \to v, u\neq v$ （ $u$ 是 $v$ 的祖先）是“同色路径”，当且仅当路径上所有节点的颜色相同。
$\hspace{15pt}$ 注意：路径必须是祖先 $\rightarrow$ 后代关系，且方向必须从祖先到后代。

$\hspace{15pt}$ 小苯想知道，树中一共有多少条不同的同色路径。
$\hspace{15pt}$ 你的任务是求出同色路径的数量。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数  代表数据组数，每组测试数据描述如下：

第一行包含一个整数 。
第二行包含  个整数 。
接下来  行，每行包含两个整数 ，表示树中有一条边 。保证构成一棵以  为根的树。

除此之外，保证单个测试文件的  之和不超过 。

输出描述:

对于每组测试数据：
输出一个整数，表示同色路径的数量。

示例1

输入

复制

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

输出

复制

3
2

说明

对于第一组测试数据，合法路径有： 三个。